이것이 취업을 위한 코딩 테스트다 with 파이썬

큰 수의 법칙 문제는 전형적인 그리디 알고리즘 문제로, 중첩 while문을 이용하여 문제를 해결하였습니다. while문의 조건에는 입력받은 M과 K를 이용하였습니다.

입력받은 행의 개수 N개만큼 반복문을 반복하여 행마다의 최솟값을 우선 찾았습니다. 그 후 매 행마다 기존의 최댓값과 비교를 함으로써 각 행마다의 최솟값들 중 최댓값을 찾도록 하였습니다.

K로 나누는 연산이 1을 빼는 연산보다 빠르게 N이 1이 될 수 있도록 해주기에, 나눗셈을 최대한 활용하는 해결 방안을 생각해 보고자 하였습니다.

입력 받은 모험가의 공포도 값 리스트를 함수로 정렬한 후 공포도가 작은 사람부터 하나 씩 그룹에 넣어가며, 그룹이 형성 조건에 위배되지 않으면 그룹으로 형성하도록 코드를 작성하였습니다.

보통의 경우 곱하기가 더하기보다 더 빠르게 큰 숫자를 만들기에 최대한 곱하기를 활용하는 방향으로 가되, 더하기를 사용해야만 하는 경우가 있다면 그때는 더하기를 사용하도록 하는 코드를 작성하고자 하였습니다.

문제에서 '연속된 하나 이상의 숫자를 잡고 모두 뒤집는 행동'을 할 수 있다고 쓰여있으므로 하나 이상의 같은 숫자로 이루어진 배열은 하나의 숫자로 이루어진 배열로 바꾸어주었습니다.

동전들을 이용하여 다양한 조합을 시도해 본 후에, 조합 마다의 나올 수 있는 모든 합들의 unique 한 값들을 sort 한 후 연속된 자연수들 중에서 빠져있는 수가 있다면 출력할 수 있도록 하였습니다.

A가 i번째 공을 선택하면 B는 i번 이후의 공을 선택하도록 코드를 작성하였습니다. 그렇게 중첩된 for 문을 이용하여 하나하나씩 A가 선택한 공과 B가 선택한 공을 비교해가며 가능한 경우의 수를 세어 주었습니다.

먹는 데 소요 시간이 적은 음식 같은 경우 먼저 없어지는 것을 이용하여 해결한 풀이입니다.

📖 DFS(Depth-First Search) - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 📖 BFS(Breadth-First Search) - 가까운 노드부터 탐색하는 알고리즘

dfs 알고리즘을 이용하여 재귀적으로 '덩어리'의 시작점을 찾아 얼리기 시작한 후 '덩어리'전체를 얼려나가는 코드입니다.

bfs를 이용하여 차근차근 주위의 좌표들로 이동해가며 해당 좌표로의 최단 경로의 거리를 계산하는 방법을 이용하여 문제를 해결하였습니다.

bfs를 이용하여 출발 도시와 연결되어 있는 도시들과의 최단 거리를 모두 계산하고 특정 거리에 있는 도시를 찾고자 하였습니다.

itertools 내의 combination 모듈을 이용하여 가능한 1의 좌표들의 조합을 모두 구한 후, 각 경우들에 대하여 바이러스를 최대한 퍼뜨린 후 남아있는 0의 개수를 세는 방식으로 코드를 작성하였습니다.

주어진 시간 동안 바이러스를 순서대로 증식시킨 후 찾고자 하는 좌표의 바이러스 종류를 출력시키는 코드를 작성하였습니다. 이때, '바이러스를 순서대로 증식시키는 코드'는 bfs를 이용하여 작성하였습니다.

solution 함수 같은 경우는 문제에서 제시해 준 "올바른 괄호 문자열"로 변형하는 알고리즘에 맞춰 dfs를 이용하여 재귀적으로 구현을 하였습니다.

(1) dfs를 이용하지 않은 풀이, (2) dfs를 이용한 풀이를 통하여 문제를 해결하였습니다.

dfs 알고리즘 혹은 combinations 함수를 이용하여 3개의 장애물을 설치하는 모든 경우의 수에 대해 고려할 수 있도록 하였고, moniter이라는 함수를 구현하여 선생님께서 상하좌우 일직선 위에 있는 모든 위치를 다 확인할 수 있도록 하였습니다.

bfs 함수를 이용하여 인접한 나라들부터 차근차근 인구수의 차이를 확인하며 연합이 되는지 안 되는지에 대해 결정하고, 연합인 나라들끼리는 균일한 인구수를 가질 수 있도록 코드를 작성하였습니다.

최단거리를 찾는 문제와 마찬가지로 bfs를 이용하여 문제를 풀되, 가로 혹은 세로로 이어진 형태로 2칸을 차지하는 로봇의 형태의 특수성과 로봇이 직선 이동만이 아닌 회전 이동을 할 수 있다는 점을 고려하여 코드를 구현한다면 문제를 해결할 수 있습니다.

📖 구현(implementation) - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념

나이트가 위치한 좌표에서 '(1) 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기' 및 '(2) 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기'가 가능한 지 확인할 수 있는 코드를 구현하여 문제를 해결하였습니다.

문제에서 제시한 이동 방법을 차근차근 구현함으로써 문제를 해결할 수 있었습니다. 특히 방향을 저장해 놓은 변수 d를 리스트 dx와 dy의 인덱스로 사용함으로써 코드를 보다 간결하게 작성할 수 있었습니다.

우선 점수를 한 자릿수 단위로 끊어 차례대로 리스트 n에 넣습니다. 그 후 리스트 n의 앞쪽 반과 뒤쪽 반을 합하여 같은 경우 “LUCKY”를, 다른 경우에는 “READY”를 출력할 수 있도록 하여 문제를 해결하였습니다.

리스트에 차례대로 알파벳 대문자와 숫자를 넣으면, 알파벳과 숫자가 순서대로 정렬이 된다는 점과 문자로써 읽어온 정수의 아스키코드가 57이하라는 점을 이용하여 문제를 해결하였습니다.

문자열 s의 길이가 n이라 하면, 1부터 n까지의 길이에 대해 문제에서 제시한 압축 변환 방법을 모두 적용해 본 후 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 하는 완전 탐색 알고리즘을 사용하여 문제를 해결하였습니다.

키를 회전하고 이동하며 넣어보는 모든 경우의 수를 계산하는 완전 탐색 방법을 이용하여 문제를 해결하였습니다.

문제에서 제시된 이동 규칙 대로 구현을 하면 해결할 수 있는 시뮬레이션 유형의 문제입니다.

문제에서 제시한 대로 코드를 작성해 나가면 해결할 수 있는 시뮬레이션 유형의 문제입니다.

itertools 모듈 내의 combinations 함수를 이용하여 폐업시키지 않을 치킨집들의 가능한 모든 조합들에 대해서 치킨 거리의 합을 모두 계산할 수 있도록 하였고, 그중 가장 치킨 거리의 합이 작은 경우의 값을 출력할 수 있도록 하였습니다.

주어진 데이터 개수가 적기 때문에 완전 탐색으로 접근할 수 있는 문제입니다. permutations함수를 이용하여 점검하는 친구들의 순서의 모든 경우의 수를 계산하고, 원형인 레스토랑의 형태를 선형으로 고려하기 위해 적절하게 변형을 하여 문제를 해결하였습니다.

📖 정렬(Sorting) - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미

파이썬 리스트의 내장 함수인 sort()를 이용하여 주어진 수열을 내림차순으로 출력할 수 있도록 코드를 구현하였습니다.

파이썬 리스트의 내장 함수인 sort()의 매개변수 key를 이용하여 점수를 기준으로 오름 차순으로 정렬하여 성적이 낮은 순서대로 모든 학생의 이름을 출력하도록 코드를 작성하였습니다.

파이썬 리스트의 내장함수 sort()를 이용하며 배열 a는 오름차순으로, 배열 b는 내림차순으로 우선 정렬하였습니다. 그 후 차례대로 k번째 원소까지만 확인하며 b의 원소가 더 큰 경우에 a의 원소를 b의 원소로 바꿔주는 과정을 구현함으로써 문제를 해결하였습니다.

파이썬 리스트의 내장함수 sort()의 parameter인 key의 사용법을 숙지하고 있다면 해결할 수 있는 문제입니다.

이 문제는 집들의 위치들 중에서 중간값이 되는 위치에 안테나를 설치해야 모든 집까지의 거리가 최소가 된다는 것을 이용하여 해결할 수 있는 문제입니다.

문제에서 정의한 대로 실패율을 계산하고, 파이썬 리스트의 내장 함수인 sort() 함수의 key parameter를 이용하여 실패율을 내림 차순으로 정렬하였습니다. 그 후 실패율이 높은 스테이지 순서대로 answer 리스트에 append() 하여 문제를 해결하였습니다.

작은 크기를 가지는 카드 묶음 2개를 선택하여 비교한 후, 그 2개의 카드 묶음을 하나로 합쳐 다시 카드 리스트에 추가하는 과정을 카드가 한 묶음이 될 때까지 반복해나가면 해결할 수 있는 문제입니다.

📖 이진 탐색(Binary Search) - 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘

최대 1,000,000개의 매우 많은 정수를 입력받아야 할 수도 있기 때문에 이진 탐색 알고리즘을 이용하였습니다.

문제에서 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받는다고 명시해 놓았고, 오름차순으로 정렬되어 있기에 이진 탐색을 활용하여 문제를 해결하였습니다.

모든 원소가 오름차순으로 정렬되어 있으며, 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받는다고 명시되어 있기에 이진 탐색을 이용하여 문제를 해결하고자 하였습니다.

가능한 집의 좌표의 범위가 10억이기 때문에 '가장 인접한 두 공유기 사이의 거리를' 이진 탐색을 이용하여 찾고자 하였습니다.

이진 탐색을 이용하여 각 쿼리마다 매치되는 단어의 개수를 계산해 줌으로써 해결할 수 있는 문제입니다.

📖 다이나믹 프로그래밍(Dynamic Programming) : 메모리 공간을 조금 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법

전형적인 다이나믹 프로그래밍 유형의 문제로, 보텀업 방식(Bottom-Up) 을 이용하여 2부터 오름차순으로 모든 숫자에 대한 최소 연산의 횟수를 계산해나감으로써 최종적으로 구하고자 하는 숫자에 대한 최소 연산 횟수를 구하였습니다.

다이나믹 프로그래밍을 이용하여 왼쪽부터 오른쪽으로 한칸씩 이동해가면서 최댓값을 계산해나가는 방식으로 문제를 해결하였습니다.

다이나믹 프로그래밍을 이용하여 왼쪽부터 차례대로 바닥을 채워나간다고 생각하며 알고리즘을 작성해나가보면 해결할 수 있는 문제입니다.

화폐들끼리 배수의 관계가 아니므로 그리디 알고리즘이 아닌 다이나믹 프로그래밍 알고리즘을 이용하여야 해결할 수 있는 문제입니다.

다이나믹 알고리즘을 이용하여, 오른쪽 위, 오른쪽, 오른쪽 아래로 이동해가면서 해당 위치에서의 금광의 최댓값을 구해나가는 코드를 작성하여 문제를 해결하였습니다.