알고리즘
-
BOJ) 빵집 (3109 번)알고리즘/백준 2021. 2. 23. 01:18
빵집 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다. 이 문제에서 필요한 제약 조건들이다. 그리고 가장 중요한 힌트는 문제의 사진 첨부에 나온다..
-
BOJ) 자두나무 (2240 번)알고리즘/백준 2021. 2. 23. 01:12
자두나무 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 처음 위치 1을 기준으로 자두나무에서 떨어지는 열매를 최대한 받을 수 있는 개수를 구하는 문제다. 자두나무는 1과 2 위치에만 있고, 1초마다 떨어지는 위치 정보가 주어진다. DP를 이용해서 이 문제를 풀었다. DP의 인덱스는 시간과 움직이는 횟수를 가진다.1초에 n번을 움직였을 때, 가장 큰 값을 저장해나간다.이동한 횟수가 짝수일 때와 홀수일 때를 나누어주었다.for문 하나에서 인덱스만 각각 구해서 돌릴 수 있겠지만, if문을 통해 w를 넘는지 확인해주어야 하..
-
BOJ) 수들의 합 2 (2003 번)알고리즘/백준 2021. 2. 18. 11:48
수들의 합 2 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N개의 수열에서 i ~ j 번 째의 값들의 합이 M이 되는 경우를 구하는 문제다. N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) 의 조건이 주어진다. 투포인터는 슬라이딩 윈도우와 유사하지만 다른 점은 바로 탐색 구간의 길이가 정해져있지 않다는 것이다. 투포인터를 활용해서 푸는 문제인데, 익숙하지 않아서 기록에 남겨둔다. 우선, 시작점 탐색을 도와줄 left와 끝점 탐색을 도와줄 ..
-
BOJ) 가르침 (1062 번)알고리즘/백준 2021. 2. 18. 11:40
가르침 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다. 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 구하는 문제다. 단어는 모두 소문자로 주어지고, 1
-
BOJ) 순열 사이클 (10451번)알고리즘/백준 2021. 2. 15. 14:58
순열 사이클 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 1 ~ N 으로 이루어진 순열을 방향 그래프로 나타냈을 때, 몇 개의 사이클이 존재하는지 구하는 문제다.각 Node에서 다음 Node의 vertex를 가지고 있고, 이 정보가 주어지기 때문에 배열을 활용했다.또한, find-union에서 착안하여 연결되는 지점을 DFS로 찾아가며 문제를 해결했다. 사이클을 형성하는지 확인하는 isCycle 메소드를 만들어 주었다.return 값은..
-
BOJ) 앱 (7579 번)알고리즘/백준 2021. 2. 15. 14:45
앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 스마트폰 앱을 이용하는데, 사용자에게 더욱 빠른 반응을 위해 백그라운드에서 앱이 돌아간다. 하지만, 메모리는 한계가 존재하기 때문에 새로운 앱을 실행시키기 위해서 백그라운드에서 돌아가는 앱 중 일부를 종료시켜야 한다. 종료된 앱을 다음에 이용할 때 드는 비용을 최소화하는 문제다. 설명이 조금 복잡해서 여러번 틀렸지만, 문제를 제대로 이해한 뒤의 풀이 자체는 어렵지 않았다. 우선, 실행중인 앱의 정보를 저장해주었다. 현재 메모리를 얼마나 차지하는지, 종료한 뒤에 나중..
-
BOJ) 다리 만들기알고리즘/백준 2021. 2. 14. 23:20
다리 만들기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 여러 섬으로 이루어진 나라에서 가장 가까운 두 섬을 잇는 최단 거리 비용을 구하는 문제다. 최단 거리라고해서 해당 알고리즘들을 사용할 수 있을까 고민했는데, 떠오르지 않았다. 그래서 평소에 즐겨하던 grouping을 하면서, 모든 섬마다 전체 좌표를 List에 저장했다. 또한, 각 섬마다 위치를 식별할 수 있어야해서 위의 섬의 좌표를 저장하는 List를 List에 저장해주었다. List 으로 섬의 모든 좌표를 저장해주었다. 좌표를 모두 저장한 이후에는 각..
-
BOJ) 스도쿠 (2580 번)알고리즘/백준 2021. 2. 14. 23:13
스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠의 조건에 따라 로직을 짜주었고, 백트래킹을 이용했다. (백트래킹을 사용하지 않으면 시간초과가 난다) 우선, 재귀 함수를 사용할 예정이어서 모든 스도쿠 맵을 돌면서 빈칸인 곳을 찾는 것이 비효율적이라고 생각했다. 그래서, 스도쿠 맵을 저장할 때, 비어있는 칸의 위치를 List에 저장해서 빈 칸들만 순회하도록 만들었다. 그리고, 빈 칸들에 들어갈 수 있는 모든 수를 넣어보면서, 적합한 수를 넣어주었다. 모든 수를 검사할 때는 빈칸의 가로와 세로에 어떤..