Cherry & Cherish

다이나믹 프로그래밍은 동적계획법, DP라고도 한다. 메모리 공간을 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 대표적인 방법 중 하나다. 다이나믹 프로그래밍은 구현의 특별한 코드가 있다기 보다는, 두 가지 방식(탑다운, 바텀업)이 존재한다. 1. 다이나믹 프로그래밍 사용 문제 DP 알고리즘을 적용해 풀어야 하는 문제는 대표적으로 피보나치 수열을 예시로 들 수 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 다시 설정한다. 다시 말해, 점화식으로 문제를 풀어야 하는 것이다. 피보나치 수열은 손쉽게 재귀 문제로 풀 수 있는데, 이렇게 되면 주어진 숫자 n이 커질수록, 기하급수적으로 수행시간이 늘어나게 된다. 따라서 이러한 문제는 다이나믹 프로그래밍으로 해결해야 한다. 2. 다이나믹 프로그래..

그래프 알고리즘은 코딩 테스트 단골 출제 문제는 아니다. 하지만 꼭 알아야 하는 알고리즘 중 하나라고 할 수 있다. 그래프 알고리즘에 대한 팁은 “서로 다른 객체가 연결되어 있다(여러 개의 도시가 연결되어 있다)”라는 표현이 들어가면 대체로 그래프 알고리즘을 활용해야 하는 문제일 가능성이 높다. 또, 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 암기해야 한다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다. 최소힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 그래프의 구현 방법은 2가지 방식이 존재한다. 인접 행렬 : 2차원 배열을 사용하는 방식 인접 리스트 : 리스트를 사용하는 방식 2가지 모두 사용된다. 1. 서로소 집합 1-1. 서로소..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 보통 그래프를 이용해서 표현하고, 각 지점은 그래프에서 노드로 표현되고 지점간 연결된 도로는 그래프에서 간선으로 표현된다. ‘한 지점에서 특정 지점까지의 최단 경로를 구해야하는 경우’, ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’ 등 다양한 사례가 존재한다. 일반적으로 사용하는 최단거리 알고리즘은 ‘다익스트라 알고리즘’, ‘플로이드 워셜 알고리즘’, ‘벨만 포드 알고리즘’ 등 여러 가지가 존재한다. 그러나 코딩 테스트에서 가장 많이 등장하는 유형은 ‘다익스트라’, ‘플로이드 워셜’ 알고리즘이다. 최단 경로 알고리즘은 DP와 그리디가 그대로 적용된다는 특징이 있다. 따라서, 그리디와 DP 유형의 하나로 보는 경우도 있다..

순차탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. count()메서드를 이용할 때도 내부에서는 순차탐색이 수행된다. 또, 특정 값의 원소가 있는지 확인하는 모든 순간에 순차탐색이 사용되며, 구현도 간단하다. def sequential_search(n, target, array): for i in range(n): if array[i] == target : return i + 1 순차탐색은 데이터 정렬 여부와 관계 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다. 따라서, 데이터의 개수가 N개일 때, 비교 연산이 필요하므로 순차탐색의 최악의 경우 시간 복잡도는 O(N)이다. 1. 이진 탐색 개념 💡 이진 탐색 - 정렬이 끝난 데이터를 시작점..

문제 : 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 접근 : 문제에서 준 그대로, 정렬하면 된다. 한 가지 유의 ..

문제 : 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 접근 : 이전에는 이 문제를 조합으로 풀어야 하는지 고민했었다. (당연히 시간 초과 나온다.) 시간 때문에 정렬로 풀려고 접근했고, 처음에는 numbers의 객체를 문자열로 바꾼 뒤에, arr.sort(key=lambda x: x, revers..

문제 : 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 접근 : lambda를 활용하면 아주 손쉽게 풀 수 있다. arr에 추가할때, 알아보기 쉽도록, 국어 영어, 수학, 이름 순서로 append 했다. key=lambda x : (-x[0], x[1], -x[2], x[3])로 설정함으로서, 국어는 감소하고 영어는 증가하고, 수학은 감소하고..

문제 : 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 접근 : lambda를 활용해서 첫 번째 인자인 나이만 정렬하도록 했다. 정렬 문제는 출력 시 타입을 잘 확인해야 한다. 답은 맞는데 type 때문에 실패 처리된 케이스가 있었다. 풀이 : import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): arr.append(list(sys.stdin.readline().split())) arr.sort(key=lambda x: int(x[0])) for i in range(n): print(ar..