조준화의 오류정정

문제를 재귀 방식으로 푼다는 것은 귀납적 방식으로 문제를 해결하겠다는 것이다. 이 마인드가 상당히 중요한데, 재귀 문제를 일반 문제 풀듯이 절차 지향적으로 이해하면 안 된다. 예를 들어 1~N까지 출력하는 재귀 함수는 아래와 같이 구현할 수 있다. void func1(int num){ if(num == 0) return; cout 2 출력 -> func1(1) 호출 -> 1 출력 -> func1(0) 호출 -> 종료와 같은 방식으로 이해할 수 있다. 나도 계속 이런 방식으로 이해했었고 그래서 재귀가 두려웠다. 이번에는 귀납적으로 사고해 보자. 1. func1(1)은 1을 출력하고 종료된다. 2. func1(k)가 k, k-1,..., 1을 출력한다고 가정했을 때 func1(k+1)은 k+1을 출력하고 f..

어제오늘은 재귀를 공부했다. 원래 백트래킹을 공부하려 했는데 바킹독님 블로그로 공부하다가 재귀먼저 꼭 이해하고 오라 하셔서 도전해 보았다. 원래도 재귀는 두려워해서 억지로 반복문으로 구현한 문제도 몇 있었다. 오늘까지 6문 제정도 풀었는데 귀납적 사고를 먼저 하고 재귀 구조를 짜면 확실히 비교적 쉽게 구현할 수 있었다. 그런데 재귀 문제들은 티어 기준이 이상한 것 같다... 실버 2문제를 풀다가 벽을 심하게 느껴서 굉장히 상처받았다. 2일 정도 재귀 문제들을 많이 풀다가 백트래킹으로 넘어가야겠다. + 알아두면 좋을 것 >n : 2^-n

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 먼저 문제를 파악해 보자. 한 변의 길이는 2^N이다. 또, 문제 풀이의 방향은 문제에서도 재귀를 언급하고 N=k-1일 때의 (r, c) 방문 위치를 N=k일 때 사용할 수 있으므로 재귀로 잡고 가자. 재귀로 푼다는 것은 귀납적으로 사고해야 한다는 뜻이다. N=0일 때 (r, c)의 방문 순서는 0인게 자명하다. N=k 일 때 (r, c)의 방문 순서를 α로 알고있다고 가정하자. 또 half는 한 변의 길이의 반으로 정한다. N=K+1일때 (r, c) ..

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 예제 3 ans : 7 1 3 1 2 3 2 1 3 2 1 2 3 1 3 n개의 원판을 기둥 1에서 기둥 3으로 옮기는 문제이다. 이 문제를 평소 풀듯이 생각해보았는데, 감도 안잡혔다. 당장 원판 하나를 어디로 옮겨야 하는지도 모르겠어서 일단 n번째 원판만 생각해보았다. n번 원판을 3번 기둥으로 옮기려면 1 ~ n-1 번 원판이 모두 임시 기둥에 있어야 한다. 그렇다면!! n-1개의 원판을 옮길 수 있다면 n개의 원판을 옮길 수 있다. 이 귀납적 사..

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 예제 10 11 12 ans : 4 a^b mod c를 구하는 문제이다. 가장 간단하게 생각할 수 있는 방법은 a^b을 구하고 mod c를 구하는 방법이다. 하지만 a, b, c 숫자가 모두 크기에 오버플로우도 나고, 시간초과도 뜬다. 오버플로우를 해결할 수 있는 방법은 long long 타입을 쓰면서 (a mod c)^b를 구하는 방식으로 해결할 수 있다. 이 방법은 O(b)만큼의 시간이 걸린다. 그러나 b의 크기는 매우 커서 또 시간 초과가 뜬다. 이 문제는 다음의 방법을 통해 귀납적 사고를 해서 재귀 구조로 구현하여 풀 ..

LCS(최장 공통부분 수열) 알고리즘은 두 개의 문자열에서 가장 긴 공통부분 수열을 찾는 알고리즘이다. 예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK로 길이는 4이다. LCS 알고리즘은 동적 프로그래밍으로 효율적으로 구현할 수 있다. dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 LCS 값이다. 알고리즘의 동작 단계는 다음과 같다. 1. 초기 조건 설정 각 문자열 앞에 0을 두어서 초기 조건을 설정한다. 이런 식으로 초기 조건을 설정하는 이유는 효율성이나 안정성 같은 측면에서는 영향이 없지만, 가독성과 코드 이해에 도움이 된다. dp [0][j] = 0, dp [i][0] = 0으로 설정한다. 초기 조건을 설정함으로써 다음에 나올 점화식을 초기 조건 ..

5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 예제 ABRACADABRA ECADADABRBCRDARA ans : 5 ------------------------------ UPWJCIRUCAXIIRGL SBQNYBSBZDFNEV ans : 0 LCS와 유사하지만 이 문제는 공통부분 문자열이 연속되어야 한다는 점이 다르다. 예를 들어 ABCD와 ABDC의 공통부분 문자열 중 BD는 존재하지 않는다. 풀이는 처음부터 LCS를 고려하고 생각했다. 그 외의 방법은 떠오르지도 않아서 일단 LCS처럼 2차..

오늘은 문자열 관련 문제 하나 풀고 C++ 이분탐색을 공부했다. 요즘 굉장히 번아웃이 와서 아무것도 하기가 싫다. 공부해야지 라는 죄책감은 계속 드는데 몸도 아프고 무기력하다... 하루에 한 문제라도 풀면서 좀 극복해야겠다. 순식간에 행복해졌다가 우울 해졌다가를 계속 반복한다. 현대인들은 조울증을 경계해야 된다더니 난 절대 아니다 싶었는데 절대는 없다보다...

이분 탐색은 정렬된 배열에서 특정 요소를 빠르게 찾는 알고리즘이다. 배열 내의 중간 요소를 선택하고 찾고자 하는 요소와 비교하여 해당 요소가 배열의 중간 요소보다 큰지 작은 지를 판단하고 탐색 범위를 절반으로 줄이는 방식이다. C++에서 이분 탐색 메서드들이 정의되어 있다. 1. binary_serach 주어진 정렬된 범위에서 특정 원소가 있는지 확인한다. 찾는 원소가 있으면 true, 없으면 false를 리턴한다. std::vector nums = {1, 2, 3, 4, 5, 6}; bool found = std::binary_search(nums.begin(), nums.end(), 3); // true 반환 2. lower_bound 주어진 정렬된 범위에서 특정 원소 이상인 첫 번째 원소의 위치를 ..

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 예제 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 ans : NO YES 한 번호가 다른 번호의 접두어인 경우가 있는지 체크하는 문제이다. 예를 들어 911과 9112314에서 911은 9112314의 접두어이므로 일관성이 없다고 판단한다. 1. 가장 간단하게 생각할 수 있는 방법으로 첫 문자열부터 끝까지 다 비교하는 방법을 생각했다. 시간제한은 1초이고 전화번호가 최대 10000개..