전체 글 썸네일형 리스트형 2447번 2447번 - 별찍기 10 규칙을 찾아서 해결하는 문제. 문제의 조건에서 3의 k 제곱으로 주어진다고 했으므로 뭔가 3이나 9와 연관이 있는 규칙이 있을거라 추측이 가능했다. 그래서 보니 9개로 나누었을 때, 재귀적으로 반복되는 것이 보였다. 따라서 분할정복의 방식으로 분할하고 재귀로 푸는 방법으로 접근했다. * 풀면서 발생했던 문제 - 나는 별을 재귀함수 내에서 곧바로 출력하는 방식으로 문제를 풀려고 했었다. 내가 다른 별찍기 문제를 풀었던 것처럼... 근데 그러다보니 분할 정복인데, 분할 정복이기 때문에 같은 줄에 1사분면과 2사분면을 배치하는 것이 불가능했다... 이를 굉장히 오랜시간 뒤에 깨달았다.. 물론 푸는 도중에 배열을 사용해서 할까 하다가도 스스로의 고집 때문에 계속 같은 방식을 고수했다... 더보기 1517번 1517번 - 버블 소트 #########다시 풀어보기########### 분할 정복을 조금 알아갈 것 같은 느낌... 아직도 어렵다 사실 버블 소트가 일어날 때, swap 되는 횟수를 구하는 문제. 처음에 어 쉽네? 하고 N값을 봤더니 50만, 그냥 이중 for문을 통해서 O(N^2) 으로 구하면 구할 수 없는 시간이었다. 그래서 생각해낸 방법은 분할 정복을 써야할 것 같은데..까지밖에 생각 못 했었다. 오래 고민하다가 다른 분들의 풀이를 보고, 아 그런 방법이 있구나 하고 풀었다. 그냥 병합 정렬을 하면서 숫자를 세는 간단하지만, 생각해내지 못한 방법이었다. 병합 정렬에서 왼쪽그룹, 오른쪽 그룹은 항상 오름차순으로 정렬이 되어있다. 따라서 정렬되어져 있는 왼쪽 그룹 사이 사이로 오른쪽 그룹의 숫자가 .. 더보기 1992번 1992번 - 쿼드 트리 분할 정복 문제. 말 그대로 분할해서 문제를 풀고 합친다. 반복 되는 부분을 재귀로 구현했다. 주어진 영상이 하나의 수로만 표현되어 있지 않다면 !perfect 로 4분할을 하게 된다. 하지만 영상이 하나의 수로 perfect 하다면 그 숫자를 출력하면 된다. string 쓰는 법을 잘 몰라서 그냥 + 로 계속 덧 붙여서 저장하였다. 함수의 인자로는 시작하는 x좌표 sx, 시작하는 y좌표 sy, 맵의 크기 N으로 구성하였다. 재귀는 단순하게 생각하자... 재귀는 단순하게... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include#i.. 더보기 11729번 11729번 - 하노이 탑 이동 순서 하노이하면 가장 먼저 떠오르는게 재귀인데.. 나는 사실 하노이에 대해서 어떻게 푸는지 몰랐다.. 백지 상태에서 풀려는데 너무 어려워서 검색을 통해서 하노이에 대해서 공부를 먼저 했다. 재귀는 역시 이해하기가 어렵긴 한데.. N-1 개 옮기고, 1개 옮기고, N-1 개 다시 옮기는게 그냥 핵심이었다. 그 과정에서 N==1 일때만 잘 체크해주면 되는 재귀함수였다. 코드에서 ans 를 구하는 방식을 2^N - 1을 썼는데 이는 하노이탑에서 경우의 수를 구하는 방법이다. 이 과정은 점화식 N개 원반을 몇번 움직여서 다 옮길 수 있는가 D[N] = D[N-1] + 1 + D[N-1] 로 놓고 DP 로 구할 수 있다. ## 이 문제는 cout 이 아닌 printf 를 써야만 시.. 더보기 1780번 1780번 - 종이의 개수 이 문제는 분할 정복으로 문제를 풀었다. 일단 같은 방식이 계속해서 이어지기 때문에, 그에 따라 재귀함수를 수행시켰다. ans 배열은 종이의 갯수를 담도록 크기를 3으로 지정하고, -1의 종이 갯수는 index 0에, 0의 종이 갯수는 index 1에 , 1의 종이 갯수는 index 2에 저장했다. 재귀함수에서 크기가 1인경우, 즉 n==1 인 경우에는 곧 바로 해당하는 종이의 갯수값을 증가시켰다. 그러지 않을 경우에는 전체 맵을 돌게 만들었고, 전체 맵이 하나의 숫자로만 이루어진 경우는 또 종이의 값을 증가시켰다. 하지만 하나의 숫자가 아닐 경우에는 9개의 종이를 재귀탐색 하도록 설정하였다. 종만북에 있는 문제와 비슷하다. 종만북 풀때 다시 풀어볼 것, 종만북과 나의 풀이 비.. 더보기 11728번 11728번 - 배열 합치기 병합 정렬을 이용해서 문제를 풀었다. 병합 정렬 개념만 알고 코드를 어떻게 구현할 지 몰랐는데, 다시 알아보면서 코드를 짜보았다. 물론 처음에 짜지 못했다. 병합 정렬에 나오는 재귀 함수 부분에서 또 약간 헷갈렸지만, 재귀함수는 생각하고 생각할 수록.. 생각이 재귀에 빠질 수록 힘든 것 같다. 그냥 그 코드에 적혀 있는 그대로를 곧 바로 이해하려고 노력해야겠다. 계속 재귀에 빠지다 보면 내가 다 헤어나올 수 없다. 이 문제는 모든 값들을 배열 A에 입력받고, A를 왼쪽 분할하고 정렬, 오른쪽 분할하고 정렬, 마지막으로 전체 정렬하는 방식으로 하였다. merege() 함수에서는 while 문 세개를 통해서 tmp 라는 임시배열에 값들을 정렬하여 저장하였고, tmp 배열을 인덱스.. 더보기 Sorting 알고리즘 참고용 https://www.toptal.com/developers/sorting-algorithms/ https://medium.com/@fiv3star/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-sorting-algorithm-%EC%A0%95%EB%A6%AC-8ca307269dc7 sorting algorithm 참고용 더보기 2110번 2110번 - 공유기 설치 ##############다시 풀기################## 이 문제는 종만북에 있는 카메라 설치 문제와 똑같다. 문제를 풀려고 고민하다가 안 풀려서 okay() 함수 부분을 어떻게 구상해야 할지 몰라서 참고해서 풀었다. 최적화 문제를 결정문제 + 최적화문제를 합쳐서 푸는 방식이었다. 공유기 설치하는 방법은 그냥 맨 처음 집부터 설치하는 탐욕적 알고리즘을 사용한다. (그리디 알고리즘을 공부할 필요가 있다. 설명을 듣고나면 충분히 이해가지만, 어떤 논리적 판단 없이 이런식으로 생각하기는 어려울 것 같기 때문에) okay() 함수에서는 특정 거리에서 공유기의 숫자를 K 보다 많이 설치할 수 있는지 판단하는 결정 문제를 푸는 함수이고, 이에 따라 이분탐색을 통해서 최적값을 찾.. 더보기 이전 1 ··· 51 52 53 54 55 56 57 ··· 61 다음