YANGORITHM

문제 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가 주어졌을 때, 가장 긴 ..

문제 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 풀이 수열 D의 숫자들이 반복되는 시작점을 N 이라고 했을 때 반복되는 부분을 제외한 나머지 부분의 개수는 N - 1 개가 된다. 그리고 숫자의 반복이 어디서부터 시작되는지 쉽게 알 수 있도록 그래프를 이용해 수열의 수들을 방문한 점과 방문하지 않은 점으로 구분한다. 결국 그래프에서 사이클을 제외한 길이를 구하는 문제가 된다. 1. A에 해당하는 노드를 방문한다. 방문 순서를 증가한다. 2. A = next(A)를 방문하지 않았다면 방문한다. 방문 순서를 증가한다. 3. 2를 만족한다면 계속 반복한다...

문제 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 풀이 유클리드 호제법을 사용하면 최대 공약수를 쉽게 구할 수 있다. gcd(a, b) 를 a와 b의 최대 공약수라고 하고 a % b = r 이라고 할 때, gcd(a, b) = gcd(b, r) 이다. r이 0 일때 b가 최대 공약수다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 P 배열에서 i 번째 있는 사람은 1번부터 i - 1번째 사람까지 다 더한 값이 된다. 따라서 i 번째 있는 사람의 값이 최소가 되기 위해서는 1번 부터 i-1 번 까지 최솟값으로 이루어지면 된다. 그러므로 P 배열을 내림차순으로 정렬을 하고 P 배열의 값을 더해주면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..