본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 문제풀이 전형적인 이진 탐색 문제이자 파라메트릭 서치(parametric search) 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정 문제(’예’, ‘아니오’로 답하는 문제)로 바꾸어 해결하는 기법이다. 범위 내에서 조건을 만족하는 가...

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 문제풀이 내풀이 # 데이터의 범위가 1,000,000 이하이기 때문에 계수 정렬을 사용 가능할 것 같음 # 매장의 부품 개수 N 입력받기 n = int(input()) # 매장의 부품 종류 입렫받기 parts = list(map(int...

이진 탐색(Binary Search) : 반으로 쪼개면서 탐색하기 예시의 그림은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임. 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를 나타내는 3개의 변수를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다....

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 성적이 낮은 순서로 학생 출력하기 내풀이 # 학생 수 N 입력받기 n = int(input()) # 학생의 이름과 성적 입력받기 dict = {} for i in range(n): name, score = input().split(' '...

정렬(Sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐(정렬 알고리즘은 이진 탐색의 전처리 과정) 이번 글에서는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 다뤄보자. 1. 선택 정렬(Selection Sort) 데이터가 무작위로 여러 개 있을 때, 이 중...

문제 설명 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가...

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 문제 풀이 이러한 거스름돈 문제는 그리디로도 풀 수 있는데, 여기서는 화폐 단위가 큰 단위가 작은 단위의 배수가 아니기 때문에 그리디로는 해결할 수 없고 DP로 해결해야 한다. 적은 금액부터 큰 금액까지 확인가며 차례대로 만들 수 있는 최소한의 ...

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 풀이 현재 i번째 식량창고에서 i-1번째와 i-2번째를 확인해가며 진행해가므로 DP로 문제를 푼다. 왼쪽부터 차례대로 식량창고를 턴다고 생각하자. i-3번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 한 칸 이상 떨어진 식량창고는 항상...

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 문제 풀이 DP에서 흔한 문제인 타일링 문제라고 한다. 왼쪽부터 차례대로 덮개를 채운다고 생각해보자. 사용할 수 있는 덮개의 형태가 최대 2x2 직사각형이기 때문에 N-2 미만의 길이에 대해서는 고려할 필요가 없다. 앞서 계산된 결과를 DP 테이...

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임 문제 풀이 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있을 것 같기 때문에 DP를 떠올렸다. 탑다운 보다는 보텀업 방식으로 구현하는 것이 좋다고 하여 보텀업 방식으로 코드를 구현한다. 소스코드 # 정수 x 입력받기 x = int(inp...