반응형 coding test15 [Coding Test][Python][백준] BOJ #1466 지름길 문제)매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.세준이가 운전해야 하는 거리의 최솟값을 출력하시오.입력)첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.출력)세준이가 운전해야하는 거리의 .. 2025. 2. 5. [Coding Test][Python][백준] BOJ #20922 겹치는 건 싫어 문제)홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K$K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. $100\,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다. 이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.입력)첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)출력)조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.. 2025. 2. 5. [Coding Test][Python][백준] BOJ #17266 어두운 굴다리 문제)인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다. 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다. 인천광역시에서 가로등을 설치할 개수 M과 각 가로등의 위치 x들의 결정을 끝냈다. 그리고 각 가로등은 높이만큼 주위를 비출 수 있다. 하지만 갑자기 예산이 부족해진 인천광역시는 가로등의 높이가 높을수록 가격이 비싸지기 때문에 최소한의 높이로 굴다리 모든 길 0~N을 밝히고자 한다. 최소한의 예산이 들 높이를 구하자. 단 가로등은 모두 높이가 같아야 하고, 정수이다. 다음 그림을 보자.가로등.. 2025. 2. 4. [Coding Test][Python][백준] BOJ #11723 집합 (input() vs sys.stdin.readline()) 문제)비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)all: S를 {1, 2, ..., 20} 으로 바꾼다.empty: S를 공집합으로 바꾼다.입력)첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에.. 2025. 2. 4. [Coding Test][Python] Exhaustive Search(완전 탐색)(Backtracking)개념 및 예제(순열, 조합, 부분집합) ※ Exhaustive Search(완전 탐색) 란?Exhaustive Search(완전 탐색)는 가능한 모든 경우의 수를 탐색하여 정답을 찾는 알고리즘 기법이다.특징완전성(Completeness) : 가능한 모든 경우를 확인하므로, 반드시 정답을 찾을 수 있다.비효율성(Inefficiency) : 최악의 경우 계산량이 급격히 증가하여 실행시간이 길어질 수 있다.단순성(Simplicity) : 구현이 쉽고 직관적이다.적용방법Iterative Approach : 단순 반복문을 통해 확인한다.Recursive Approach : Backtracking 기법과 함께 사용되어 불필요한 탐색을 줄일 수 있다.Bitmasking : 이진수 표현을 이용해 모든 경우의 수를 탐색할 수 있다.1. Backtracking.. 2025. 2. 4. [Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제 1. Dijkstra Algorithm 이란?Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적으로 갱신하며 계산한다. 탐색은 "이미 방문한 Node"와 "방문하지 않은 Node"를 구분하여 진행되며, 방문한 Node로 가는 경로 중에서 가장 짧은 경로를 선택해 나간다. 알고리즘 동작 과정1) Adjance List & Priority Queue 사용Priority Queue에 시작 Node 추가우선 순위가 가장 높은(Distrance가 가작 작은) Node 추출방문 여부 확인Distance Update현재 Node에 연결된 Node를 Prio.. 2025. 1. 30. 이전 1 2 다음 반응형
