https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net # N이 20억이고 M이 1000이므로 이분탐색을 사용해야 한다는 것을 알 수 있다. 이분탐색을 사용하는 문제는 '이분탐색' 자체로 후보수를 매우 극단적으로 줄일 수 있기 때문에 풀이 자체는 naive한 경우가 많았다. 특히 매개변수 탐색 문제를 여러개 풀어보면서 느꼈다. 이 문제 역시 이분탐색이란 걸 생각한 뒤, naive한 방법을 생각했는데 그게 맞았다. ..
https://programmers.co.kr/learn/courses/30/lessons/72411?language=python3 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr # 2021 카카오 블라인드 코딩테스트 문제이다. # 우선 메뉴종류가 A부터 Z까지 26가지이고 course가 10이하이므로 모든 요리를 다 확인한다해도 26C1 + 26C2 + 26C3 + ... + 26C10 = 10,970,271가지이다. 따라서 모든 메뉴의 조합을 다 구한 뒤 각 메뉴의 개수를 파악해서 풀어주었다. 1. 각 손..
https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net # 그냥 문제만 읽어봐도 MST를 사용해서 푸는 문제임을 알 수 있다. 1. 처음에 M개의 도로를 (a, b, c)로 입력받고 build에는 (c, a, b)로 저장해준다. ( build.sort()를 했을때 c부터 정렬되게 하기 위해서) 2. total_cost에 모든 도로..
https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net # N이 100만이하이고, M이 100만이하이므로 단순히 M에서 찾고자하는 문자열을 하나하나 비교해서 풀면 O(N * M)이므로 시간초과가 난다. 해설들을 보니 M을 한번만 순회해서 찾는 O(M)방법도 많고 빠르긴 한데 KMP알고리즘을 공부하기 위해 KMP를 사용해서 풀었다. (KMP 알고리즘은 O(N + M)에 동작한다. # k..
https://programmers.co.kr/learn/courses/30/lessons/84512?language=python3 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr # 모음이 5개 밖에 없고 길이도 5가 최대이므로 A부터 UUUUU까지 모든 단어를 만든뒤 dic에 넣고 찾고자 하는 단어의 index를 반환하는 식으로 짰다. 1. 처음에 11번째줄에서 반복문을 돌며 add_word('A'), add_word('E') ... add_word('U')를 ..
https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr # 2021 카카오 블라인드 코딩테스트 문제이다. # 그냥 문제를 보면 '그래프' ..
https://programmers.co.kr/learn/courses/30/lessons/84325?language=python3 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr # 위클리 챌린지 4주차 문제이다. (3주차 문제는 너무 헬이어서 못 풀었다..) # 문제에서 시킨대로 단순 구현만 하면 되는 문제이다. 어차피 문제에서 주어지는 table은 그대로라고 했으므로 SI, CONTENTS, HARDWARE, PORTAL, GAME의 딕셔너리를 미리 만들어 놓고 시작했다. 1. 선호하는 언어의 번호와 선..
https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr # 2020카카오 블라인드 코딩테스트 2번문제이다. # 문제 설명이 친절하지 않은데.. 문제 설명을 잘 읽고 따라가면 크게 어렵지 않게 풀 수 있다. 1. 우선 '균형잡힌 괄호 문자열'과 '올바른 괄호 문자열' 두가지가 있는데, '균형잡힌 괄호 문자열'은 단순히 ')'의 개수와 '('의 개수가 같으면 된다. '올바른 괄호 문자열'은 우리가 처음 스택을 배울때 푸는..
모르는 사이에 조금씩 조금씩..
