1. 문제 현재 위치에서 N미터 떨어진 곳까지 물고기가 얼마나 있는지 주어진다. 정확히 M마리의 물고리를 잡고자 할 때 그물은 딱 한번 내리고 딱 한번 올릴 수 있다. 이때 정확히 M마리를 잡을 수 있는 경우의 수를 구하라. 예를 들어 5 3 7 2 1의 물고리가 존재할 때, 10마리의 물고리를 잡을 수 있는 경우의 수는 위와 같이 2가지가 존재한다. 가장 밑의 경우 떨어져있으므로 불가능한다. 2. 입력 3. 출력 가능한 경우의 수를 출력한다. 4. 알고리즘 : 투포인터 그물을 내리는 위치, 그물을 올리는 위치를 가리키는 두개의 포인터를 이용해서 구할 수 있다. 왼쪽에서 시작하기 때문에 물고기가 너무 적다면 그물을 올리는 위치를 오른쪽으로 이동하고, 물고기가 너무 많다면 그물을 내리는 위치를 오른쪽으로 ..

1. 문제 수열에 있는 연속된 원소들의 합을 이용하여 새로운 수열을 만들 수 있다. 예를 들어 1, 2, 3, 4, 5와 같은 수열이 있다고 했을 때, 1, 2를 합쳐서 3, 3, 4, 5 또는 2, 3, 4를 합쳐서 1, 9, 5를 만들 수 있다. 모든 원소를 합쳐서 15 등의 수열을 만들 수도 있다. 두 개의 수열이 주어질 때, 두 수열을 같은 수열로 만들 수 있을 때, 만들수 있는 가장 긴 같은 수열의 길이를 구하는 것이다. 2. 입력 3. 출력 두 수열을 똑같은 수열로 만들 수 있다면 그 수열의 최대 길이를, 만들 수 없다면 -1을 출력한다. 4. 알고리즘 : 그리디, 투포인터 첫번째로 두 수열의 총합이 다르다면 절대로 같은 수열로 만들 수 없다. 해당 확인이 끝났다면 투 포인터를 이용해서 원소들..

1. 문제 강의 상부와 하부를 연결하는 다리를 건설해야한다. 다리는 여러 지점으로 나눠져있고, 같은 번호의 지점끼리만 연결할 수 있다. 다리를 건설하기 위해 미리 N개의 지점을 골라두었다. 강 한쪽은 1번부터 N번까지 순서대로 지점에 번호를 매겼지만 반대쪽은 무작위로 매겨져 있다. 같은 번호의 두 지점끼리만 다리로 연결할 수 있다. 두 개의 다리는 겹칠 수(교차될 수) 없다. 주민들의 편의를 위해 다리는 최대한 많은 개수를 건설하고자 한다. 2. 입력 첫 번째 줄에는 지점의 개수 N이 주어진다. (5

1. 문제 지구를 호시탐탐노리는 아주 질나쁜 외계인들을 다 무찔러야한다. 그러기 위해서는 외계인들의 행성인 A행성의 모든 기계들을 파괴시켜야한다. A 행성에 있는 모든 기계의 위치는 N x N크기의 격자판 상에 나타낼 수 있다. 격자판 위의 모든 기계가 같은 종류의 기계라면 단 한 번의 공격으로 모든 기계를 파괴할 수 있다. 만약 격자판 위의 기계들 중 하나라도 다른 종류의 기계가 있다면, 4개의 구획으로 나누어 다시 기계를 확인한다. 모든 기계가 파괴될 때까지 2-3단계의 작업을 반복한다. 2. 입력 첫번째 줄에는 격자판 크기 N이 주어진다. 이때 N은 항상 2^k(2의 지수승) 형태이다. 두번째 줄부터 N x N 행렬에 기계번호 3이하의 자연수가 주어진다. 3. 출력 기계의 최소 공격횟수 4. 알고리..

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다. 하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n -1번의 이동으로 원판을 모두 옮길 수 있다. 이 규칙들을 이용하여 63(64)개의 원판을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가..

1. 문제 - 난이도 ★ 12척의 배가 주어졌을 때, 대장선을 제외한 11척을 이용해 최적의 진형을 찾는 것이다. 2. 입력 11 * 11의 행렬이 주어지며, aij는 i번째 배가 진형의 j번째 위치했을 떄의 전투력을 뜻한다. 3. 출력 첫번째 줄에 최적의 진형을 이루었을 때의 합을 구한다. 두번째 줄에는 아군의 진형을 첫번째부터 순서대로 출력한다. 최적의 진형이 여러개인 경우 사전순으로 앞선 진형을 출력한다. 4. 알고리즘 문제는 11척의 배를 순서대로 나열할 때, 그 능력치가 최대가 되는 순서를 찾는 문제이다. 가장 간단한 방법은 역시 완전탐색이다. 1번배가 1번자리에, 2번배가 2번자리에, ... , 11번 배가 11번자리에 들어가는 진형부터, 1번배가 11번자리에 2번배가 10번자리에, ..., ..

1. 문제 - 난이도 ★ 거리가 가장 먼 친구를 찾아보자. 2. 입력 첫번째 줄에는 사람 수 N이 주어진다. 두번째 줄부터 N + 1번째 줄까지 i번째 사람의 위치 정보가 좌표로 주어진다. 3. 출력 가장 애틋한 친구의 번호를 구분하여 낮은 번호부터 출력한다. 4. 알고리즘 이중 반복문을 이용하여 모든 친구들 사이의 거리를 비교하여 가장 거리가 먼 친구를 출력한다. 5. 코드 # 입력 처리 N = int(input()) friends = [list(map(int, input().split())) for _ in range(N)] # 거리 구하는 함수 def dist(x, y): return (x[0] - y[0])**2 + (x[1]-y[1])**2 max_list = [] # 가장 거리가 먼 친구 저장..

1. 문제 - 난이도 ★★ 팀원들의 능력치가 주어졌을 때 홍현이의 능력을 포함한 그 합이 S가 되게하는 환상의 조합을 구하라. 2. 입력 첫번째 줄에는 사람 수 N과 팀원들의 능력합 S가 주어진다 두번째 줄부터 N명의 사람들의 능력치가 주어진다. 첫번째로 주어지는 능력은 홍현이의 능력이다. 3. 출력 최고의 팀을 만들 수 있는 경우의 수 출력, 팀원은 최소 1명 이상이어야 한다. 즉, 홍현이 혼자 팀을 구성할 수 있다.. 4. 알고리즘 : 완전 탐색 홍현이를 포함하는 부분집합의 합이 S가 되는 경우의 수를 찾는 문제이다. 집합 A의 크기가 n일 때 공집합을 포함한 부분집합의 개수는 2^n개이다. 따라서 문제는 O(2^N)시간안에 풀 수 있다. 완전 탐색은 두가지 방법이 있다. 1. 재귀 함수 2. 비트 ..

출처 : 한국 코드페어 비타알고 시즌2 투 포인터(two pointer) 1. Two Pointer 정렬된 배열에서 두 개의 인덱스를 사용하여 원하는 값을 찾는 기법 투 포인터는 정렬된 배열에서 2개의 포인터(인덱스)를 이용하여 두 포인터가 가리키는 값과 찾고자 하는 값(key값)을 비교한 뒤 포인터를 조정하여 원하는 결과를 얻어내는 기법이다. 대표적인 예로 '배열 내 합이 S가 되는 순서쌍 찾기'가 있다. for(int i = 0; i < n; ++i){ for(int j = i + 1; j < n; ++j){ if(data[i] + data[j] == S) cout

1. 문제 - 난이도 ★ 해당 수가 2^k인지 판별하는 것이다. 2. 입력 10^18 이하의 자연수가 주어진다. 3. 출력 2의 거듭제곱이면 Yes, 아니면 No를 출력한다. 4. 알고리즘 먼저 바로 떠오르는 생각은 2로 계속 나누다가 나머지가 0이면 2의 거듭제곱이고 1이면 2의 거듭제곱이 아닌 수이다. 그러나 입력값을 보면 절대로 안된다는 것을 알 수 있다. 그렇다면 다른 방법으로 접근해야한다. 바로 비트연산이다. 2의 거듭제곱은 딱 한 비트만 1인 수이다. 위와 같이 2의 거듭제곱은 비트 하나만 1이다. 해당 수를 n이라고 했을 때, n & -n은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다. 따라서 2개 이상이 켜져있다면 n과 n & -n은 절대로 같을 수 없다. 그러나 2의 거듭제곱과 같이 ..