본문 바로가기

코딩 농장/백준 문제

 (16)
[백준 Python] 3020 개똥벌레 https://www.acmicpc.net/problem/3020 문제정리 동굴 길이 N , 높이 H 석순, 종유석 ( 아래, 위 ) 순서로 장애물의 길이가 입력된다. 임의의 높이로 일직선을 그을 때 만나는 장애물의 수가 가장 적은 높이를 출력 문제풀이 먼저 가장 쉽게 생각해보자 모든 H 에 대해서 arr[N] 를 처음부터 끝까지 확인해서 석순은 H 보다 낮은 원소의 개수를, 종유석은 H 보다 높은 원소의 개수를 구하면 된다. 즉 시간은 모든 H 에 관해 arr[N] 배열의 확인을 하면 되므로 O(NH) 이다. 이 방법은 20만*40만이라 시간초과가 난다. 어떻게 줄일 수 있을 지 확인해보자 모든 H 에 관해 판단을 해야하는 것은 당연하다. -> 그래야 최소로 부딪히는 H 를 구하쥬 그렇다면 반복적으로 ..
[백준 Python] 2110 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제정리 N 개의 집이 수직선 위에 있다. 중복X C 개의 공유기를 설치한다. 이때 한 집에 하나만 설치하며 인접 설치 X 이다. 가장 인접한 공유기의 거리가 최대인 경우를 구해라 * (1, 2, 4) 는 불가 (2, 6, 8) 일 때는 output : 4 문제풀이 1. greedy 로 생각해 보자 N 개의 집에서 C 개를 뽑아 공유기를 설치해본..
[백준 Python] 1072번 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 문제정리 게임횟수 X, 이긴게임 Y 인 상태에서 승률은 Z 이다. ( 소수점 버림 ) 이때 항상 이기는 게임 a 번을 했을 때 승률이 바뀌도록 해라. 문제풀이 Z = Y*100 // X 이다. *Z = (Y+a)*100 // (X+a) 에서 Z 와 *Z 가 달라지는 a 값을 구하면 된다. Z 가 이미 99 라면 아무리 게임을 해도 100 으로 가지 못하며 Z 가 100 이라면 변화가 없으므..
[백준 Python] 2512번 예산 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제정리 N개의 예산 신청을 예산액에 맞게 부여해야 한다. 기준 예산액을 정한 후 기준 예산액보다 작은 경우 그대로 배정, 클 경우 기준 예산액으로 부여한다. 문제풀이 기준 예산액을 정해야한다. 기준 예산액을 정한 후 예산액을 계산해서 통과인지 아닌지 찾기 기준 예산액을 1부터 최대 예산액 까지 증가시키며 조건을 만족하는지 찾을 수 있다. ( 브루트 포스 ) 이분 탐색으로 기준 예산액을 구해..
[백준 Python] 15975번 화살표 그리기 https://www.acmicpc.net/problem/15975 15975번: 화살표 그리기 직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 www.acmicpc.net 문제이해 수평선에 (좌표, 색) 점이 주어짐 각 점에서 같은 색을 가진 가까운 점의 거리를 구하고 다 더함 문제 풀이 흐름 결국 같은 색의 점들을 오름차순으로 모아둔 다음 양 옆의 가까운 점과 거리를 구하면 된다. 양 끝 점은 바로 옆 놈 더해주면 되고 # 수평선 (좌표, 색) # 모든 점에 대해 같은 색이며 가장 가까운 점까지의 거리를 구하고 # 다 더함 num = in..
[백준 Python] 1431번 시리얼 번호 https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 문제정리 기타 시리얼 번호를 입력받는다 > 순서에 맞게 출력 1. 길이가 짧은 것 먼저 2. 같다면 숫자의 합이 작은놈 먼저 3. 나머지 사전순 출력 ( 숫자 < 알파벳 ) 문제 풀이 흐름 1. 문자열을 받아서 어떤 자료형에 담아볼까? 일단 문자열 길이를 기준으로 오름차순, 문자열의 합으로 오름차순, 사전순 오름차순을 해줘야 한다. list 로 받아 해결하면 되겠다. num = int(inp..
[백준 Python] 20923번 숫자 할리갈리 게임 문제는 생략한다. 사실 그냥 Stack, Queue, Deque 를 사용할 때 파이썬에서 deque 를 사용해 한번에 해결하는 것이 편하다고 생각한다. from collections import deque deq = deque() # Add element to the start deq.appendleft(10) # Add element to the end deq.append(0) # Pop element from the start deq.popleft() # Pop element from the end deq.pop() deque.append(item): item을 데크의 오른쪽 끝에 삽입한다. deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다. deque.pop(): 데크..
[백준] 여러가지 문제풀이 방법 모음 ★유클리드 호제법 : 최대공약수 구하기 증명하는 방법 한번만 검색해서 보고 바로 쓰면 된다. a,b 가 있을 때 (a>b) a 를 b 로 나눈 나머지와 b 와의 최대공약수는 a, b 의 최대공약수와 일치한다. (a, b 의 최대공약수 = b, a%b 의 최대공약수) 이를 뒤에 것이 0이 아닐 때 까지 반복하면 된다. (12, 4) -> (4, 0) -> 최대공약수 4 (12, 5) -> (5, 2) -> (2, 1) -> (1, 0) -> 최대공약수 1 ★소수 1. 테스트케이스 마다 소수를 구할 수도 있지만 미리 배열에 소수를 구해놓을 수 있다. 2. 이때 각 숫자가 소수인지 판단하는 것이 아니라 "배수" 를 사용한다. ( arr[i] 가 소수라면 -> i 의 배수 arr 은 모두 소수 X ) ★이분탐색..

티스토리툴바