알고리즘/BOJ 썸네일형 리스트형 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 배열을 인덱스.. 더보기 2110번 2110번 - 공유기 설치 ##############다시 풀기################## 이 문제는 종만북에 있는 카메라 설치 문제와 똑같다. 문제를 풀려고 고민하다가 안 풀려서 okay() 함수 부분을 어떻게 구상해야 할지 몰라서 참고해서 풀었다. 최적화 문제를 결정문제 + 최적화문제를 합쳐서 푸는 방식이었다. 공유기 설치하는 방법은 그냥 맨 처음 집부터 설치하는 탐욕적 알고리즘을 사용한다. (그리디 알고리즘을 공부할 필요가 있다. 설명을 듣고나면 충분히 이해가지만, 어떤 논리적 판단 없이 이런식으로 생각하기는 어려울 것 같기 때문에) okay() 함수에서는 특정 거리에서 공유기의 숫자를 K 보다 많이 설치할 수 있는지 판단하는 결정 문제를 푸는 함수이고, 이에 따라 이분탐색을 통해서 최적값을 찾.. 더보기 10816번 - 97% 시간 초과(해결) 10816번 - 숫자 카드 2 ##################다시 풀기################## 일단 이분 탐색 방법에서 찾은 후에, 왼쪽을 다시 이분탐색, 오른쪽을 이분탐색 하는 방식. 아직 이 문제는 제대로 못 품 ( 97% 시간 초과 ) ... 이유를 모르겠음... 나도 어떤 분 코드를 보고 참조하였음. 근데 그 분 코드도 내가 그대로 돌려보니 시간초과가 발생... 문제점 1. vector 로 구현하다가 느리다고 하여 배열로 바꿨지만 여전히 시간 초과.. 2. cin, cout 전부 printf, sacnf 로 바꿨지만 시간 초과. ==> 문제점 해결 입력으로 가지고 있는 카드가 50 50 50 50 50 이렇게 max 로 들어오고 확인해야 할 카드 또한 50 50 50 50 이런식으로 입.. 더보기 10815번 10815번 - 숫자 카드 이분 탐색을 통해서 풀 수 있었다. 우선 가지고 있는 카드들은 sort() 함수를 통해서 오름 차순으로 정렬한다. (이분 탐색은 정렬되어져 있는 데이터 중에서 원하는 값을 찾을 때 중요하다는 것을 깨달았다. 이전 이분탐색에서는 그냥 완전탐색을 좀 빠르게 한다라고 생각한다고 써놨었다. 그런데 질문도 올리고 그러면서 다른분의 말씀을 들으니 정렬되어있다! 라는게 정말 중요한 말이었다. 이전 문제들도 따로 정렬은 안했지만 찾고자 하는 값이 0 ~ 랜선의 길이, 나무의 최대 높이 처럼 정렬되어 있는 값이었던 것이었다.) 그 뒤 이번 문제는 배열의 인덱스를 가지고 , lo 와 hi 를 변화시켜주면서 가장 가까운 인덱스 값을 찾는다. 그 가장 가까운 값이 내가 찾고 있는 값이라면 1을, 그.. 더보기 2805번 2805번 - 나무 자르기 이분 탐색 문제 중 하나, 앞에서 풀어봤던 1654번이랑 거의 똑같다. 이 문제도 N을 제외한 모든 자료형에 int 대신 long long을 써야했다. 자꾸 습관적으로 main 에서 long long 쓰지만 함수에서 int를 써버리는 실수를.... 이분 탐색에 대해서 궁금증 - 이분 탐색을 하다보면 결국 low, mid , high 가 거의 근사한 값에 다가 올 텐데.. int 형 변수로 하면 low 랑 high랑 1차이가 나게된다.. 항상 답을 low로 출력해야하는지.. mid 로 출력해야하는지.. 내일 궁금증을 어디에 올려서라도 해결해야 겠다.. 123456789101112131415161718192021222324252627282930313233343536373839404.. 더보기 1654번 1654번 - 랜선 자르기 이분 탐색에 대해서 종만북으로 한번 보고 풀어본 문제. 만약 내가 이 문제가 이분탐색 문제라는 걸 몰랐다면 풀 수 있었을까? 이런 고민을 많이 한다. 이분 탐색도 결국은 주어진 범위 내에서 해가 있을 때, 완전 탐색을 좀 빠르게 하는 방식? 이라고 나는 이해했다.. 앞으로 몇 문제를 더 풀어보면서 익혀야겠다. decision() 함수를 통해 결정 문제로 바꾸고, 이분탐색을 통해 최적값을 찾도록 하였다. 문제에서 실수 2가지 1. 처음에 high 값을 vector.back() 으로 넣었는데 , 이러면 만약 답이 high 값이 될 경우에는 lo 가 high 에 막혀서 못 올라가는 경우가 생겼다. 그래서 high 값을 vector.back() + 1값으로 바꿔주었다. 마찬가지로, 물.. 더보기 이전 1 ··· 31 32 33 34 35 36 37 ··· 40 다음