짱아의 개발 기록장

백트래킹 하면 가장 많이 떠올리는 문제이다. 근데 이 문제는 시간초과때문에 고생할 수가 있기 때문에 효율적인 최적화 작업을 해주어야 한다. 사실 글쓴이의 풀이보다 1차원 배열을 통해서 더 최적화해서 시간을 줄일 수 있는 풀이방법이 있는 것으로 알고 있다. 따라서, 코드는 참고만 해두시면 좋을 것 같다. (그닥 좋은 풀이는 아닌 것 같다... 시간이 오래 걸림;;) 아무래도 2차원 배열을 활용했고 더 가지치기를 할 수 있는데 적당히만 가지를 쳐서 시간이 오래걸리는 것 같다,,, 나중에 더 최적화를 해보는 걸로... 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 38 39 ..

위상정렬을 이론으로는 알고 있었지만 직접적으로 활용해서 푸는 문제는 처음 접했다. 요즘 라인, 네이버 등 it회사에서 자주 출제되는 경향이 있어서 연습삼아 풀어보았다. 위상정렬에 대한 이론 정리는 아래 블로그에서 아주 잘 정리해놓아서 참고하시면 될 것이다. gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 이 문제는 우선순위큐를 사용해서 위상정렬을 그대로 구현한 문제이기 때문에 코드를 참고하시는게 좋을 것 같습니다. 1 2 3 4 5 6 7 8 9..

그리디 문제이다. 가스관에서 빵집으로 가는 특정 경로를 완성하게 되면 그것과 전혀 겹치지 않는 경로를 또 만들어야 하기 때문에 한 번 빵집에 도착했으면, 맨 처음 가스관으로 돌아가서 새로운 경로를 찾아가는 것이 핵심이다. 그래서 dfs에서 빵집에 도착하면 true를 리턴해주어서 계속 처음으로 돌아가게 해주었다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 // 빵집 #include using namespace std; int r, c; string s; char map[10001][501]; i..

중위순위의 특징?을 통해서 풀 수 있는 문제이다. 중위순회의 특징은 Start~End의 범위를 가지고 있는 배열에서 Mid = (Start+End)/2;의 값이 루트가 된다는 것이다. 그렇게 계속 재귀를 돌면, level별로 노드를 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546// 완전이진트리#include #include using namespace std; int k, node;vector height[11];int arr[1100] = {0, }; void dfs(int Start, int End, int level){ int mid = (Start+End)/2; height[le..

방문처리가 핵심인 BFS문제였다. 그냥 (x, y)로만 방문처리를 해주면, 더 빠른 길인데도 불구하고 누락되는 경우가 생긴다. 따라서, 말로 몇 번 이동했는지를 인자값으로 하나 더 넣어주었다. => visited[x좌표][y좌표][말 이동 횟수] 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 // 말이 되고픈 원숭이 #include #include #include using namespace st..

점화식을 세워서 풀 수 있는 DP문제였다. DP[n] = DP[n-1]+DP[n-5]; 1~5의 DP값은 미리 넣어놓고 이것보다 큰 값의 경우에만 계산해주었다. 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 // 파도반 수열 #include using namespace std; int n, testcase; long long dp[101] = {0, }; void setting() { dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; } int main() { cin>>testcase; setting(); for(int i=0; i>..

dfs로 해결할 수 있는 문제지만, 유니온파인드를 사용해서 풀었다. 다만, 문제를 풀다가 계속 20%에서 틀려서 엄청 고생했다..ㅎㅎ 스터디원의 도움을 받아서 반례를 찾을 수 있었다. 간선을 모두 이어서 cycle이 형성되면 그 집단의 최상위 부모를 cycle[최상위부모] = true로 해주었다. 하지만, 문제가 cycle이 이미 형성되고 간선을 긋게 되면 그것을 같은 cycle집단으로 판단하지 못하는 잘못된 로직을 구현했다. 아래는 내가 틀렸던 반례이다. 9 9 1 2 2 3 3 4 4 5 3 5 6 7 7 8 6 8 8 9 정답 : Case 1: No trees. 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..

오랜만에 그리디 문제를 풀어봤다. 역시 그리디는 아이디어를 도출해내는 것이 참 어렵다...ㅎ 하지만, 그렇게 어려운 그리디 문제에 속하지는 않아서 생각보다 간단하게 해결할 수 있었다. 우선순위큐를 사용했고 맨 마지막에 있는 마감일 기준으로 우선순위큐에 값을 넣어서 각 날마다 가장 큰 값을 더해주었다. 아래는 놓치기 쉬운 반례들이다. 6 5 3 5 3 5 3 4 2 4 1 4 2 정답 : 13 4 9 9 9 9 9 9 1 10 정답 : 37 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354// 과제#include #include #include #include using name..