알고리즘

(Python) 백준 2164번 - 카드 2

문제 링크 : https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 처음에는 단순히 list를 사용하여 풀이를 진행하였으나, 시간제한이 2초로 매우 짧아서 log(N)으로 삽입과 삭제를 진행하는 list로는 시간 초과가 발생할 수밖에 없었다. 그래서 상수 시간으로 조회, 삽입, 삭제가 가능한 deque를 사용하여 풀이를 진행하였다. import sys from collections import deque # 1부터 n까지의 카드들을 deque를..

(Python) 백준 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 풀이 처음에 이진탐색 구현 시에 인덱스를 사용하지 않고, python의 리스트 슬라이싱을 활용한 풀이를 사용했는데 시간 초과가 발생하였다. 리스트 슬라이싱은 지정한 범위의 모든 리스트의 원소를 복사하여 새로운 리스트를 만드는 과정을 거친다고 한다. 그렇기 때문에 시간 초과가 발생한 것이다. 따라서 아래 풀이처럼 슬라이싱한 리스트를 넘겨..

(Python) 백준 1018번 - 체스판 다시 칠하기

문제 링크 : https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 브루트포스 문제이기 때문에 하나하나씩 계산하는 과정이 귀찮을 뿐 풀이가 어렵진 않았다. import sys def cnt_sqr(r, c, board, bw): # 8*8로 체스판을 자른 후에 다시 칠해야하는 칸의 수 계산 cnt = 0 if bw == 'B': # 8*8 체스판의 시작칸이 'B'인 경우 for i in range(8): for j in range(8):..

(Python) 백준 11866번 - 요세푸스 문제 0

문제 링크 : https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 오랜만에 정렬이 아닌 다른 유형의 문제를 풀다보니 조금 헤메었다. 리스트를 사용해 간단한 원형 큐와 원형 큐에서의 삭제를 구현하면 되는 문제였다. import sys def josephus(arr, k, order): # N명의 사람이 저장된 arr에서 (N, K)-요세푸스 순열을 order에 저장 arrow = 0 # 제거될 사람의 번호 while len(arr) != 0: # 모든 사람이 제거될 때까지 arrow += (k-1) # 다음 K번쨰 사람을 지목 ..

(Python) 백준 11651번 - 좌표 정렬하기 2

문제 링크 : https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 11650번 문제와 정렬 순서가 바뀌었을 뿐, 동일한 정렬 문제로 볼 수 있다. sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[1], x[0] 순으로, 즉 리스트의 두번째 요소인 y좌표로 정렬 후에 첫번째 요소인 x좌표를 기준으로 정렬하게..

(Python) 백준 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 풀이 sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[0], x[1] 순으로, 즉 리스트의 첫번째 요소인 x좌표로 정렬 후에 두번째 요소인 y좌표를 기준으로 정렬하게 되는 것이다. import sys num = int(sys.stdin.readlin..

(Python) 백준 10814번 - 나이순 정렬

문제 링크 : https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[0], 즉 리스트의 첫번째 요소인 age를 기준으로 정렬하게 되는 것이다. import sys num = int(sys.stdin.readline()) arr = [] for _ in range(num): age, name = map(str, sys.st..

(Python) 백준 7568번 - 덩치

문제 링크 : https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 브루트포스 문제이다보니 실버 문제치고 풀이가 어렵지 않았다. import sys num = int(sys.stdin.readline()) weight = [] height = [] rank = [0] * num for _ in range(num): w, h = map(int, sys.stdin.readline().split()) weight.append(w) hei..

(Python) 백준 2751번 - 수 정렬하기 2

문제 출처 : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 합병 정렬을 사용한 풀이이다. O(NlogN)의 시간복잡도를 가지는 합병 정렬이기에 시간 초과가 발생하지 않을 것으로 기대했으나 시간 초과가 일어나서 상당히 당황했었다. 하지만 sys.stdin.readline()이 아닌 input()을 사용해서 시간초과가 발생한 것이었다. import sys def mergesort(arr): # 분할과 정복을 활용한 합병정렬 if..

(Python) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 처음엔 단순하게 에라토스테네스의 체 방식으로 풀어서는 시간 초과가 날 수 있을거 같았으나 문제 분류에 에라토스테네스의 체라고 적혀있어서 시도해보았더니 제한 시간 내에 통과할 수 있었다. n = int(input()) count = 0 # 소수가 아닐 경우를 count arr = list(map(int, input().split())) for num in arr: if num == 1: # 1은 소수가 아님 count += 1 # 소수가 아니면 c..