알고리즘

동적 계획 알고리즘

동적 계획법이란? - 복잡한 문제를 푸는 알고리즘의 한 종류 - 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결한 뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다. - 이 때 계산한 작은 문제의 값을 저장해 두는 메모리를 캐시(cache)라고 부른다. 동적 계획법의 조건 Overlapping Subproblem : 겹치는 부분(작은) 문제 (중복되는 부분문제) 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있음 재귀 알고리즘 피보나치 수열이 대표적인 예시 Optimal Substructure : 최적 부분구조 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 설계될 수 있음 문제의 정답을 작은 문제의 정답에서부터 구할 수 있다. 그리디 알고리즘의 유용성을 판별하는데 사용되기도 한다...

[알고리즘/개념정리] 2. 알고리즘이란?

2-1 알고리즘이란 알고리즘이란? 알고리즘의 일반적 특성 정확성 알고리즘은 입력값에 대해 항상 올바른 로직을 거쳐 올바른 해를 주어야 한다. 수행성 컴퓨터 내에서 모든 단계가 수행 가능해야 한다. 코드로 바꿀 수 없다면 컴퓨터에서 수행 가능한 알고리즘이 아니다. 유한성 너무 오래 걸린다면 알고리즘으로써의 가치가 없다. 일정 시간 내에 종료되어야 한다. 효율성 커지면 커질수록 더 오래 걸린다면 효율적이라고 볼 수 없다. 입력값이 크면 클수록 점점 적은 시간이 걸리는 것이 효율적이다. 시간복잡도 2-2 최초의 알고리즘 유클리드의 최대공약수 알고리즘 곱셈을 통해 푸는 방법 12 → 12 x 1 , 6 x 2, 4 x 3 30 → 30 x 1, 15 x 2, 10 x 3, 6 x 5 공약수 중 가장 큰 것이 최..

[백준/파이썬] 1100 하얀 칸

문제 체스판은 8×8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄부터 8개의 줄에 체스판의 상태가 주어진다. ‘.’은 빈 칸이고, ‘F’는 위에 말이 있는 칸이다. 출력 첫째 줄에 문제의 정답을 출력한다. 예제 입력 1 .F.F...F F...F.F. ...F.F.F F.F...F. .F...F.. F...F.F. .F.F.F.F ..FF..F. 예제 출력 1 1 예제 입력 2 ........ ........ ........ ........ ........ ........ ........ ........ 예제 출력 2 0 count = 0 ..

[백준/파이썬] 1076 저항

문제 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. 색값곱 black 0 1 brown 1 10 red 2 100 orange 3 1,000 yellow 4 10,000 green 5 100,000 blue 6 1,000,000 violet 7 10,000,000 grey 8 100,000,000 white 9 1,000,000,000 예를 들어, 저항의 색이 yellow, violet, red였다면 저항의 값은 4,700이 된다. 입력 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 위의 표에 있는 색만 입력으로 주..

[백준/파이썬] 1075 나누기

문제 두 정수 N과 F가 주어진다. 지민이는 정수 N의 가장 뒤 두 자리를 적절히 바꿔서 N을 F로 나누어 떨어지게 만들려고 한다. 만약 가능한 것이 여러 가지이면, 뒤 두 자리를 가능하면 작게 만들려고 한다. 예를 들어, N=275이고, F=5이면, 답은 00이다. 200이 5로 나누어 떨어지기 때문이다. N=1021이고, F=11이면, 정답은 01인데, 1001이 11로 나누어 떨어지기 때문이다. 입력 첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. F는 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 마지막 두 자리를 모두 출력한다. 한자리이면 앞에 0을 추가해서 두 자리로 만들어야 한다. 예제 입력 1 복사 1000..

알고리즘 시간복잡도로 평가하기

주요 시간 복잡도 총정리 O(1), O(lgn), O(n), O(nlgn), O($n^2$), O($n^3$) 정도가 많이 사용되고, 나머지는 흔치 않습니다. O(1) O(1)은 인풋의 크기가 소요 시간에 영향이 없다는 뜻입니다. Tip♤ 반복문이 없으면 대체로 O(1) 입니다. O(n) # O(n) 함수 def print_each(my_list): for i in range(len(my_list)): print(my_list[i]) 반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n) 입니다. # O(n) 함수 def print_half(my_list): for i in range(len(my_list) // 2): print(my_list[i]) n번 반복하는 게 아니라 n/2번..

[Python] 구명보트 - 프로그래머스 코딩테스트

문제 설명 더보기 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성..

1. 선형 탐색과 이진 탐색

선형 탐색(Linear Search)색(Linear Search) 선형 탐색이란, 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘입니다. 선형 탐색 알고리즘 def linear_search(element, some_list): for i in range(len(some_list)): if element == some_list[i]: return i return None i = 0 부터 끝까지 순서대로, 해당 인덱스의 값과 element가 같은지 비교합니다. 이진 탐색(Binary Search) 이진 탐색이란, 리스트의 중앙값을 계속 확인하며 특정값과 비교하는 방법입니다. 이진 탐색 알고리즘 * 주의 할 점은, 이진 탐색 알고리즘은 list가 sort 되어 있는 상태에서만 가능하다는 것입..