컴퓨터 공학 기초
-
Merge Sort (병합 정렬)컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 10. 27. 03:19
병합 정렬이란 ? 병합 정렬 (Merge Sort) 은 정렬 알고리즘 중 하나로 분할 정복 알고리즘을 사용한다. 즉 문제를 작은 2개의 문제로 분리하여 분리 된 각각의 작은 문제를 해결하여 해결한 결과를 가지고 원래의 문제를 해결하는 방식이다. 보통의 분할 정복 방법은 순환 호출 (재귀 함수)를 이용하여 구연하게 된다. 병합 정렬 과정 병합 정렬은 다음과 같은 과정으로 수행 된다. 입력 받은 List를 2개의 List로 나눈다. 이때 나누는 횟수는 나누어진 List가 더이상 나누어 질 수 없을때 까지 반복한다. 더 이상 나누어 질 수 없게 된 경우 2개의 List의 각 요소를 비교하여 (큰값, 작은값) 을 새로운 리스트에 옮긴다. 만약 위의 과정에서 2개의 List 중 하나라도 요소가 모두 옮겨져 요소가..
-
백준 2206 (벽 부수고 이동하기)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 23:32
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 해당 문제는 N by M 크기의 격자판이 주어지고 해당 격자판에서 N , M의 위치까지 최단거리를 찾는 문제이다. 이때 이동시 지켜야할 규칙이 존재한다. 규칙은 다음과 같다. 맵 밖으로 벗어날 수 없다. 맵에는 벽이 존재하며 벽 1개 까지는 뚫고 갈 수 있다. 이동 방향은 위, 아래, 좌, 우측으로 이동이 가능하다. 여기서 핵심은 벽을 최대 1개까지 뚫고 가면서 이동할..
-
백준 1261 (알고스팟)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 19:15
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해당 문제는 M * N 크기의 미로가 주어지며 (벽은 1 , 빈 공간 0) 해당 미로의 1 by 1 의 위치에서 N M 의 위치 까지 이동한다고 했을 때 가장 적은 수의 벽을 깨고 갈 수 있는 경우에 깬 벽의 횟수를 구하는 문제이다. 일반적인 Queue를 사용한 BFS탐색을 이용할 경우 결국 모든 경우를 모두 순회 해야 함으로 Queue 메모리 초과가 발생한다. 따라서 Deq..
-
백준 13549 (숨바꼭질 3)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 18:27
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 해당 문제는 수빈이의 위치와 동생의 위치가 주어질 때 수빈이가 동생을 찾을 수 있는 가장 빠른 경우의 시간을 찾는 문제이다. 이때 수빈이의 이동할 수 있는 경우는 다음과 같다. 수빈이는 1초 뒤에 +1, -1 번의 위치로 이동할 수 있다 수빈이는 0초 뒤에 현재위치 * 2 의 위치로 이동할 수 있다. 위의 조건대로 움직인 좌표를 Queue 에넣고 BFS를 사..
-
백준 2178 (미로 탐색)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 17:24
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N by M크기의 미로가 주어지며 시작점이 1 by 1 의 위치일 때 N by M 의 위치에 도달하기 까지 걸리는 최소 이동 횟수를 구하는 문제이다. #include #include #include using namespace std; struct Node{ int y, x; int cnt; }; int n, m; int checkY[4] = { 0, 0, 1, -1 }; int checkX[4] = { 1, -1, 0, 0 }..
-
백준 4963 (섬의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 17:07
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net M by N 크기의 격자판이 주어지며 이 격자판 안에는 육지와 바다가 있다. 육지는 상하 좌우 대각선 방향으로 이어질 수 있으며 이렇게 이어진 육지를 하나의 섬으로 본다. 이때 섬의 개수를 구하는 문제이다. 풀이 : BFS를 이용한 탐색 #include #include #include #include #include #include using namespace std; struct Node{ int y,..
-
백준 2667 (단지번호붙이기)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 15:58
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 해당 문제는 0과 1로 이루어진 격자판이 주어지며 해당 격자판의 1은 집을 의미하고 0은 빈 집을 의미한다. 이때 집들의 모임인 단지를 정하고 단지의 개수와 각 단지마다 포함 된 집의 개수를 오름차순으로 출력하는 문제이다. 단지는 상하좌우로 인접한 집들의 집합이다. 풀이 : 2 중 for를 사용하여 격자판을 모두탐색 하며 만약 처음 방문하는 집일 경우에 BFS를 통한 상하좌우 방향의 집 탐색을 진..
-
백준 11724 (연결 요소의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:30
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 해당 문제는 N개의 정점과 M개의 간선들이 주어질 때 하나로 연결 된 요소들의 총 개수를 구하는 문제이다. 풀이 : for 문을 사용하여 N개의 정점을 BFS를 사용하여 탐색하며 탐색한 정점은 check 해주며 Check 되지 않은 정점이 있을 경우 해당 정점에서 다시 BFS를 사용하여 정점을 탐색하는 과정을 반복하면서 check되..