[DP] Dynamic Programming 알고리즘 알아보기

오늘은 거두절미하고, DP(Dynamic Programming) 알고리즘에 대해서 알아보고자 한다.여기서 설명하는 DP 알고리즘은 동적 할당과는 다른 개념이므로, 착각하지 말자동적할당은 메모리 공간에 동적으로 (런타임에) 변수 공간을 할당한다는 개념이며,동적이라는 것 자체가 프로그램이 실행되는 런타임에 발생한다는 것을 이해하면 된다. DP 알고리즘을 설명할 때 주로 피보나치 수열을 예시로 들곤 한다.피보나치 수열은 특정 점화식으로 반복되는 수열을 의미한다.점화식은 아래와 같다. F(n) = F(n-1) + F(n-2), 단 F(0) = 0, F(1) = 1 이러한 피보나치 수열을 코드로 구현한다면 어떨까? # 재귀를 사용한 피보나치 수열 구현def fibonacci(n): if n  코드는 매우 간..

• format_list_bulleted CodingTest/algorithm
• · 2024. 11. 10.
• textsms

[프로그래머스] 과제 진행하기

문제 설명과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다. 과제는 시작하기로 한 시각이 되면 시작합니다. 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다. 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다. 만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다. 과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주..

• format_list_bulleted CodingTest/programmers
• · 2024. 11. 8.
• textsms

[프로그래머스] 조이스틱 - 파이썬

문제 설명조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다.▲ - 다음 알파벳▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를..

• format_list_bulleted CodingTest/programmers
• · 2024. 11. 7.
• textsms

[프로그래머스] 모의고사 - 파이썬

문제 설명수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요..

• format_list_bulleted CodingTest/programmers
• · 2024. 11. 6.
• textsms

[프로그래머스] 정수 삼각형 - Python

문제설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.  제한사항삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.  입출력 예triangle result[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]30문제풀이DP로 문제를 해..

• format_list_bulleted CodingTest/programmers
• · 2024. 10. 27.
• textsms

자료구조와 알고리즘의 시간복잡도 완벽 정리: 이진트리부터 해시 테이블까지

자료구조와 알고리즘을 이해하는 것은 효율적인 프로그래밍을 작성하는 데 중요한 요소이다.자료구조의 선택에 따라 성능이 크게 달라질 수 있기 때문에,각 자료구조와 알고리즘의 시간복잡도를 잘 파악하는 것이 필요하다. 이 글에서는 파이썬을 기반으로 다양한 자료구조와 알고리즘의 시간복잡도를 코드와 함께 설명하고,삽입, 탐색, 제거와 같은 주요 연산의 시간복잡도를 비교해보고자 한다. 1. 배열 (Array) 배열은 파이썬의 list와 유사하다. 파이썬 리스트는 동적 배열로 구현되어 있으며, 여러 요소를 연속된 메모리 공간에 저장한다.삽입: 끝에 삽입은 O(1)이다. 중간에 삽입은 O(n)이다.탐색: 특정 인덱스를 통해 접근하는 것은 O(1)이다.제거: 특정 인덱스의 요소를 제거하는 경우 O(n)이 걸린다. arr ..

• format_list_bulleted CodingTest/algorithm
• · 2024. 10. 17.
• textsms