https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 분석 크기가 n인 집합을 v1 그리고 크기가 m인 집합을 v2라고 하였을 때, v1의 원소 중 v2보다 작은 것이 몇개인지 카운트 하는 문제이다. 다양한 풀이 방법이 있지만, 완전 탐색으로 풀었다. 코드 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..
Koala - 7기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/21608 [문제 해석] 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 위 3가지 조건을 만족하는 자리배치를 하고, 좋아하는 학생 수에 따른 만족도 계산하여 출력하도록 한다. N = int(input()) st = [] for _ in range(N**2) : st.append(list(map(int, input().split()))) sit = [[0]*N..
https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 문제분석 분류 투포인터 슬라이딩 윈도우 문제설명 횡단보도의 개수 N개 입력 고장난 신호등의 개수 B개 그리고 좌표 입력 탐색하고자 하는 길이 K 입력 배열의 길이가 가변적일 때: 투 포인터, 배열의 길이가 고정적일 때: 슬라이딩 윈도우 슬라이딩 윈도우 -> O(N)의 속도로 탐색 입력 10 6 5 2 10 1 5 9 출력 1 코드 #include #include using namespace std; int main() { int N, K, B; ci..
https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 코드 ##17135 캐슬_디펜스 import copy from itertools import combinations as cm n, m, d = map(int, input().split()) enemies = [] for _ in range(n): row = list(map(int, input().split())) enemies.append(row) distance = -1 if d
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 분석 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1. 두 ..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제분석 분류 구현, 브루트포스 알고리즘, 백트래킹 문제설명 크기가 NxN인 도시가 있고, 도시는 1x1 크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타나고, r과 c는 1부터 시작한다. 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리 → (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r..
https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 문제 정리 1. 가장 물고기가 작게 들어있는 어항에 물고기 한마리를 넣는다. (최소값이 여러개면 모든 최솟값인 어항에 한마리씩 넣는다) 2. 다음과 같은 순서로 어항을 쌓는다 * 1. 초기: 제일 왼쪽 어항을 그다음 어항위에 올린다. * 2. 이후: 높이가 2이상인 모든 열을 시계방향으로 회전시킨 후 높이가 1인 열 위에 쌓는다 * 3.밑의 그림과 같이 어항이 공중에 뜨기 전까지 반복한다. 3. ..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N >n>>m; int a[n+1]; for(int i=1; i>a..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 분석 어떤 자연수 N이 주어졌을 때 N을 나타낼 수 있는 소수의 연속합의 개수를 구하는 문제입니다. 에라토스테네스의 체를 이용하여 어떤 자연수 이하의 모든 소수를 구할 수 있고, 소수들이 자연스레 정렬되어 있기 때문에 투 포인터로 쉽게 문제를 해결할 수 있습니다. 코드 #include #include using namespace std; vector p(4000001, true); vector prime; int N, s=0, e=0, sum=0, ans=0; int main() { cin>>N; for(int..
11055번: 가장 큰 증가 부분 수열 (acmicpc.net) 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 해석 수열 A의 부분수열 중 제일 합이 큰 부분수열의 합을 구한다. 코드 문제 풀이 예제로 나온 "가장 긴 증가하는 부분 수열"과 비슷한 문제이다. n과 a에 input 값들을 넣어주고 누적합을 구하기 위한 list b를 선언해주었다. 그리고 b는 최소 자기자신을 더한 값이 나오므로 a의 값을 그대로 b로 옮겨주었다. n이 최대 1000..
https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 문제분석 분류 수학, 다이나믹 프로그래밍, 조합론 문제설명 N번째 행에는 N개의 수가 있다. 첫 번째 행은 1이다. 두 번째 행부터 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다. 정수 n과 k가 주어졌을 때, 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 출력한다. (1 ≤ k ≤ n ≤ 30) 코드 1 n, k = map(int, inp..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제분석 코드 n = int(input()) a_1 = 1 a_2 = 1 for _ in range(2, n+1): temp = (a_1 + a_2) % 10007 a_1 = a_2 a_2 = temp print(a_2) 문제분석 1. n = 1일 때 1, 2일 때 1가지 방법으로 배치 가능하다. 2. n = 3일 때는 위의 n=1일때 가로길이 2짜리 블록을 배치하는 방법 + n=1일 때 가로 1짜리 블록을 배치하는 ..
