전체 글

이것이 코딩테스트다. 220페이지 문제이다. 스키장 3,5,7일권 최저가 구하기 문제와 비슷하다. 다이나믹프로그래밍의 정석 문제 같다. 다이나믹 프로그래밍은 보통 min(나올수있는 경우들) 또는 max(나올 수 있는 경우들)을 이용한다. 이 문제는 바텀업방식문제이다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) food = list(map(int,sys.stdin.readline().split())) dp=[0]*N dp[0]=food[0] dp[1]=max(food[0],food[1]) for i in range(2,N): dp[i] = max(dp[i-2]+food[i],dp[i-1]) print(dp) print(dp[N-1]) 아래는..

이 문제는 이것이 코딩테스트다. 217페이지 문제이다. 문제 난이도는 높지 않았다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) dp=[0]*(N+1) dp[1]=0 dp[2]=1 for i in range(2,N+1): temp = [N] * 4 if i%5 == 0: temp[0] = dp[i//5] + 1 if i%3 == 0: temp[1] = dp[i//3] + 1 if i%2 == 0: temp[2] = dp[i//2] + 1 temp[3]=dp[i-1]+1 dp[i]=min(temp) print(dp[N]) 아래는 예시코드 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 ..

정의 및 장단점 순차탐색(일반적인 탐색)과 달리 이진 탐색은 배열내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 매우 빠른 탐색이다. 탐색범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진탐색은 위치를 나타내는 변수3개를 사용하는데 탐색하고자 하는 범위의 시작점(low),중간점(middle),끝점(high)이다. 찾으려는 데이터와 중간점(mid)위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. log2N의 시간이 걸리고 빅오 표기법에 따라 간단하게 표현하면 O(logN)이다. 탐색대상의 데이터가 큰 문제의 경우 이진탐색을 이용하여 풀어야 한다. 문제조건을 잘 살피자. 이진탐색문제의 경우 이진탐색코드형식을 미리 암기 해놓으면 아주 쉽게 구현할 수..

해시(Hash) 자료구조 해시(Hash) 구조란, 키(Key)와 값(Value) 쌍으로 이루어진 데이터 구조입니다. 해시 구조에서는 Key 를 이용하여 데이터(value)를 빠르게 찾을 수 있는 장점이 있습니다. 파이썬에서 사용하는 dictionary type 이 해시구조입니다. 해시와 관련된 몇가지 용어들에 대해 알아보겠습니다. 키 (Key) : 해시 함수의 input 이 되는 고유한 값. 키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경되어 value 값과 매칭되어 저장소에 저장됩니다. 해시 (Hash) : 임의의 값을 고정 길이로 변환하는 것 key 값 그대로 저장소에 저장되게 되면 다양한 길이의 저장소를 구성해야하기 때문에 효율성을 위해 일관적으로 해시(hash)로 ..

트리 자료 구조중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진탐색트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 예를 들어 다음과 같은 트리가 이진탐색트리이다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 ..

이 문제는 이것이 코딩테스트다 201페이지 문제이다. 이 문제는 구현자체는 쉽지만 입력의 최대값이 20억이여서 최악의 경우 최대 20억의 실행이 발생할 수있다. 그러므로 이진탐색을 사용하여야 한다. 아래는 나의 코드이다. # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n, m = list(map(int, input().split(' '))) # 각 떡의 개별 높이 정보를 입력 array = list(map(int, input().split())) # 이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(array) # 이진 탐색 수행 (반복적) result = 0 while(start mid: total += x - mid # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부..

이 문제는 이것이 코딩테스트다. p197페이지 문제이다. 이진탐색을 이용하지 않고도 쉽게 풀 수 있기만 오늘은 이진탐색을 연습하는 날이기에 이진탐색을 이용하여 풀었다. 이진탐색을 구현할 수만 있다면 문제의 난이도는 쉽다. 아래는 나의 코드이다. import sys seller_N = int(sys.stdin.readline().rstrip()) seller = list(map(int,sys.stdin.readline().split())) customer_N=int(sys.stdin.readline().rstrip()) customer=list(map(int,sys.stdin.readline().split())) seller.sort() def search(searchList,target): low=0 h..

정의 및 장단점 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 있어야 한다. 정렬 알고리즘은 굉장히 다양한데 대표적인 몇가지만 설명하겠다. 여러정렬은 각각의 장단점이 존재한다. 각 상황에 맞는 정렬을 선택하여야한다. 일반적으로 라이브러리에서 제공하는 정렬은 퀵소트 또는 변형된 퀵소트이다. 평균 nlogn에서 n^2의 시간복잡도를 가진다. 기수정렬: O(N) 또는 O(N+K) N은 개수, K는 숫자범위크기 (ex. 0~99면 100) 계수정렬: O(N) 또는 O(N+K) N은 개수, K는 최대자리수 선택 정렬(selection) 선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾..