본문 바로가기

전체 글99

[알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python) [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘을 듣고 정리한 내용입니다. 최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘을 의미한다. - 다양한 문제 상황 1. 한 지점에서 다른 한 지점까지의 최단 경로 2. 한 지점에서 다른 모든 지점까지의 최단 경로 3. 모든 지점에서 다른 모든 지점까지의 최단 경로 - 각 지점은 그래프에서 노드로 표현한다. - 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. - 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다. .. 2024. 3. 28.
[백준 2293번] 동전 1 (Python) 문제 링크 [백준 2293번] 동전 1 문제 요약 n가지 종류의 동전으로 합이 k원이 되는 경우의 수 구하기 접근 방법 정리 DP를 풀 때 중요하다고 강조했던 2가지를 생각해서 접근한다. 1. 큰 문제를 작은 문제로 나눠 작은 문제의 합으로 풀 수 있는지를 고민해야하고 2. 동일한 작은 문제를 반복적으로 해결할 수 있는지 고민 1번에 해당하는 것은 합이 k원을 구하는 큰 문제에서 각 금액을 만들 수 있는 경우의 수를 차례대로 계산해나가는 것이다. 2번에 해당하는 것은 1번으로 구해놓은 정보를 바탕으로 반복문을 수행해 DP 배열을 업데이트 한다. 코드 n, k = map(int, input().split()) nums = [int(input()) for _ in range(n)] dp = [0 for i .. 2024. 3. 27.
[알고리즘 개념 정리] 다이나믹 프로그래밍 (Python) [이것이 코딩 테스트다 with Python] 28강 다이나믹 프로그래밍 개요를 듣고 정리한 내용입니다. 다이나믹 프로그래밍 (= 동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 메모이제이션 : 한번 계산한 결과를 메모리 공간에 메모하는 기법이다. 즉, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 2가지 방식(top-down과 bottom-up)으로 구성된다. top-down(메모이제이션) 방식 (=하향식): 재귀함수를 이용함 bottom-up 방식 (=상향식): 반복문을.. 2024. 3. 27.
[백준 11404번] 플로이드 (Python) 2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python) 플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥 문제 링크 [백준 11404번] 플로이드 문제 요약 도시들 사이의 최단 거리를 구하는 문제로, 도시 간 이동 비용을 최소화하는 것이 목표 첫번째 줄에 도시의 개수 n이 주어진다 (2 2024. 3. 26.
[백준 1389번] 케빈 베이컨의 6단계 법칙 (Python) 2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python) 플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥 문제 링크 [백준 1389번] 케빈 베이컨의 6단계 법칙 문제 요약 지구에 있는 모든 사람들은 최대 6단계 이내에 서로 아는 사람으로 연결될 수 있다는 케빈 베이컨의 법칙 이론을 바탕으로 하는 문제다. 케빈 베이컨의 수란, 한 사람이 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합을 의미한다. 백준 유저 사이에서 케빈 베이컨의 수가 가장 작은 사람을 찾아 출력하는 것이 목표다. (만약, 그런 사람이 여러 명이면 번호가 가장 작은 사람을 출력) 유저의 수 n과 친구 관계의 수 m이 주어진다. 이어서 m개의 줄에 걸쳐.. 2024. 3. 26.
[알고리즘 개념 정리] 플로이드 워셜 (Python) [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘을 듣고 정리한 내용입니다. 플로이드 워셜 알고리즘 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. - (다익스트라 알고리즘과 마찬가지로) 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만, 다익스트라 알고리즘과 달리 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다. - 2차원 테이블에 최단거리 정보를 저장한다. - 다이나믹 프로그래밍 유형에 속하며, 시간 복잡도는 O(n³)이다. - 노드의 갯수가 적은 경우에 사용이 적합하며, 노드와 간선의 갯수가 많은 경우에는 다익스트라 알고리즘을 활용해야하는 경우가 많다. 실제로도 .. 2024. 3. 25.
[백준 2573번] 빙산 (Python) 그래프 탐색(DFS, BFS)과 추가적인 구현이 필요한 문제였다. 문제 링크 2573번 빙산 문제 요약 이 문제는 지구 온난화로 인해 북극의 빙산이 녹고 있는 상황을 배경으로 한다. 빙산을 2차원 배열에 양의 정수로 표시하여, 각 부분별 높이 정보를 배열의 각 칸에 저장한다. 빙산이 아닌 바다에 해당되는 칸에는 0이 저장된다. 빙산의 높이는 동서남북 네 방향으로 0이 저장된 칸의 개수만큼 매년 줄어든다. 한 덩어리의 빙산이 주어졌을 때, 이 빙산이 두 덩어리 이상으로 분리되는 시간(년)을 구하는 것이 문제의 목표. 입력: 첫 줄에는 2차원 배열의 행과 열의 개수(N, M)가 주어지고, 그 다음 N개의 줄에는 M개의 정수가 주어지며, 이는 빙산의 높이 정보 출력: 빙산이 두 덩어리 이상으로 분리되는 최초.. 2024. 3. 11.
[백준 14501번] 퇴사 (Python) 다이나믹 프로그래밍을 활용하여 푸는 문제이다. (DP? 나에겐 너 무 어 려 워 😭) 점화식 세우는게 반복되는 규칙성있는 로직을 파악하지 않고서야 감도 안잡히기 때문에 자꾸 DP문제에 그리디로 접근하게 되는 부족함이 있다. 하다하다 안되어서 뤼튼과 함께했다. → 이해를 목표로 다시 정리! 문제 링크 14501번 퇴사 (똑같은 문제, 15486번 퇴사2) 문제 요약 재택 근무 중인 백준이가 퇴사까지 남은 N일 안에 상담을 통해 얻을 수 있는 최대 수익을 계산하는 문제 상담을 완료하는 데 필요한 기간 ( T_i )와 상담을 통해 얻을 수 있는 수익 ( P_i )가 주어진다. 상담 기간이 퇴사일을 넘기면 안 되고, 한 번에 한 개의 상담만 진행할 수 있다. 필요 항목 정리 퇴사까지 N일 날짜별로 얻을 수 있는.. 2024. 3. 7.
Swift 심화 학습하기 (프로토콜, Never 타입, #keyPath와 #selector, 메타타입, availability) 프로토콜 Equatable 프로토콜 동일성 비교를 위한 프로토콜이다. 스위프트에서 제공하는 기본타입은 모두 채택하고 있다. 아래 메서드 구현이 해당 프로토콜의 요구사항이다. static func == (lhs: Self, rhs: Self) -> Bool 구조체, 열거형의 경우 Equatable 프로토콜 채택 시 모든 저장 속성이 Equatable 프로토콜을 채택한 타입이라면 비교연산자 메서드가 자동 구현된다. 단, 예외 케이스가 몇 가지 존재한다. 1) 클래스는 인스턴스를 비교하는 항등연산자(===)가 존재하기 때문에 비교연산자(==)는 개발자에게 구현이 위임된다. 2) 열거형의 경우 연관값이 없다면 기본적으로 Equatable, Hashable하기 때문에 Equatable 프로토콜을 채택하지 않아도 .. 2023. 8. 30.

티스토리툴바