알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/24481 24481번: 알고리즘 수업 - 깊이 우선 탐색 3 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2번 노드이다. 2번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 4번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net DFS를 이용해 노드 깊이를 구하는 문제였습니다. 방문 순서가 아닌, 방문 깊이이기 때문에, 정점을 방문할 때마다 1씩 증가해서 넣으면 안됩니다. void dfs(int x, int cnt){ check[x] = cnt; for(int i = 0 ; i < connect[x].size(); i++){ int xx = connec..

문제 링크입니다. https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net DFS를 사용하는 문제입니다. 내림차순으로 탐색하는 것을 주의해야 했습니다. DFS를 이용해 그래프 탐색을 할 때, 노드 방문 순서를 출력하는 문제입니다. 노드를 방문할 때, 인접 정점은 내림차순으로 방문한다는 것이 중요했습니다. DFS 코드는 재귀 함수를 이용했습니다. DFS를 탐색하기 전에, 노드를 정렬..

문제 링크입니다. https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net DFS 문제입니다. 그래프 탐색 중, DFS를 이용한 문제입니다. 시작점이 주어졌을 때, 다른 정점을 몇번만에 방문하는지를 출력해야됩니다. 저는 check, Cnt 배열을 이용해, check 배열에는 방문 여부를, Cnt 배열에는 방문 순서를 저장했습니다. 탐색을 진행하기 전에, 오름차순 방문을 위해 오름차..

문제 링크입니다. https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 다익스트라 알고리즘으로도 풀 수 있겠지만 비추천합니다. 1번에서 시작해 가장 가중치가 큰 곳의 값을 구하는 문제입니다. 항상 시작은 1번이니 1번부터 시작해 DFS 탐색을 해줍니다. 재귀함수를 반복할 때마다 최대 거리를 비교하면서 탐색이 끝난 뒤에 최대 거리를 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요 #define _CRT..

문제 링크입니다. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net DFS를 사용하여 푸는 문제입니다. 임의의 점을 하나 선택한 뒤, 해당 점에서 다시 탐색을 하여 답을 구하는 문제였습니다. 1 ~ N까지의 정점이 있을 때, 가장 긴 노드 사이의 거리를 구하는 문제였습니다. 1번 점부터 N번 점까지 모든 경우를 확인하기에는 경우가 너무 많아 시간 초과가 생길 수 있습니다. 따라서 다른 방법을 통해 지름을 구해야하는데 그중 한 ..

문제 링크입니다. https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net DFS를 이용한 문제였습니다. 1번 정점에서 시작해서 가장 긴 거리에 있는 점을 찾은 뒤, 해당 점에서 되돌아오면서 길이를 재는 방법이였습니다. 해당 문제는 두번의 DFS를 사용해야하는 문제였습니다. 1~N번까지의 점 중에서 임의의 점을 하나 선택합니다. 해당 점에서 가장 거리가 먼 점을 하나 확인합니다. 이 점을 X라 하겠습니다.(저는 1번을 임의로 정했습니다...

문제 링크입니다. https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 삼성 SW 역량테스트 기출 문제입니다. 까다로운 기출문제 였습니다. 문제에서 구현할 것은 물고기의 움직임 + 상어의 움직임 입니다. 물고기가 움직일 때는 조건이 있습니다. 먹힌 물고기가 아니며, 이동한 칸이 상어가 있는 곳이 아닐 경우에만 이동할 수 있습니다. int map[5][5]; // 상어가 위치한 칸은 -1이다. info info_fish[17]; in..

문제 링크입니다. https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 삼성 SW 역량 테스트 기출문제 였습니다. 문제에서 주어진 조건대로 구현하면 풀 수 있는 문제였습니다. 구현 문제에 익숙하지 않으시다면 어려울 것 같습니다. 모든 경우를 탐색해야 함으로 DFS를 통해 확인했습니다. CCTV는 1번~5번까지 있습니다. 1번 -> 한방향 2번 -> 2방향(평행) 3번 -> 2방향(수직) 4번 -> 3방향 5번 -> 4방향 6번 -> 벽 M..

문제 링크입니다. https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 삼성 SW 역량테스트 문제였습니다. 2048 게임을 응용한 문제로, 상하좌우를 움직이는 것은 똑같지만 게임처럼 움직일 때마다 2가 생기지는 않습니다. 이때 나올 수 있는 최대 값을 구하는 문제였습니다. 먼저, 값이 더이상 변하지 않는 횟수가 몇 번인지를 찾아야합니다. 1줄에 최대 20개의 수가 주어질 수 있으니 한번 가정을 해보겠습니다. Case 1,..

문제 링크입니다! https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net DFS를 이용한 선택 + BFS를 이용한 탐색이 합쳐진 문제였습니다(연구소 문제의 심화문제 느낌이였습니다.) DFS에서 주의할 점이 Green, Red를 선택해야 하는데 겹치면 안된다는 것이였습니다. 따라서 저는 Green -> Red 로 선택해줬습니다. 예를들어 1, 2, 3, 4칸에 배양액을 놓을 수 있고, 초록색, ..

문제 링크입니다 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 1과 같이 DFS를 통해서 선택, BFS를 통해서 탐색을 하는 문제였습니다. 문제 조건과 출력예시는 위 링크를 참고해주세요! 문제 접근 방법 1. 입력과 같이 바이러스의 위치와 빈칸의 갯수를 저장한다. 2. 빈 칸의 갯수가 1개 이상일 때, 바이러스를 M개 만큼 선택해준다. 3. 바이러스가 M개 선택되었다면, BFS 탐색을 통해서 바이러스를 확산시킨다. 4. 빈 칸이 없다면 T를, ..

문제 링크입니다 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net DFS를 통해서 벽을 선택한후, BFS를 통해서 탐색하는 문제였습니다. (문제는 너무 길어서 생략하겠습니다) 문제 접근 방법 1. 입력을 받음과 동시에 빈칸을 저장한다. 2. 빈칸 중에서 3개를 순차적으로 고른다. 3. 고른 빈칸에 벽을 세운뒤 BFS 탐색을 통해서 바이러스를 퍼트린다. 4. 안전 영역을 구한다. 5. 벽이 전부 선택될 때까지 반복한다. 문제 접근 방법 - 1번 for (int..