BOJ 9012. 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 여는괄호 '(' 면 스택에 담는다. 닫는괄호 ')' 면 스택에서 pop()한다. 만약 중간에 '('가 아닐 때, 스택이 비어있으면 괄호가 맞지 않는 것이므로 답은 "NO"이다. 루프가 종료되고 스택이 비어있으면 괄호가 맞는 것이므로 "YES" 루프가 종료되어도 스택에 무언가가 남아있다면 괄호가 맞지 않는 것이므로 "NO"이다. 소스코드 i..

사전의 기본값 처리 collections.defaultdict 일반적인 dictionary 기본값 처리 숫자 리스트 li = [1,1,2,2,2,3,3,5] 의 출현 횟수를 count하는 경우를 생각해 봅시다. 딕셔너리를 이용해 구할 수 있습니다. 포문을 돌며 딕셔너리에 해당 값이 없을 경우엔 i가 키인 값을 0으로 초기화 해주고 모든 경우에 += 1 해줍니다. li = [1,1,2,2,2,3,3,5] dict = {} for i in li: if i not in dict: dict[i] = 0 dict[i] += 1 print(dict) """ {1: 2, 2: 3, 3: 2, 5: 1} """ if문을 사용해 존재하지 않는 키에 대한 값을 초기화 해주는 이유는 존재하지 않는 키에 접근했을 경우 다음과..

BOJ 1978. 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 입력 받은 수들을 모두 한번씩 소수인지 검사 하면 된다. is_prime()함수는 간단하다. def is_prime(n) -> bool: if n == 1: return False i = 2 while i < n: if n % i == 0: return False else: i += 1 return True 1은 소수가 아니므로 False 리턴 무언가로 나눠지면 소수가 아니므로 False 리턴 (자기 자신과는 무조건 나누어 떨어진다..

BOJ 1920. 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이진 탐색(Binary Search) 으로 풀었다. 이진탐색의 원리는 이러하다. 탐색하고자 하는 리스트를 오름차순으로 정리한다. target < 중앙값 이면 target은 중앙값의 왼쪽에 있으므로 end(index)를 중앙값index - 1 로 설정하고 중앙값의 오른쪽은 버린다. 중앙값 < target 이면 targe..

BOJ 11650. 좌표 정렬하기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 BOJ 1181 과 같은 방법으로 파이썬의 내장함수 sort()에 key 파라미터를 (첫번째 기준, 두번째 기준)의 튜플로 넘겨주어 정렬한다. 소스코드 import sys locations = [] N = int(input()) for _ in range(N): (x, y) = map(int, sys.st..

BOJ 10814. 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 BOJ.1181 단어정렬 처럼 파이썬의 내장함수의 sort()를 이용하면 쉽게 풀 수 있다. for i in range(N): tmp = sys.stdin.readline().split() tmp.append(i) member.append(tmp) 정렬할때 먼저 가입한 순서가 두번째 기준이 되기 때문에 입력 시에 세번째 원소에 순서도 append해준다. 그렇게 되면..