전체 글

- DFS란, 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동하는 방법이다. - 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드로 돌아가서, 다시 깊이우선 탐색을 반복 - 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법 https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif# stack 또는 recursive(재귀 함수)로 구현. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리..

너비 우선 탐색(BFS, Breadth-First Search) - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 - 큐를 사용하여 구현됨 A 노드(시작 노드)를 방문한다. (방문한 노드 체크) - 큐에 방문된 노드를 삽입(enqueue)한다. - 초기 상태의 큐에는 시작 노드만이 저장 (초기 큐에서는 시작 노드만 있음) - 즉, A 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다. - 큐에서 꺼낸 노드를 방문한다. (큐에서 값을 빼서 탐색 시작) - 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다. - 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue). - 큐에..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 이 문제는 분할 정복을 사용하는 문제이다. 알고리즘은 다음과 같다. 1. 입력으로 배열의 크기와 찾고자하는 좌표를 받는다. 2. 배열의 크기를 통해 2의 N승을 size로 사용하고, 0, 0을 현재 좌표로 설정한다. 3. 현재 좌표가 찾고자하는 좌표이면 counter를 출력한다. 4. 만약 현재 좌표와 size를 더한 값이 찾고자 하는 좌표보다 크고, 현재 좌표가 찾고자 하는 좌표보다 작..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 배열을 생성하고 DFS와 BFS를 사용해서 해결해야한다. DFS를 한국어로 번역하면 깊이 우선 탐색이며, 이는 그래프 탐색 방법 중 하나이다. 또한 BFS는 너비 우선 탐색이다. 문제 풀이 방식은 다음과 같다. 1. 2차원 배열인 밭에 아무 것도 없게 초기화 한다. 2. 입력에 따라 배추를 심는다. 3. 2차원 배열을 순회하며 밭에 배추가 있고, 방문하지 않았던 좌표이면 DFS나 BFS를 진행한다...

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 처음 문제를 해결할 때는 주어진 함수를 그대로 사용하고, map을 사용하여 0일 때와 1일 때 value를 증가시키는 방식을 사용했다. 하지만 이 방식은 시간 초과 문제로 해결할 수 없었다. 이유를 생각해보니 C++에서 함수 호출은 시간이 오래 걸리는 문제가 있었고 이를 해결하기 위해서는 문제에서 규칙을 찾아야 하는 것을 알게 되었다. 문제를 보면 40까지의 수로 한정되어 있으며 이는 반복문으로 40까지의 수를 배열로 초기화하면 된다. 또한 0과 1, 2, 3을 보면 또다른 규칙을 가지고 있다..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 이 문제는 queue를 이용하여 해결할 수 있었다. queue에 N까지의 숫자를 1부터 삽입하여 queue의 front는 1 back은 N으로 한다. 이후 queue가 비어있지 않을 때 까지 반복을 수행한다. 이때 queue에서 K 만큼 앞에 있는 것을 뒤에 빼고 넣는 과정을 반복한다. 반복을 빠져 나오면 queue의 front에 있는 숫자를 출력하면 K 번째 숫자가 된다. #include #include using namespace std; int main(){ int N, K;..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이 문제는 배열에 값을 삽입하고 정렬하면 해결할 수 있다. 이때 배열의 요소에 좌표를 삽입해야한다. 이를 위해 Point라는 class를 선언하여 배열의 요소로 사용하였다. x 좌표가 같으면 y 좌표를 기준으로 내림차순으로 정렬하고, x 좌표가 다르면 x 좌표를 기준으로 내림차순으로 정렬한다. #include #include #include u..

https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이 문제는 위키 백과의 이항 계수 공식을 참고 하였다. 공식은 아래 링크와 같다. https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98 이항 계수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 이항 계수의 표를 파스칼의 삼각형이라고 한다. 조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며 ko.wiki..