Processing math: 100%

본문 바로가기

전체 글79

[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.

[Coding Test][Python] Heap(Min Heap / Max Heap) Priority Queue 개념 및 예제(백준 2075번 N번째 큰 수) ※ Heap 이란? Complete Binary Tree(완전 이진 트리)로 구성된 특수한 자료구조이다. Heap은 Priority Queue를 구현하기 위해 사용된다.Heap 종류 Max Heap(최대 힙)부모 노드의 값이 자식 노드의 값보다 크거나 같은 TreeMin Heap(최소 힙)부모 노드의 값이 자식 노드의 값보다 작거나 같은 TreeMin - Max HeapMin Heap과 Max Heap을 동시에 만족하는 자료구조짝수 Level은 Min Heap을 따르고, 홀수 Level은 Max Heap을 따른다.Root Node는 최솟값을 제공하고, 그 자식 노드들은 최대값을 제공한다.Min Max Heap을 통해 최상위 레벨에서 최소값과 최대값을 빠르게 추출할 수 있는 장점이 있다.Sibling 간의.. 2025. 1. 30.

[Coding Test][Python] Dynamic Programming(DP) 개념 및 예제 ※ Dynamic Programming(DP, 동적 프로그래밍) 란?DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 재사용하여 큰 문제를 해결하는 알고리즘이다. 즉, 동일한 하위 문제가 반복되는 문제에서 효율적이다. DP 주요 개념Optimal Substructure(최적 부분 구조)문제를 작은 하위 문제들로 나눌 수 있으며, 하위 문제의 최적 해를 사용하여 전체 문제의 최적 해를 구할 수 있어야한다.ex) 피보나치 수열 :

$F(n) = F(n-1) + F(n-2)$ Overlapping Subproblems(중복 부분 문제)동일한 하위 문제가 여러번 반복해서 나타나는 경우, 이를 저장해 재사용하면 계산량을 줄일 수 있다.ex) 피보나치 수열의

$F(5)$ 를 계산할 때

$F(4), F(3)$ 을.. 2025. 1. 27.

[Coding Test][Python] Graph 개념 및 Graph 순회 예제 ※ Grapn 란?그래프

$G(V, E)$ 는 객체와 객체 간의 관계를 표현하기위한 자료구조이다. Graph는 객체를 표현하는 Vextex의 집합 V와 이들을 연결하는 Edge의 집합으로 구성된다. 그래프의 기본 구성요소Vertex(Node)그래프를 구성하는 기본 요소데이터의 단위를 표현한다Vertex의 집합은 일반적으로 V로 표시한다Edge두 Vertex를 연결하는 선 또는 관계를 의미한다방향성, 가중치 등에 따라 다양한 특성을 가질 수 있다Edge의 집합은 일반적으로 E로 표시한다그래프의 종류Undirected Graph(무방향 그래프)Edge에 방향이 없다. 즉, Vertex

$u$ 와

$v$ 가 연결되어있다면, 서로 연결된 상태이다.Directed Graph(방향 그래프)Edge에 방향이 있다. 즉,.. 2025. 1. 27.

[Coding Test][Python]Tree 개념 및 Tree 순회(Inorder, Preorder Postorder) 구현 ※ Tree 란?데이터를 계층적으로 구성하고 관리하는 자료구조이다.서로 연결된 Node들로 구성되며 Cycle이 없는 Graph이다. Tree 용어 정리Node : Tree는 보통 node로 구현Edge : Node 간에 연결된 선Root Node : Tree는 항상 Root Node에서 시작Leef Node : 더이상 뻗어나갈 수 없는 마지막 노드Parent Node : 다른 노드와 연결되어 Child Node를 가진 NodeChild Node : Parent Node에서 파생된 NodeSibling Node : 같은 Level에 있는 NodeDegree : 각 노드가 갖는 Child Node의 수, 모든 Node의 Degree가 n개 이하인 Tree를 n진 Tree라고 한다Ancestor(조상) : .. 2025. 1. 27.

이전 1 2 3 4 5 6 ··· 9 다음

티스토리툴바