https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 알고리즘 [접근 방법] 이 문제는 dict를 사용해서 Key, value로 빠르게 접근하는 게 포인트다. 풀이 포켓몬의 수 n과 입력받을 명령어 개수 m을 map형태로 입력받는다. sys 라이브러리를 이용하여 입력을 받아야한다. (안그러면 시간초과) sys라이브러리로 입력받을 경우 개행(\n)까지 dict에 입력되므로 rstrip() 처리를 해야한다. dict에 키와 ..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 알고리즘 [접근 방법] 그냥 bfs문제이다. 코드 import sys # sys.stdin=open("input.txt", "rt") from collections import deque N, M, R = map(int, sys.stdin.readline().split()) # graph graph = [[] for _ i..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 알고리즘 [접근 방법] 기본적인 DFS 문제이다. 그냥 cnt변수만 추가해서 카운팅해주면 된다. 또는, 리스트를 하나 만들어서 append해주고 길이를 출력하면 된다. 풀이 흔히 dfs와 bfs 문제를 풀 때, 트리 방식으로 생각해서 문제를 해결하는 경우가 많다. 이번 문제에서는 딱히, 상위 노드와 하위 노드가 정해진 것이 아니기 때문에 그래프 방식으로 생각하면 된다. 1번과 연결되어있는 컴퓨터만 찾으..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 [접근 방법] dfs는 깊이 우선 탐색, 즉 말 그대로 깊이를 우선적으로 탐색해주는 것이고, bfs는 너비 우선 탐색, 즉 너비를 우선적으로 탐색해주는 것이다. 문제 자체는 bfs의기본 구조를 벗어나지 않아 쉽게 풀 수 있지만 주의해야할 점은 dfs와 bfs를 각자 실행해야하므로 visited 를 초기화 해주거나, 두개 만들거나, dfs는 visite..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 알고리즘 [접근 방법] 이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다. 배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 쪼갤 수 있는 경우와 ..

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 [접근 방법] 문제 예제들을 그대로 적용해보면 이렇다. 첫 번째 예제는 아래와 같다. (배열로 표현함) 여기서 연속된 수를 선택하여 뽑아내면 다음과 같다. 두 번째 예제를 보자. 두 번째 예제를 보면 index5 에 -4 라는 음수가 들어있지만 이를 포함하여 index7까지 연속으로 택하여 합한 것이 최댓값임을 알 수 있다. 즉, 포인트는 음수 양수 상관없이 '연속적으로 선택한 수의 합'이 최댓값이 되는 수를 찾..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 [접근 방법] ko.wikipedia.org/wiki/최장_공통_부분_수열 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에 ko.wikipe..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 알고리즘 [접근 방법] 먼저 문제에서는 서로 교차되지 않도록 하기 위해 철거되어야 할 전선의 최소 개수를 구하는 것이다. 하지만 그렇게 구하기에는 교차 여부를 확인해야 하기에 불편하다. 그렇다면 역으로 생각해보자. 철거되어야 할 전선의 최소 개수라 하면, 거꾸로 전체 전선의 개수에서 최대한 겹치지 않게 설치 가능한 개수를 구하여 빼면, 즉 (전체 전선 개수 - 설치 가능 개수) = 철거 개수 가된다. 한..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 알고리즘 [접근 방법] 문제 예제를 한 번 보도록하자. 일단 이전 포스팅에서는 LIS(최장 증가 부분수열)에 대해 알아보았다. 이번에는 개념 하나가 더 추가 되는데, 증가가 있다면 감소도 있듯 이러한 부분 감소 수열을 LDS(최장 감소 부분수열)이라 한다. 먼저 바이토닉(Bitonic)에 대해 정의를 알아보자. 바이토닉의 경우 특정 값을 기준으로 왼쪽 부분은 오름차순, 오른쪽 부분은 내림차순인 수열 또는 그러한 부분 순환이동을 말..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 [접근 방법] 보통 이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 말 그래도 주어진 수열에서 오름차 순으로 구성 가능한 원소들을 선택하여 최대 길이를 찾아내는 것이다. 잘 활용하면 O(N log N)의 시간 복잡도를 갖는다. 예제를 보자면 위 수열은 {10, 20, 10, 30, 20, 50} 이다. 이..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 알고리즘 [접근 방법] https://linerate.tistory.com/31 [2579번] 계단 오르기 JAVA☕ www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/pr..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 [접근 방법] 문제 설명을 보면 일단 자릿수가 100, 즉 100째자리 수까지 주어지니 기본 형식은 long타입으로 해준다고 가정하고 설명하겠다. 또한 문제에서 가장 중요한 포인트는 '인접한 모든 자릿수가 1씩 차이가 난다'는 것이 포인트. 여기서 유의해야 할 점이 있는데 다음 두 가지를 조심해야 한다. 1) N번째 자릿수의 자릿값이 0인 경우 : 다음 자릿수의 자릿값은 1밖에 올 수 없다. 2) N번째 자릿수의 자릿값이 9인 경우 : 다음 자릿수의 자릿값은 8밖에 올 수 없다. 즉, 10 다음에 붙을 수 있는 수는..

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 알고리즘 [접근 방법] 이 문제는 크게 3가지 조건이 필요하다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다 이 조건을 토대로 1로 만들기 위한 최소 연산 횟수를 찾아내야 한다. 여기서 주의할 점은 무조건 "큰수로 나눠서는 안된다" Integer[] dp; // 메모이제이션 할 배열 static int recur(int N) { // 탐색하지 않았던 N일 경우 if (dp[N] == null) { // 6으로 나눠질 경우 if (N % 6 == 0) { } // 3으로만..

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 알고리즘 [접근 방법] 이번 문제는 테스트 케이스가 여러개이므로 각 케이스마다 동적계획법을 사용해야 한다. 예를들어 Func()함수가 있다고 가정한다면, 이 함수는 Func(N) = Func(N-1) + Func(N-2)를 만족하는 피보나치 수를 구하는 기능을 담당한다. 이 때 N=4에 대하여 값을 구하고자 하면 아래와 같은 과정을 거칠 것이다. Func(4) = Func(3) + Func(2) Func(4) = (..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 알고리즘 [접근 방법] static int w(int a, int b, int c) { if(a 20) { return w(20, 20, 20); } if(a < b && b < c) { return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c); } return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, ..

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 [접근 방법] 풀이조건을 설명하자면 다음과 같다. 일단 각각의 집을 색칠해야하고, 색의 종류는 3가지가 주어진다 ( 빨강, 초록, 파랑 ) 그리고 각 집마다 해당 색을 칠하는 비용이 주어진다. 그리고 전체 집을 색칠할 때 최소 비용을 구하는 것이다. 이때 중요한 점이라면 인접한 집끼리는 색이 겹치면 안된다는 점이다. 예를들어 3번 집에 초록색을 칠한다면, 2번집과 4번집은 초록색을..

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 [접근 방법] 이 문제는 크게 3가지 조건을 만족해야 한다. 계단을 오를 때 한계단 또는 두 계단을 오를 수 있다. 연속된 3개의 계단을 밟을면 안된다. (한계단씩 오를 떄 최대 연속 2번만 한계단씩 오를 수 있다) 마지막 계단은 '반드시' 밟아야 한다. 기본적인 알고리즘은 아래와 같다. static int find(int N) { if(dp[N] == null) { dp[N] = Math.max(find(N - ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 알고리즘 [접근 방법] 먼저, 삼각형을 입력받을 2차원 배열 arr와 경로 합을 가질 DP배열 이렇게 두개가 있어야 한다. 그리고 삼각형의 밑변, 즉 마지막 값은 DP배열에도 똑같이 저장해준다. 맨 위에서부터 탐색을 해보면, 아래의 양쪽 값 중 최대값을 찾아야한다. 하지만, 위 그림에서 보듯이 위에서 두 번째 줄의 값 또한 비어있다. 그렇기 때문에 재귀호출을 통하여 다시 그 아래의 양쪽 값중 최대값을 찾는다. 이런식으로 반복하다보면 양쪽에 값이 있는 경우를 만나게 된다..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 알고리즘 [접근 방법] 이 문제는 만약 N=1 부터 경우의 수를 쭉 나열해보았다면 매우 쉽게 풀 수 있다. N=6까지 가능한 경우의 수를 나열해보았다. 개수가 피보나치 수의 수열처럼 증가하고 있음을 알 수 있다. 즉, N=3일 때는 N=1, N=2일 때의 개수의 합이다. 이는 피보나치 점화식과 일치함을 알 수 있다. 풀이 1 2 3 4 5 6 7 8 9 10 11 12 static int[] dp = ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이법 일단 이번 문제는 피보나치 수를 구하는 것이 아니라 피보나치 수에서 0과 1이 호출되는 횟수를 구하는 것이다. 코드로는 N이 최대 40까지 주어지고, 각 N에 0과 1이 호출된 횟수를 담아야 하므로 2차원 배열이 필요하다. (또한 null 체크를하기 위해서 int[][] 가 아닌 Integer[][]로 사용한다.) DP라는 배열을 선언하고, 피보나치 함수는 각 N에 대한 0과 1의 값을 DP에 저장하면서 재귀호출을 진행한다. N에 대한 0과 1은 다음과 같은 규칙을 따른다. 1. N에 ..