코딩 기록 저장소

1. 어떤 문제를 동적 프로그래밍으로 푸는가 - 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 재귀적 중복을 해결하는 방법을 뜻함. - 피보나치 수 구하기에 동적 프로그래밍의 개념을 이해할 수 있는 핵심이 모두 들어있음. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 - n의 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치 수를 포함하고 있음. - 이처럼 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조를 가졌다고 함. - 동적 프로그래밍을 적용하려면 문제가 일단 이 성질을 가져야 함. - 간명하지만 때때로 엄청난 비효율을 초래할 수 있음. - 문제의 크기가..

문제 정보 제목 : 주식가격 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42584 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한 사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 ..

1. 연결 리스트를 이용한 집합의 처리 연결 리스트 - 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결함. - 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있음. - 다음 원소를 가리키는 포인터를 이용해 집합의 모든 원소가 연결 리스트로 연결됨. - 각 집합에는 마지막 원소를 가리키는 tail이라는 변수를 둠. 이것은 두 집합을 합칠 때 시간을 절약할 수 있게 해줌. 상호 배타적 집합의 관리를 위해 필요한 세 가지 연산 1. Make-Set(x) : 원소 x로만 구성된 집합을 만듦. - 노드를 하나 만들어 해당 원소를 저장함. 대표 노드로는 자신을 가리키도록 하고, 다음 원소는 없으므로 포인터는 NIL로 해둠. 2. Find-Set(x) : 원소 x를..

문제 정보 제목 : [3차] 압축 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17684 문제 설명 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다. 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다. LZW 압축은 다음 과정..

문제 정보 제목 : 더 맵게 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42626 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scovil..

문제 정보 제목 : 피로도 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/87946 문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해..