20210621 알고리즘 문제 풀이
백준 11729번 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729
풀이
n = int(input()) def hanoi(n, start, end): if n == 1: print(start, end) return hanoi(n-1,start, 6-start-end) print(start,end) hanoi(n-1, 6-start-end,end) print(2**n-1) hanoi(n,1,3)
- hanoi라는 재귀 함수 선언
- start에서 end로 옮긴다.
- start, end는 1,2,3 중 하나
- 나머지 막대는 6에서 start,end를 빼준 값
- n개의 원판이 있을 때, n-1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을 1번에서 2번으로 옮긴 뒤, 맨 밑의 원판을 1번에서 3번으로 옮긴다.
- n-1개의 원판들을 다시 2번에서 3번으로 옮긴다.
백준 11651번 좌표 정렬하기 2
https://www.acmicpc.net/problem/11651
풀이
N = int(input()) nums = [] for i in range(N): [x, y] = map(int, input().split()) arr = [y, x] nums.append(arr) nums = sorted(nums) for i in range(N): print(nums[i][1], nums[i][0])
- 숫자를 입력받는다.
- 빈 리스트(nums)를 만든다.
- 입력받은 숫자의 횟수만큼 x,y좌표를 리스트의 형태로 입력받는다.
- x,y좌표를 뒤집어서 [y,x]의 형태로 nums에 추가한다.
- nums를 sorted로 정렬해준다.
- 처음 입력된 횟수 만큼, b의 i번째 항의 1번쨰 요소, i번째 항의 0번째 요소를 출력한다.
- [y,x] 형태로 저장되어 있었기 때문에 다시 출력될 때는 [x,y] 형태로 출력된다.
백준 4949번 균형잡힌 세상
https://www.acmicpc.net/problem/4949
풀이
import sys input = sys.stdin.readline while 1: string = input().rstrip() stack = [] true_flag = 1 for cha in string: if cha == '(' or cha == '[': stack.append(cha) elif cha == ')': if stack and stack[-1] == '(': stack.pop() else: true_flag = 0 break elif cha == ']': if stack and stack[-1] == '[': stack.pop() else: true_flag = 0 break if string == '.': break print("yes" if true_flag and not (stack) else "no")
- 입력받은 문자가 좌측 괄호('(','[')인지 검사한다.
- 만약 좌측 괄호라면 스택에 넣어준다.
- 우측 괄호(')',']')인지 검사한다.
- 만약 우측 괄호라면 스택의 원소와 비교하여 괄호의 균형이 맞는지 검사한다.
- 입력받은 문자열이 종료 문자 '.'라면 종료하고, 아니라면 문제에서 원하는 출력을 수행한다.
백준 1021번 회전하는 큐
https://www.acmicpc.net/problem/1021
풀이
n, m = map(int, input().split()) s = list(map(int ,input().split())) q = [i for i in range(1, n + 1)] cnt = 0 for i in range(m): q_len = len(q) q_index = q.index(s[i]) if q_index < q_len - q_index: while True: if q[0] == s[i]: del q[0] break else: q.append(q[0]) del q[0] cnt += 1 else: while True: if q[0] == s[i]: del q[0] break else: q.insert(0, q[-1]) del q[-1] cnt += 1 print(cnt)
- 현재 뽑아내려고 하는 수가 큐의 앞쪽에 더 가까운지, 뒤쪽에 더 가까운지 판별
- 앞쪽에 더 가까우면 왼쪽으로 한칸 이동시키는 연산
- 뒤쪽에 더 가까우면 오른쪽으로 한칸 이동시키는 연산
- 이런 식으로 이동을 할 때 cnt를 증가시켜주고 마지막에 cnt 출력
백준 18528번 큐 2
https://www.acmicpc.net/problem/18528
풀이
import sys from collections import deque n = int(sys.stdin.readline()) q = deque([]) for i in range(n): s = sys.stdin.readline().split() if s[0] == 'push': q.append(s[1]) elif s[0] == 'pop': if not q: print(-1) else: print(q.popleft()) elif s[0] == 'size': print(len(q)) elif s[0] == 'empty': if not q: print(1) else: print(0) elif s[0] == 'front': if not q: print(-1) else: print(q[0]) elif s[0] == 'back': if not q: print(-1) else: print(q[-1])
- pop할 때 del 함수를 사용하면 나머지 요소들이 앞으로 땡겨지는데 시간이 걸리므로 deque로 구현하여 popleft() 함수를 사용한다.
백준 2108번 통계학
https://www.acmicpc.net/problem/2108
풀이
import sys from collections import Counter n = int(sys.stdin.readline()) nums = [] for i in range(n): nums.append(int(sys.stdin.readline())) nums.sort() nums_s = Counter(nums).most_common() print(round(sum(nums) / n)) print(nums[n // 2]) if len(nums_s) > 1: if nums_s[0][1] == nums_s[1][1]: print(nums_s[1][0]) else: print(nums_s[0][0]) else: print(nums_s[0][0]) print(nums[-1] - nums[0])
- Counter를 사용하여 요소의 개수를 세어준다.
- most_common()은 빈도수가 높은 순으로 리스트 안의 튜플형태로 반환해준다.
- 만약 첫 번째와 두 번째의 value값으 비교해서 같다면 두 번째 key 값을 출력한다.
- key 값이 오름차순으로 정렬되어 있으므로 nums_s 길이가 1이라면 입력받은 값을 출력한다.
백준 1002번 터렛
https://www.acmicpc.net/problem/1002
풀이
t = int(input()) for i in range(t): x1, y1, r1, x2, y2, r2 = map(int, input().split()) d = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5 rs = r1 + r2 rm = abs(r1 - r2) if d == 0: if r1 == r2: print(-1) else: print(0) else: if d == rs or d == rm: print(1) elif d < rs and d > rm: print(2) else: print(0)
- 원과 원의 접점의 개수를 구하는 문제
- x와 y는 원의 중심위치, r은 원의 반지름이 될 수 있다.
- 우선 두 개의 원의 중심 사이의 거리를 d라고 하고, 피타고라스의 정리를 이용해 거리를 구해준다.
- 그리고 공식을 이용해 적정한 값을 출력해준다.
if d == 0: if r1 == r2: print(-1) else: print(0)
- 위의 코드는 d가 0일 때, 즉 두 원의 중심위치가 같을 때 반지름이 같다면 두 개의 원이 겹친다는 것이므로 무한개의 점을 만들어낼 수 있다.
그래서 -1을 출력하고 그게 아니라면 아예 만나지 않으므로 0을 출력한다.else: if d == rs or d == rm: print(1) elif d < rs and d > rm: print(2) else: print(0)
- 위의 코드는 d가 0이 아닐 때, 즉 원의 중심 위치가 서로 다를 때이다.
- 원의 중심 사이 거리가 각 반지름의 합과 차이가 같다면 접점은 1개이다.
- 원의 중심 사이의 거리보다 반지름의 합이 더 크고, 반지름의 차가 더 작으면 접점이 2개이다. 그게 아니면 두 원의 접점은 없다.
백준 2798번 블랙잭
https://www.acmicpc.net/problem/2798
풀이
N,M = map(int,input().split()) arr = list(map(int,input().split())) result = 0 for i in range(N): for j in range(i+1,N): for k in range(j+1,N): if arr[i] + arr[j] + arr[k] > M: continue else: result = max(result, arr[i] + arr[j] + arr[k]) print(result)
- 모든 경우의 수를 다 뒤져봐야 하는 완전 탐색 문제
- N,M을 입력받아 int로 변환
- 카드에 쓰여 있는 수들을 list로 만들어 저장
- 문제 조건에 적합한 수를 저장하여 반환하기 위한 변수 result 선언
- 3개의 카드를 뽑아야 하며 이에 대한 모든 경우의 수를 살펴보기 위해 3중 for문을 이용
- 첫 for문에서는 0
- N, 세번째 for문에서는 2~N을 순회하면서
- 모든 경우의 수를 확인하며 각각의 값을 더한 뒤, 세 카드의 값이 M보다 클 경우에는 continue
- M보다 크지 않을 경우, 일단 정답의 가능성이 존재하므로 result에 저장
- 이렇게 모든 경우를 반복하면 결국, result 변수에는 M의 값 또는 M에 가장 가까운 값이 저장된다.
백준 2231번 분해합
https://www.acmicpc.net/problem/2231
풀이
N = int(input()) result = 0 for i in range(1,N+1): A = list(map(int,str(i))) result = i + sum(A) if result == N: print(i) break if i == N: print(0)
- 입력값 N과 입력값과 비교하기 위한 변수 result 선언
- str 함수를 통해 i의 각 자리수를 A 리스트에 넣기
- i와 각 자리수가 들어간 A 리스트의 합을 더하면 분해합(result)이 된다.
- 분해합(result)과 N이 같다면 i를 출력한다. >> 가장 작은 생성자
- i와 N이 같다면 0을 출력한다. >> 생성자가 없는 경우
프론트엔드 개발자를 꿈꾸는