참고 내용 https://blog.encrypted.gg/943 정의 재귀 : 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 핵심 수학적 귀납법으로 생각해야 함. 절차지향식으로 생각하면 머리 터짐! 수학적 귀납법 N=1이 성립한다. N=k가 성립한다면 N=k+1 역시 성립함을 증명하면 N=k가 성립함을 증명할 수 있음 알고리즘 틀 함수의 정의 : 함수의 인자로 무엇을 받을지, 함수에서 어디까지 계산하고 자신을 호출할지가 명확해야 함. 이때, 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수로 표현할 수 있음. (재귀로 할지, 반복문으로 할지 상황에 따라 메모리와 시간의 제약상황에 따라 선택할 수 있다는 뜻) base condition : 특정 입력에 대해 자기 자신을 호출하지 않고..
백준 풀이 - 재귀 연습문제 문제리뷰 계속 4n만 생각하다가 N=k+1, N=k와 연결지어야 하는걸 잊어버렸다. 한마디로 수학적 귀납법으로 접근해야하는 것을 수열로 하려다가 시간만 버렸다. 그리고 N=1은 2^0 x 2^0인데 내 맘대로 2^1 x 2^1로 생각해서 수열로 접근하려고 했던거 같다. 접근 N=2(N=k)일 때와 N=3(N=k+1)일 때 사각형을 연결짓는 것이 중요하다. 나는 4x1 + 0 / 4x2 + 0 / 4x3 + 0 의 관계는 알았는데 이를 재귀로 연결짓지 못 했다. 풀이 바킹독 풀이를 그대로 봤기 때문에 링크로 남긴다. 풀이 : https://blog.encrypted.gg/943 (재귀 어려엉..)
참고자료 https://yabmoons.tistory.com/m/657 백준 풀이 - BFS 문제리뷰 21609 상어 중학교 (골드2) 1. 가장 큰 블록 찾기 (1차 BFS) 1-1 같은 coloring 그룹화 (2차 BFS - 무지개 블록 처리 주의) 2. 가장 큰 블록 제거 3. 제거 후 중력 적용 4. 90도 반시계 회전 5. 중력 적용 피드백 구현 함수가 많은 문제 제거를 위해 정보가 많이 필요하므로 struct 처리를 해야 함 무지개 블록 처리를 위해 무지개 블록을 방문 체크하는 배열을 따로 생성해야 함 (걍 구현이 빡세요 ㅠㅠ) C++ 21609 상어 중학교 #include #include #include #include #define MAX 20 #define X first #define ..
백준 풀이 - DFS / 조합 문제리뷰 15686 치킨 배달 (골드5) 피드백 DFS로 치킨 가게의 조합을 구한 후, 각 치킨 가게에서 집까지의 거리를 구해 최솟값을 구하면 되는 문제 가장 처음 풀 때는 치킨가게까지 BFS로 구하려다가 꼬였는데 그냥 좌표로 계산하면 간단한 문제였음 이중 for문 인덱스 주의 입력값을 for문에 사용할 때 의미를 제대로 알고 사용해야 실수하지 않음 m은 남길 치킨 가게의 개수인데 치킨 가게의 총 개수로 착각해서 헤맸음 C++ 15686 치킨 배달 #include #include #include #define MAX 50 #define X first #define Y second using namespace std; struct PLACE { int x; int y; int..
참고자료 https://kimjingo.tistory.com/37 백준 풀이 - 2차원 배열의 나선형 알고리즘 문제리뷰 20057 마법사 상어와 토네이도 (골드3) 피드백 나선형 알고리즘만 잘 구현하면 되는 문제 단, 토네이도가 회전 시 모래에 적용되는 비율도 같이 회전해야 해서 비율 회전 관련된 배열이 필요하다는 것을 주의해야 함 그리고 비율에 float 자료형 적용하는거 잊지 말자.. C++ 20057 마법사 상어와 토네이도 #include #define MAX 500 #define X first #define Y second using namespace std; int dx[] = { 0, 1, 0, -1 }; int dy[] = { -1, 0, 1, 0 }; float sand[] = { 0.05..
참고자료 https://yabmoons.tistory.com/659 백준 풀이 - 2차원 배열의 나선형 알고리즘 문제리뷰 21611 마법사 상어와 블리자드 (골드1) 0. 자료구조 구성 (remap) 1. 블리자드 마법 (doBlizzard) while(3. 구슬 폭발 (exploreBall)) 2. 구슬 이동 (moveBall) 4. 맵 변화 (changeBoard) 피드백 나선형 알고리즘을 1차원 배열로 바꾸어 좌표 나선형 맵의 숫자가 되도록 자료구조를 구성하는 것이 문제를 간단하게 해결하는 핵심 처음에는 나선형 알고리즘을 그대로 적용하다가 인덱스 범위가 벗어나서 오류 고치다가 포기함 >> 뇌절 오면 빨리 런치고 다른 방법을 고민해야 함 C++ 21611 마법사 상어와 블리자드 (골드1) #inclu..
참고 내용 https://paris-in-the-rain.tistory.com/35 순열 예제 핵심 : list.push_back(num[i]) / list.pop_back(num[i]) / vis 사용해서 중복 체크 #include #include using namespace std; vector nums; vector list; int vis[4]; void print() { for (int i = 0; i < list.size(); i++) { cout
프로그래머스 풀이 문제리뷰 코딩테스트 고득점 Kit - 완전탐색 전력망을 둘로 나누기 그래프를 인접 행렬이나 인접 리스트로 구현할 줄 알고 그래프 탐색 (DFS / BFS)를 할 줄 아는지 물어보는 문제 같았다. 그래서 일단 DFS로 구현했는데 테스트케이스 2번 문제가 계속 틀려서 곰곰히 생각해보니 문제의 그래프는 undirect graph로 [1,2]나 [2,1]을 같게 처리해야 한다. List로 구현해서 해당 부분이 중복된거 같아서 Set으로 처리했더니 해결됐다. 강의 내용 vis( = ch) 변수에 끊고자 하는 노드를 1로 표시함 체크한 노드의 다른 한 쪽에 있는 노드를 DFS를 돌려 순회하여 개수를 셈 전체 개수에서 DFS를 돌릴 때 구한 개수를 이용해 두 구역의 송전탑 개수를 구함. Python..
