Algorithm

[백준 14442] 벽 부수고 이동하기2 C++

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS 1. 문제해결 아이디어 매번 칸을 이동할 때마다 지금까지 몇 개의 벽을 부쉈는지 정보를 가지고 있어야한다. struct P를 만들고 해당 객체를 queue에서 가지고 다니게 하였다. 가장 중요한 visited배열이다. visited[r][c][k] = 1 : r, c를 방문할 때 총 k번 벽을 부수고 방문했음을 의미한다. 만약 다음 좌표가 3, 5이고 지금까지 부순 벽이 2개라면 visited[3][5][3]이 0인지 확..

[백준 1007] 벡터 매칭 C++

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 브루트 포스 1. 문제해결 아이디어 처음에 단순히 최대 20개의 점 중에서 2개씩 묶어 나가는 방법으로 풀려고 했다. 위 방법대로 하면 O(20 * 18 * ... * 4 * 2) 같은 끔찍한 시간복잡도가 나와 불가능함을 알 수 있었다. v1, v2 이라는 벡터가 있다고 가정해보자 v1 + v2 = = 이 된다. 여기서 알 수 있는점은 N개의 점 중에서, N/2개의 점은 시작점이 될 것이고, 나머지 N/2개의 점은 도착점이 되는 것을 알 수 있다. 따라..

[백준 1005] ACM Craft C++

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..

[백준 14939] 불 끄기 C++

14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 그리디 알고리즘 1. 문제해결 아이디어 전구의 가장 윗 라인에서 스위치를 누르는 모든 경우(2^10=1024)를 시도해 본다. 그리고 두 번째 라인을 부터는 현재 열의 바로 윗 행의 전구가 켜져있는지 꺼져있는지에 따라서 스위치를 누를지 말지가 결정된다. 만약 바로 윗 행의 전구가 켜져있는데 현재 열의 스위치를 누르지 않는다면 앞으로 윗 행의 전구를 끌 방법은 없기 때문이다.(방향 : 왼쪽 상단부터 오른쪽 하단) 이렇게 하면 1~9 행은 모든 전구가 꺼질..

[백준 2011] 암호코드 C++

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 현재 자릿수에서 어떤 암호가 만들어 질 수 있는지 dp를 이용해서 해결해야한다. 우선 0은 암호로 바꿀 수 없다. 하지만 0 이전에 1 또는 2가 있다면 암호로 바뀔 수 있다. 숫자 3 이상과 이어지는 암호는 없다. 현재 숫자가 2인 경우 다음 숫자가 0 ~ 6 인 경우만 숫자 2개를 사용해서 암호를 만들 수 있다. dp배열 : dp[i][2] -> i번 자리수 이후로 숫자를 1개 또는 2개를 사용해서 만들 수 있는 경우를 저장하는 배열..

[백준 2143] 두 배열의 합 C++

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 문제에서 정의된 부 배열의 최대 크기는 N(N+1)/2 가 됨을 알 수 있었다. (1~N까지의 합) N, M이 최대 1000이므로 부 배열의 크기는 최대 500,000 이다. 따라서 배열에 담은 후 nlogn 연산이 충분히 가능함을 알 수 있었다. 이분 탐색을 수행하기 위해 subB배열을 정렬한다. T 에서 subA의 원소를 뺀 값이 subB에 있는지 ..

힙 정렬(heap sort) <priority queue> C++

min heap 구현 heap[i]의 값은 heap[i * 2] 와 heap[i*2 + 1]의 사이에 있다 BST(이진 탐색 트리)구조를 기반으로 한다 STL의 priority queue를 사용하면 되므로 직접 구현할 일은 없겠지만 heap 자료구조를 직접 구현해 본다는 점에서 의미있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using namespace std; vector heap; void push_heap(vector& heap, int newvalue){ heap.push_back(newvalue); int idx = he..

[백준 16929] Two Dots C++

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net DFS 1. 문제해결 아이디어 DFS를 통해서 사이클을 찾는 문제이다. 시작 알파벳과 같은 칸만 이동하며 시작 좌표에 다시 돌아올 때까지 or 돌아오지 못할 때까지 dfs 를 돌린다. 하나의 dfs루프에서 방문한 점을 backtracking 하지 않고 방문처리 기록을 남겨둔다. 2. 코드 : dfs를 돌면서 방문을 했거나 시작점으로 지목된 점에 방문을 한 경우 + 현재 점이 시작점이 아닌경우 (시작하자마자 return 되는것 방지) 1 2 3 4 5 6 ..

[백준 1309] 동물원 C++

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 기초 1. 문제풀이 아이디어 row행에서 사자를 놓는 모든 경우의 수 = row행에 사자를 놓지 않는 경우 + row행의 1번에만 사자를 놓는 경우 + row행의 2번에만 사자를 놓는 경우 row행에 사자를 놓지 않는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만 사자를 놓는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 1번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 2번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만..

[백준 17298 17299] 오큰수 , 오등큰수 C++

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료구조, 스택 문제 1. 문제풀이 아이디어 N이 최대 1,000,000이므로 단순히 2중 for문으로 해결하는건 시간제한에 걸리게 된다. (N이 최대 5,000 정도면 가능할듯..) (1) 오큰수 1. 스택이 비어있을때 지금 보는 배열의 원소와 원..