YANGORITHM

문제 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는 기본적으로 큰 값의 우선순위가 높으므로 따로 비교 연산자를 지정..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 풀이 연속해서 세 개의 계단을 밟을 수 없으므로 n번째 계단에서 가능한 경우는 두 가지가 있다. 1. n-1번째 계단과 n번째 계단을 밟는 경우 2...

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n번째 숫자에서 발생하는 비교 연산은 다음과 같다. ( n - 1 번째 숫자까지의 최대값 + arr[n] ) , arr[n] 두 숫자 중 큰 값이 n번째 숫자에서의 최대값이 된다. d[n] = arr[n]을 포함하는 연속된 수열 중 최대값 이라고 하면 다음의 점화식을 구할 수 있다. d[n] = max { ( d[n-1] + arr[i] ), arr[i] } 코드 1 2 3 4 5 6 7 8 9 ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 d[k] = A[k]을 포함하는 가장 긴 바이토닉 부분수열 이라고 하면 i = 1 부터 i = k 까지 가장 긴 증가하는 부분 수열과 i = N 부터 i = k 까지 가장 긴 증가하는 부분 수열을 구해서 더하면 된다. 이때 k번째는 겹치게 되므로 -1을 해준다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 ..