https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 분류 이진 탐색(이분 탐색) 문제 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서..
Koala - 13기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 유형 누적합 문제 농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자. 입력 첫 줄에..
문제 https://www.acmicpc.net/problem/2230 풀이 해당 문제는 투 포인터를 사용하면 된다. 투 포인터를 사용하기 위해서는, 먼저 정렬을 진행해줘야 한다. 문제의 요구사항은 두 수의 차 중 M보다 가장 작은 차이를 구하는 것이므로, M을 구하게 되면 바로 답이 된다. 나머지의 경우, 차이 값의 최소 값을 갱신하며 찾아가면 된다. 코드 N,M = map(int, input().split()) nums = [int(input()) for _ in range(N)] nums.sort() left,right = 0,1 result = 2e9 while left
https://www.acmicpc.net/problem/6159 6159번: Costume Party It's Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The costume fits precisely two cows with a length of S (1
https://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 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int dp[100][100001]; int main() { memset(d..
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제요약 모래의 양이 표시된 격자가 있고, 토네이도가 격자 안을 돌아 나간다. 토네이도는 모래를 주어진 규칙에 맞게 흩뿌리면서 지나가는데, 이때 토네이도가 최종적으로 격자끝에 도달했을 때, 격자 바깥으로 나간 모래의 양을 구하는 시뮬레이션 문제 문제 해결 문제에서 흩뿌리는 정보가 토네이도 현재위치 기준으로 주어졌으므로, 먼저 토네이도의 위치변화를 문제의 주어진 조건..
문제 https://www.acmicpc.net/problem/13567 13567번: 로봇 입력은 표준 입력으로부터 받는다. 첫 줄에는 두 정수 M과 n (1 ≤ M ≤ 1,000, 1 ≤ n ≤ 1,000)이 주어진다. M은 정사각형 S의 한 변의 길이, 즉 오른쪽 맨 위의 좌표는 (M, M)이 된다. n은 로봇이 수행할 www.acmicpc.net Algorithm n개의 명령어 이후에 로봇의 위치를 출력하는 문제이다. 만약 로봇이 구역을 벗어난다면 -1을 출력하도록 구성해야 한다. 로봇이 구역을 한번이라도 벗어난다면 -1을 출력해야 하므로 명령어가 입력될때마다 현재 위치를 확인하여 판단해주어야 하므로 flag변수를 이용하여 판단하였다. 로봇이 MOVE명령어를 입력받으면 해당 칸수만큼 현재 바라보고..
1417번: 국회의원 선거 (acmicpc.net) 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 문제유형 *시뮬레이션 문제 다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다. 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다. 현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M..
문제 설명 매 초 바이러스가 인접한 칸으로 전염되고, 바이러스의 번호가 낮은 순부터 먼저 증식한다. 따라서 최소 힙을 구성하여 현재 바이러스의 시간과 번호를 차례로 넣어주면, 바이러스 중에서 시간이 가장 적은 바이러스가 먼저 선택되고, 같은 시간 내에서는 낮은 번호부터 선택된다. 풀이 import sys, heapq input = sys.stdin.readline DIR = [(1,0), (-1,0), (0,-1),(0,1)] def bfs(graph, n, s): que = [] # (흐른 시간, 바이러스 레벨, y좌표, x좌표) for i in range(n): for j in range(n): if graph[i][j] > 0: heapq.heappush(que, (0, graph[i][j], i,..
문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력 1 9 5 12 7 10 9 1 2 3 11 13 예제 출력 1 3 해결 먼저 수열의 크기와 수열, 합을 입력 받고, 수열을 오름차순으로 정렬한다. 투포인터를 이..
문제 https://www.acmicpc.net/problem/11726 기본 풀이 해당 문제는 dp로 풀 수 있습니다. 하나씩 채워 나간다고 생각했을 때, 채울 수 있는 방법은 2가지입니다. 세로 직사각형 채우기, 가로 직사각형 채우기입니다. 하지만, 가로 직사각형은 칸을 채우기 위해 가로 직사각형을 겹쳐서 2개씩 (정사각형 모양으로) 채워야만 합니다. 1. 두 단계 전(dp[i-2]) + 정사각형(가로 직사각형 두 개) 2. 한 단계 전(dp[i-1]) + 직사각형(세로 직사각형 한 개) 이렇게 두 가지로 나눠볼 수 있기에, dp[i] = dp[i-2]+dp[i-1] 의 반복으로 구할 수 있습니다 코드 풀이 그러나, 고민을 해보면 다른 수학적 방법이 있습니다. 직관적으로 가장 간단하게 채우는 법은 세..
문제 https://www.acmicpc.net/problem/14916 설명 - DP (다이나믹 프로그래밍) - 1부터 9까지의 숫자 중에서 -1이 나오는 경우는 1과 3밖에 없다. 그리고 나머지 값들에 대해서는 미리 해당하는 동전 개수를 할당해주었고, 10부터의 숫자는 동일한 규칙을 발견할 수 있다. 10원 : 5원 * 2 + 2원 * 0 => (5원) + 1개 11원 : 5원 * 1 + 2원 * 3 => (6원) + 1개 12원 : 5원 * 2 + 2원 * 1 => (7원) + 1개 . . 코드 n = int(input()) # 0 1 2 3 4 5 6 7 8 9 dp = [-1, -1, 1, -1, 2, 1, 3, 2, 4, 3] for i in range(10, n+1): dp.append(dp..
