삼성역에서 택시를 타고 강남역으로 향했는데 30분 걸렸다. 구글에서 알려주는 최단경로로 갔더라면 15분내에 도착할 것이다. 레스토랑을 예약해서 가는 경우라던지 친구와 약속 시간을 잡은 경우 우리에게는 시간은 항상 소중하다. 그래서 우리는 시간을 효율적으로 사용하기위한 노력을 의식적으로 하고 있다. 컴퓨터 프로그래밍에서도 시간복잡도가 가장 낮은 알고리즘을 채택해 이러한 상황을 개선하고 있다. 택시를 타고 삼성역까지 가는 절차를 알고리즘이라고 하는데 이때 수행하는 연산의 수를 시간복잡도로 나타낸다. 택시를 타고 강남역까지 가는 과정을 알고리즘으로 표현하면 아래와 같다. function TakeTaxy(from, to) { /* 1. 차량에 탑승한다. 2. from에서 to까지 최단거리 루트를 선택한다. 3...

문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scovil..

재귀(Recusion) 알고리즘이란? 재귀 함수는 자기 자신을 참조하는 함수입니다. 원래의 문제를 동일한 유형의 하위 문제로 나누고 하위문제를 해결한 다음 결과와 결합합니다. 이러한 알고리즘을 분할 정복법이라합니다. 또 하위 결과를 저장하여 조회하는 알고리즘이 추가되면 동적 프로그래밍이라고 부릅니다. 이러한 재귀함수는 다음과 같은 구조를 가져야 합니다. Base Case : 재귀함수의 종료 조건으로 더 이상 문제를 쪼갤수 없을 때, 자기자신을 호출하지 않고 답이 나올 때 Recusion Case : 복잡한 입력을 더 간단한 입력으로 분류하여 자기자신을 호출 재귀의 활용 예시 1. 계수(factorial) 구하기 다음은 factorial 함수는 n!을 구합니다. int factorial(int n) { /..

반복 알고리즘이란? 반복적인 방법으로 문제를 해결하는 알고리즘이다. 반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용한다. 루프 변성이란 반복문을 수행하면서 변하는 성질을 의미하며, 루프 불변성이란 변하지 않는 성질을 의미한다. 예를 들어, start에서 end까지 숫자의 합계를 구하는 문제는 다음과 같은 알고리즘을 갖는다. sum:=0 반복(index:=start -> end) sum := sum + index 반환 sum 위 알고리즘에서 index는 반복문이 실행 될 때마다 start에서 end까지 값이 순차적으로 증가한다. 이처럼 반복문을 수행할 때마다 변하는 성질을 루프 변성이라고 한다. 반대로 sum은 반복문이 몇 번 수행되더라도 start에서 ind..