짱아의 개발 기록장

오랜만에 이분탐색을 풀려고 하니까 머리가 돌아가지 않는다....ㅎ 하지만, 쉬운 이분탐색 문제여서 가볍게 풀 수 있었다. 첫 번째 숫자카드를 한 줄 받고 배열에 저장한다. 그리고 정렬한다. 두 번째 숫자카드를 한 개씩 첫 번째 숫자카드의 배열의 값과 이분탐색으로 대조한다. That's all..^^ 코드 첨부 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 // 숫자 카드 #include #include using namespace std; int arr1[500001] = {0, }; int arr2[..

문자열 처리와 유니온파인드를 모두 활용해야 하는 아주 괜찮은 문제이다. 글쓴이는 총 2가지 경우로 나누어서 처리해주었다. 1) 속국이 종주국을 공격하는 경우 2) 왕국이 다른 왕국이나 다른 왕국의 속국을 공격하는 경우 문제를 풀면서 생각했던 풀이방법을 아래 사진으로 첨부했다. (유니온파인드) 문제를 풀면서 또 헤맸던 부분이 문자열 처리 부분이다. 글쓴이는 getline()을 사용하여 문자열 한 줄을 전체 받았는데, 이상하게 앞에서 cin으로 n, m을 받고 나서 한 줄의 여백이 자꾸 생기는 바람에 마지막 입력 한 줄을 못받는 이상한 상황?이 벌어졌다. 아마 getline이 '\n'을 인식해서 벌어진 일 같은데,,,, 정확한 이유는 모르겠다,,, 그래서 해결 방법을 모색하다 cin.ignore()라는 것을..

흠... 골드5인데,,,참 어렵다...아직 글쓴이는 dp가 어려운 것 같다...^^ 그래서 구글에 검색해서 나온 코드를 읽어가며 이해하고 다시 풀었다. 8+3-2-4+8-7-2-4-0+8=8 이러한 식이 있을 때에 dp[지금까지의 합][현재 idx] 이렇게 저장했다. 맨 처음 idx=0일때는, dp[8][0] += (dp[11][1]+dp[5][1]) 그 다음의 수를 더한 경우와 그 다음 수를 뺀 경우를 모두 더한 값이다. 주절주절....코드를 보시면 더 이해하기 쉬울 것이다. 코드 첨부 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..

자칫 조합으로 그냥 풀다가는 바로 시간초과가 나버리는 문제이다. 이유는, 백트래킹으로 하나씩 확인하면서 하게 되면 바로 다른 경우로의 탐색이 가능하지만 조합으로 하나씩 확인해나가면 가지치기가 확실하게 되지 않기 때문에 그 만큼 시간단축을 할 수 없게 되기 때문이다. 따라서, 한 사람씩 기존에 있는 사람들과 모두 친구관계인지 확인하면서 조합을 해나갔다. 코드 첨부 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..

골드3였지만...여러 가지 경우의 수를 고려해야 하는 구현 과정이 매우 복잡했던 문제... 물론, 구현하는 방법이 사람마다 가지 각색이지만 글쓴이는 매우 복잡하게 푼 것 같다ㅎ 1. 먼저, 층을 쌓았다 (5!) -> 아래 코드에서 stacked함수 2. 각 층을 회전시켜주었다.(4^5) -> 아래 코드에서 rotate함수 3. bfs로 최단 경로를 구해주었다. -> 아래 코드에서 bfs함수 코드 첨부 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 6..

피보나치는 dp 알고리즘을 사용해서 풀 수 있는 전형적인 문제 중 하나이다. 피보나치 공식인 f(n) = f(n-1)+f(n-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 // 피보나치 수 5 #include #include using namespace std; int n; int dp[22] = {0, }; int go(int N) { if(dp[N]!=-1){ return dp[N]; } dp[N] = go(N-1)+go(N-2); return dp[N]; } int main() { memset(dp, -1, sizeof(dp)); cin>>n; dp[0] =..

처음에 아이디어가 잘 생각나지 않아 애를 먹었다. 그냥 일일히 bfs로 돌게 되면 당연히 시간초과가 날 것 같아서 무언가를 저장하고 그것을 가져다가 쓰는 방식으로 구현을 해야겠다고 생각했다. 따라서, 인접한 영역들을 idx로 표시해두고 해당 idx의 영영의 크기를 따로 vector에 저장해두었다. 아마 코드를 보면 더 이해하기 쉬울 것이라 생각한다. 코드 첨부 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 ..

이러한 유형은 매우 자주 접했던 그리디 유형이다. 보석의 정보와 가방의 정보를 각각 저장하고 보석은 무게를 기준으로 정렬, 가방도 정렬한다. 그리고 가방을 기준으로 가장 높은 가치를 가지고 있는 보석을 담는다. -> 우선순위큐 사용 코드 첨부 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 // 보석 도둑 #include #include #include #include using namespace std; int n, k, m, v; pair jewelry[300001]; int bag[300001] = {0, }; priorit..