PS (25) 썸네일형 리스트형 2022-03-20::DP Dynamic Programming DP는 분할 정복의 한 형태이다. 분할정복 방식은 다음과 같은 형태로 진행된다. DP문제가 판별도 어렵고 그 방식이 다양하기 때문에 상당한 창의력이 요구되는 파트라고 생각한다. 특정 단계에 영향을 끼치는 단계가 무엇인지, 단계간 관계는 어떠한 형태인지 파악하는 것이 중요하다. 1. 한 번에 해결하기 힘든 문제를 잘게 자른다. 2. 잘게 자른 문제의 해답을 이용해 더 큰 문제를 해결한다. 3. 최종 답을 구한다. DP 위와 같은 형태에 중간 값들을 저장해 중복되는 계산을 생략한다는 특징이 있다. DP문제 중 가장 처음 만나는 것 중 하나가 바로 피보나찌 수열 구하기이다. 피보니찌 수열의 N번째 요소를 구할 때, 메모이제이션을 사용해 시간효율이 더 좋은 알고리즘을 만들 수.. HW.2.3 트리미노 퍼즐 처음 문제를 봤을 때 2차원 배열에 재귀로 패턴을 찍어낸다는 점에서 백준 별찍기 문제가 떠올랐다. 그 문제 역시실버 1난이도의 문제였음에도 재귀 동작의 복잡성 떄문에 제대로 이해하기 어려웠다. 풀이에 앞서 먼저 문제를 분석해봤다. 앞서 말했듯이 이 문제는 재귀함수를 통해 풀이한다. 기본 동작은 다음과 같다. 1. 이미 채워져 있는 점의 위치를 고려해 트리미노 하나를 놓는다. 2. 재귀의 depth를 검사한다. 3. 2번 step이 참이라면 1, 2, 3, 4분면을 분할정복한다. 1. 트리미노 하나를 놓을 수 있는 범위는 2x2이다. 이 2x2의 공간을 4분면의 축소라고 생각해보자. 채워져 있는 점 역시 2x2의 공간 안에 축소 시켜 표현할 때, 채워져 있는 점은 어디에 위치 하는지를 구해야한다. 그리고 .. 기수변환 알고리즘 #include using namespace std; char dchar[] = "0123456789ABCDEFGHIJKSLMNOPQRSTUVWXYZ"; string ans; int card_conv(int n, int dn) { int cnt = 0; while(n) { ans[cnt++] = dchar[n % dn]; n /= dn; } return cnt; } int main(void) { puts("10진수를 기수변환 합니다."); int n; int dn; coutn; coutdn; int cnt = card_conv(n, dn); cout 백준 1931번: 회의실배정 C++ Code 처음 풀 당시 이해하기 난해했던 문제였다. 지금 돌이켜 생각해보면 왜그리 어려워했나 싶다. 먼저 어느 지점을 선택할지가 문제인데, 처음 접근 했을 때에는 물론 회의 시작 시간을 중심으로 생각했다. 회의가 언제 종료될지 알 수 없으니 반대로 종료시점을 기준으로 시작 시간이 늦은 값을 선택한 다음에 그리디로 해결할 수 있다. 백준 11047: 동전 0 C++ Code 그리디 알고리즘의 대표적인 예로 자주 등장하는 문제 형태이다. 처음 문제를 분석할 때 (입력: 3 50000 10 25000 40000)에 대한 해답을 찾지 못해서 한동안 코딩을 하지 못했다. 이제보니 문제의 조건에 하나의 단위와 다음 단위는 배수관계에 있다고 적혀 있었다,, 그래서 그냥 그리디로 풀면 된다. 왜 실버1 티어 문제인지 모르겠다. 백준 14888번: 연산자 끼워넣기 C++ Code 숫자는 그대로 가만히 있고 연산자를 삽입하는 모든 경우의 수를 단순 탐색하는 문제이다. 다만 return과정에서 어떻게 역연산을 할까 고민했다. 변수 ans를 재귀의 인자로 계속 전달하며 임의 레벨에서의 ans값을 유지하여 해결했다. 백준 2508번: 스도쿠 C++ Code solved.ac 기준으로는 n-queen문제 보다 난이도가 높지만 풀기에는 더 쉬웠다. 처음 풀 때 가장 어려웠던 부분은 박스 단위의 체킹 방식이였다. 이 부분은 다른 분의 코드를 참고 해서 풀었었고 나머지 부분은 그렇게 어렵지 않았다. 다만 체킹 하는 부분이 까다로워 실수를 찾느라 시간이 다소 오래 걸렸다. 박스 단위가 n인 경우에는 (y/n)*n + (x/n)로 할 수 있다. 그리고 한 가지 경우의 수만 출력하는 경우 재귀 안에서 처리하기 힘들 수 있다. 이 때 그냥 출력하고 exit(0)으로 종료하는 방법도 있다. 백준 9663번: N-Queen C++ Code 백트레킹의 중심 아이디어는 재귀의 깊이를 명시적으로 설정한다는 것에 있다. 다만 n-queen문제와 같이 응용된 문제의 경우에는 무엇을 깊이로 할지 설정 해야하는 어려움이 있다. 물론 n-queen 문제의 풀이방식에는 여러가지가 있겠지만은 백트레킹으로 풀었다. 퀸을 두면서 check해야 되는 배열은 4가지가 있다. 종류로는 행, 열, 왼쪽 위 대각선, 오른쪽 위 대각선이 있다. 이때 재귀의 깊이로 행 check를 하고, for반복문을 돌리면서 나머지 열, 왼쪽 위 대각선, 오른쪽 위 대각선에 대한 check를 수행했다. 나머지 수행은 기본 백트레킹 문제와 동일하기 때문에 생략하겠다. 이전 1 2 3 4 다음
