상상쓰

https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 중복되지 않은 소수의 곱이 최소 공배수이다. 중복되는 소수가 나올 수 있는 경우를 주의하자. '틀렸습니다' 가 아닌 '출력 초과' 로 나와서 뭐가 틀렸는지 한참 찾았다. import sys, math def prime(n): answer = True for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: answer = False break return answer N = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().st..

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 저번에 풀었던 [3차] 자동완성에서 썼던 Trie 자료구조를 이용하였다. '?' 가 접두사 아니면 접미사로만 존재하기 때문에 두 개의 dictionary 를 만들어 검색할 수 있도록 하였다. 예를 들어, 'frodo' 를 dictionary에 추가시키면 {'f': {'*': [5], 'r': {'*': [5], 'o': {'*': [5], 'd': {'*': [5], 'o': {'*': [5]}}}}}} 이고 '*' 는 그 위치의 문자를 가진 문자열의 길이가 5인 것이 하나 존재한다는 의미이다. 'front', 'frost' 과 'fronze..

https://programmers.co.kr/learn/courses/30/lessons/42888?language=python3 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 퇴근! def solution(record): answer = [] dic = {} for i in record: if i[0] != 'L': command, idx, name = i.split() dic[idx] = name for i in record: if i[0] == 'E': answer.append(dic[i.split(..

https://www.acmicpc.net/problem/5545 5545번: 최고의 피자 상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 www.acmicpc.net 초기의 값 C // A 를 기준으로 분모와 분자에 값을 계속 더하여 최고의 피자를 찾는 문제이다. 분모는 토핑이 추가될 때마다 일정하게 더해주고(B) 분자에는 토핑의 열량을 더해준다. 즉, 토핑의 열량을 큰 것부터 처리했을 때, answer 이 감소하는 시점부터 토핑의 열량은 계속 전보다 작은 값을 더해주므로 증가하고 감소하는 시점에 break 를 걸어준다. 수학적으로 증명하기는 쉽다. 예를 들면 1과..

https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3# 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 예를 들어, 정렬하면 '119,' '11955' 가 되며 119 와 11955 사이에 접두어가 119 가 아닌 전화번호가 올 수 없다. def solution(phone_book): answer = False N = len(phone_book) phone_book.sort() for i in range(N-1): answer ..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 파스칼의 삼각형의 원리를 이용하여 다리를 지을 수 있는 경우의 수를 동적 계획법으로 구현할 수 있다. 동적 계획법으로 조합을 구한다. import sys dp = [[0] * 31 for i in range(31)] for i in range(31): dp[i][0] = 1 for i in range(1, 31): for j in range(1, 31): dp[i][j] = dp[i-1][j-1]..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1부터 시작하여 BFS 알고리즘을 이용하여 구현했다. while 문을 한번 돌 때마다 deque 의 popleft() 함수를 이용하면 1과의 거리가 1씩 늘어나는 번호들의 집합을 얻을 수 있다. from collections import deque, defaultdict def solution(n, edge): answer = 0 dic = defaultdict(list) D = defaultdict(int) D[1] = 1 que..

https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 4단계 문제 '호텔 방 배정' 처럼 재귀함수를 이용하여 위치를 찾고 'C' 일 때, k 를 remove 에 담아 처리하려고 했으나, 'Z' 때문에 구현하기가 힘들 것 같았다. 그래서 생각해낸 것이 heapq 를 이용하였다. 'Z' 의 경우에도 복원된 행의 위치를 queue 에 담기만 하면 제 위치를 찾아가기 때문..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net heapq 를 이용하여 bigger 과 smaller 인 queue 를 만들어서 기준이 되는 중간값(bigger[0]) 을 기준으로 크면 bigger, 작으면 smaller 에 추가해준다. bigger[0] 은 값이 추가될 때, 그 값이 smaller 의 어떤 원소보다 작을 수 있으므로 smaller[0] 과 비교하여 작으면 교체해준다. import sys, heapq N = in..

https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 문제를 잘 읽어보면 커플이 문제다. import sys N = int(sys.stdin.readline()) S = sys.stdin.readline().strip() n = 0 for i in S: if i == 'L': n += 1 answer = N if n == 0 else N - (n // 2) + 1 print(answer)