Algorithm

[백준 1280] 나무심기 (C++)

1280번: 나무 심기 첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다. www.acmicpc.net 세그먼트 트리를 응용하는 문제 tree 배열은 나무를 심을 수 있는 좌표의 구간(0 ~ 200000)을 node번호로 하는 세그먼트 트리이다. 0 ~ 200000 : 1번 노드, 0 ~ 100000 : 2번 노드, 100001 ~ 200000 : 3번노드 ...... 각 구간에 속하는 나무의 개수가 tree[node].first에 저장된다. 각 구간의 나무 위치의 합이 tree[node].second에 저장된다. 이 정보들이 왜 필요한가?? 새로운 나무를 심을..

[백준 3020] 개똥벌레 (C++)

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이를 떠올리기 어려운 문제였다. top 배열과 bottom 배열의 의미 처음 input함수에서 종유석과 석순의 높이를 입력 받으며, 해당 구간에서 길이가 끝나는 종유석, 석순의 개수를 카운팅해준다. 높이가 7일 때, ex) 석순 3이 입력되면 3번 구간의 장애물이 하나 생겼음을 알 수 있다. ex) 종유석 5가 입력되면 3번 구간의 장애물이 하나 생겼음을 알 수 있다. (7 - 5 + 1) 입력이 끝나면 모든 구간에 있는 장애물의 개수를 누적합으로 계산해 준다. ..

[백준 1649] 택시 (C++)

1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 ≤ N ≤ 1,000)과 도로의 개수 M이 주어진다. 그 다음 M개에 줄에는 도로의 정보를 알려주는 시작점과 끝점이 주어진다. 다음 줄에는 시작점 A와 끝점 B, 그리고 방 www.acmicpc.net 조건 N개의 노드가 존재하고 노드들은 서로 단방향으로 연결되어 있다. A라는 노드에서 출발해 다시 A노드로 돌아올 수 없다. U -> V 연결이 있다면 V -> U 연결은 있을 수 없다. A에서 B로 가야 한다. 가는 도중에 C1, C2 ... Cn 노드를 거쳐가야 한다. 이때 중간 노드의 방문 순서는 중요하지 않다. 요구사항 A에서 B로 가기 위한 경로의 수를 출력하라. A에서 B로 가는 모든 경로를 탐색해보는 top-down DP로 풀려다가 도저히..

[백준 1039] 교환 (C++)

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net N이 100만보다 작다는 조건 덕분에 문제를 해결할 수 있었다. 최대 10번의 교환을 수행할 수 있기 때문에, 몇 번째 교환일 때 어떤 수가 나왔는지 확인한다면 모든 경우의 수를 확인해서 최솟값을 찾을 수 있다. -> check[1000001][11] 처음 숫자가 한자릿수라면 교환이 불가능하기 때문에 -1을 출력한다. 처음 숫자가 두자릿수일 때 일의 자리가 0이라면 교환이 불가능하기 때문에 -1을 출력한다. dp를 수행하면서 교환한 수가 0으로 시작할 때는 넘긴다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..

[백준 1368] 물대기 (C++)

1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 모든 논을 최소 비용으로 연결시키는 문제이다. 따라서 최소 스패닝 트리라고 생각할 수 있다. 문제의 핵심은 이미 물이 있는 논을 통해서만 물을 댈 수 있다는 것이다. 그래서 어렵게 생각한다면 우물을 파는데 가장 비용이 적은 논을 구하고.. 그 논을 통해서 가장 비용이 적은 간선을 선택하고.. 등등 케이스가 복잡한 상황이 정말 많이 생길 것이다 다익스트라에서 주로 사용했었던 방식인데 가상 노드를 하나 설정한다. 가상 노드는 논들과 연..

[백준 1322] X와 K (C++)

1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net X + Y = X | Y 위 식의 의미는 다음과 같다. 두 수를 2진수로 바꾸었을 때 x와 y가 가진 비트 '1'의 위치가 모두 서로 다르다는 뜻이다. 같은 말로 X의 비트가 0인 위치에만 1이 채워져 있는 수가 Y가 될 수 있는 수이다. 문제를 풀기 위해서는 위 아이디어를 다음과 같이 응용하면 된다. 7번째 Y 값을 찾고싶을 때 7은 2진수로 바꾸면 111 이다. X를 5로 가정하면 X는 ..000101 이라고 생각할 수 있다. 여기서 비트 1의 위치는 보지않고 0인 위치를 숫자가 들어갈 수 있는 위치라고 생각하자. 따라서 7이라는 숫자가 들어갈 수 있는 비..

[백준 20928] 걷는 건 귀찮아 (C++)

20928번: 걷는 건 귀찮아 일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 세상 www.acmicpc.net 1. 현재 인력거에서 M까지 갈 수 있는지 확인한다. M까지 갈 수 있다면 결과 값을 최솟값으로 갱신한다. 2. 현재 인력거에서 갈 수 있는 인력거들을 모두 queue에 넣는다. 이때 가장 멀리있는 인력거 위치 이후부터 찾는다. 인력거를 찾게되면 그때마다 가장 멀리있는 인력거의 위치를 갱신해준다. 알고리즘 과정 입력 4 10 1 3 5 7 4 6 5 2 파란색 동그라미는 인력거의 위치를 의미한다. 파..

[백준 1486] 등산 (C++)

1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net 다익스트라를 사용해서 풀었다. 가로와 세로의 최대 길이가 26으로 짧다. 시작점으로 되돌아와야 한다. 1. 모든 점에 대해서 원점으로 돌아오는 최단거리를 구한다. 우선순위 큐에 들어갈 수 없는 정점은 아래와 같다. 1. 현재 위치의 높이와 다음 위치의 높이 차이가 T보다 크다 2. 다음 정점에 대해서 이미 최단거리가 구해져 있다. 3. 다음 정점으로 가는 거리가 D보다 크다. 4. 다음 정점이 Map을 벗어난다. 위 4가지의 경우에 대해서 con..

[백준 1726] 로봇 (c++)

1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 오랜만에 푼 알고리즘 문제 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 두 가지 조건을 만족하며 출발 로봇이 도착지점의 상태와 같아질 때까지 이동시키는 프로그램을 구현하면된다. 나는 K칸 만큼 움직일 때 갈 수 없는 모든 조건에 break를 걸어주어서 많이 틀렸다. 벽에 막혀서 갈 수 없는 경우에만 ..

[백준 1826] 연료 채우기 (C++)

1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 처음에 DP 문제인줄 알고 DP로 접근을 시도했었다. dp[현재 이동한 거리][현재 가지고 있는 연료 양] 을 두면 top down DP를 통해서 쉽게 구할 수 있을거라고 생각했었다. 근데 L이 최대 100만이고 연료 양도 최대 100*10000 라서 DP 배열 자체를 할당할 수가 없었다. N과 L이 너무 커서 이건 무조건 그리디라고 생각했고 실제로 그리디로 풀수가 있었다. 1. 현재 연료를 모두 소진할 때까지 쭉 달린다. ..