YANGORITHM

문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 풀이 먼저 섬을 번호 순으로 그룹화를 시킨다. 그리고 각 번호가 다른 그룹사이에서의 최소 칸 수를 구하면 되는 문제이다. 섬을 ..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 bfs 탐색을 (1,1)에서 시작해서 (N,M)에 도착했을 때 지나가는 level의 수가 최소 횟수가 된다. result = (1,1)에서 (N,M)까지 이동할 때 지나야하는 최소 칸 수 라고 할 때, bfs 탐색을 진행하면서 현재 level에 해당되는 좌표들을 모두 방문한 후에 result 값을 증가시켜주면 된다. 현재 level에 해당하는 좌표를 모두 방문하려면, bfs 탐색에서 현재 큐에 저장되어 있는 데이터 수..

문제 https://www.acmicpc.net/problem/2011 2011번: 암호코드 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", " www.acmicpc.net 풀이 N자리의 암호가 주어질 때 N번째에 올 수 있는 암호는 1부터 9까지이고, N-1과 N번째에 10부터 26까지 올 수 있다. ..

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 풀이 DFS 탐색의 개념을 이용하는 문제이다. 값이 1인 좌표에서 상하좌우, 대각선으로 모두 검사해서 1인 좌표가 있다면, 그 좌표에..

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 풀이 DFS의 개념을 이용하면 간단하게 풀 수 있는 문제이다. 2차원 배열을 이용해서 그래프를 만든 후 2차원 배열에서 값이 1인 지점을 기준으로 DFS 탐색..

문제 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 소인수분해는 소수들의 곱을 이용해서 정수를 나타내는 방법이다. https://ko.wikipedia.org/wiki/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4 소인수분해 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org N 보다 작은 소수들을 먼저 구하려고 했지만 그럴 필요가 없는 문제이다. 소수가 아닌 수들은 결국 앞에 나온 소수들의 곱으로 이루어지게 되므로, N을 2부터 시작해서 나누었을 때 나머지가 없으면 그 수는 N을 이루는 소수가 된다. 예를..

문제 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 www.acmicpc.net 풀이 입력 받은 B 진법을 10진법으로 바꾸는 문제이다. 주어진 N에 대해서 1의 자리 부터 차례대로 10진수로 변환을 한다. i의 자리 수가 0~9일 때와 알파벳일때 구분을 해서 변환을 해주면 된다. 변환을 한 숫자를 n이라 할 때, n * B^(i - 1) 이 i의 자리 수가 된다. 따라서 이 숫자들을..

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 벨만-포드 알고리즘을 이용하는 문제이다. 벨만 포드 알고리즘은 가중치에 음수가 있는 경우에서 최단경로를 찾고 싶을 때 사용하는 알고리즘이다. 모든 간선에 대해서 정점의 개수-1 (N-1) 번의 relaxation 과정을 거치면 시작 정점에서부터 최단 경로를 구할 수 있게 된다. 벨만포드는 음의 사이클을 가지지 않는 그래프에서는..

문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 풀이 모든 탐색의 끝은 사이클을 이루게 되므로 마지막에 방문한 정점을 기준으로 사이클을 검사하면 된다. 그리고 사이클을 계속 순..

문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. www.acmicpc.net 풀이 최대 힙을 만드는 문제이다. stl의 우선순위 큐를 이용한다. 우선순위 큐를 이용하려면 #include를 해준다. 우선순위 큐는 priority_queue로 정의한다. priority_queue는 기본적으로 큰 값의 우선순위가 높으므로 따로 비교 연산자를 지정..