도각도각 필기노트

대표적인 이진탐색, 파라메트릭 탐색 문제였다. mid 값을 답 후보로 두고 start 와 end 를 조정해나가며 푸는 문제였다. import sys k, n = map(int, input().split()) array = [int(sys.stdin.readline().strip()) for _ in range(k)] start = 1 end = max(array) while start

입력이 많은 문제이다. 시간 초과가 나면 input 대신 sys.stdin.readline() 을 사용할 것!! * 처음에는 주어진 숫자들이 순위가 아니라 점수인 줄 알고 문제 이해를 못했었다.. 문제를 잘 읽자!! 우선 첫번째 순위로 정렬을 해준다. 1 4 2 3 3 2 4 1 5 5 그러고 나면 두번째 순위만 따져주면 된다. rank라는 변수에 첫번째 사원의 두번째 순위를 초기값으로 넣어준다. 아래 사람으로 갈수록 첫번째 순위는 전 사람보다 낮기에 두번째 순위가 rank(이전 사원의 순위)보다 커야 선발이 된다. 1 4 2 3 이 두 사람을 비교할 땐, rank=4와 3을 비교하게 된다. 4등보다 3등이 높으므로 두번째 사람은 선발된다. rank는 더 높은 순위의 것으로 업데이트해준다. 4 1 5 5..

일단 숫자(numbers)와 연산자(operators)를 구분해주었다. 보통 구분자를 기준으로 나눌 때 split 함수를 사용하는데, 여기서는 +, - 두 가지로 구분을 해야하기 때문에 import re 를 통해 여러 개 구분자로 split 해주었다. 아래 코드와 같이 numbers = re.split('[+-]', S) 으로 써주었다. split 기준이 될 기호를 '[ ]' 안에 넣는 형식으로 사용한다. 문제 풀이 아이디어 최솟값이 나와야 하므로 +와 -가 있을 때 최대한 -로 계산되게 하는 것이 문제의 핵심이었다. previous에 이전 연산자를 넣고, now에 현재 계산할 연산자를 넣은 다음, 둘을 비교하여 현재 숫자를 더할지 뺄지 결정하였다. (1) previous = +, now = + 그대로 ..

www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 여러 개의 숫자들 간의 최대공약수를 구하는 문제이다. 100, 360, 25, 10 간의 최대공약수를 구한다고 하면, gcd(100, 360) = 20 gcd(20, 25) = 5 gcd(5, 10) = 5 이런 식으로 앞에 두 수의 gcd를 구하고, 결과로 나온 그 gcd값과 다음 수와의 gcd를 구하고, 이런 방식으로 반복하여 여러 수들 간의 gcd를 구한다. def gcd(..

www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net n,m = map(int, input().split()) check = [False]*(m+1) for i in range(2, m+1): if check[i] == False: for j in range(i*2, len(check), i): check[j] = True # True: 소수가 아닌 수 if n==1: for i in range(2,m+1): if check[i] == False: print(i) else: for i in ra..

www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 덱을 이용하는 문제 잊고 있던 덱 기본 문법을 익히기 좋은 문제였다. import collections people, n = map(int, input().split()) deq = collections.deque([]) answer = [] for p in range(people): deq.append(p+1) while len(deq) != 0: for _ in range(n): x = deq.popleft() deq.append(x) answer.append(deq.pop()) print('') ..

www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 커서를 기준으로 left, right 스택을 두고 풀어야 한다. 코드 플러스 알고리즘 기초 강의를 수강하면서 문제를 풀고 있는데, 강의에서 스택문제라는 걸 알고 풀어서 나름 쉽게 풀렸는데 스택을 이용해야하는 문제라는 것을 아는 것이 중요한 것 같다. import sys sen = list(input()) # 입력 문자열 n = int(input()) # 명령어의 개수 cmds = [] for _ in range(..

백준 문제풀이를 시작했다. 평소 프로그래머스 문제들만 풀다가 처음 백준을 풀기 시작했는데 변수 입력받는 것부터 헤매서 정리를 하려고 한다. www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net split() a.split()처럼 괄호 안에 아무 값도 넣어 주지 않으면 공백(스페이스, 탭, 엔터 등)을 기준으로 문자열을 나누어 준다. 만약 b.split(':')처럼 괄호 안에 특정 값이 있을 경우에는 괄호 안의 값을 구분자로 해서 문자열을 나누어 준다. input().split() 여러개 입력받을 때. 리스트 형태로 반환 map map(데이터 타입, 리스트) : 리스트 원소들을 해당 ..