[Algorithm] 그래프 탐색 알고리즘 - BFS & DFS
2024. 8. 16. 11:31
CS/Algorithm
"그래프 탐색"이란 그래프에서 하나의 노드를 시작으로 다수의 노드를 방문하는 알고리즘을 말한다. 이때, 방문하는 노드는 딱 한 번씩만 방문하는 것이 특징이다.만약, 자료구조 그래프에 대한 내용이 궁금하다면 아래 포스팅을 참고 바란다.https://seokyoungg.tistory.com/94 [Data Structure] Graph"그래프"(Graph)는 각 데이터와 그들을 잇는 선들로 이루어진 ADT이다. 각 데이터들을 "정점"(vertex) 혹은 "노드"(node)라 부르며, 이들을 잇는 선을 "간선"(edge)라 부른다. 즉, 그래프는 유한한 개수의seokyoungg.tistory.com 이러한 그래프 탐색 알고리즘에는 2가지가 있다. BFSDFS BFS"BFS"는 Breadth-first Sea..
[Algorithm] 정렬 알고리즘(2) - 머지 소트, 퀵 소트, 기수 정렬
2024. 8. 12. 16:12
CS/Algorithm
이전 포스팅에서 살펴본 정렬 알고리즘들은 평균, 최악의 경우 $O(n^2)$의 시간복잡도를 가지게 되었다. 병합 정렬 (Merage Sort)"병합 정렬"(또는 합병 정렬)은 문제를 분할하고, 문제를 정복하여 합치는 분할정복을 기반으로 한 정렬 알고리즘이다. 정렬 과정이러한 분할정복은 "하향식"과 "상향식"구현으로 구분할 수 있는데,병합 정렬에선 하향식 구현방식을 대부분 사용한다. 하향식(TopDown)방식으로 구현한 병합 정렬의 과정은 다음과 같다. (아래 그림은 정확한 Top-Down 방식은 아니지만, 분할되고 정복되는 순서만 차이 있을 뿐, 방법은 동일하다.)리스트를 절반으로 나누어 두 부분 리스트로 나눈다. 이를 부분 리스트의 길이가 1이하가 될 때까지 재귀적으로 위의 과정을 반복한다. (길..
[Algorithm] 정렬 알고리즘(1) - 버블정렬, 선택정렬, 삽입정렬
2024. 7. 10. 17:25
CS/Algorithm
"정렬 알고리즘"은 일련의 원소들에 대해 정해진 규칙에 맞게 재배열하는 알고리즘이다. 정렬 알고리즘은 현대까지도 계속 발명 될 정도로, 많은 알고리즘이 존재하지만 이중 대표적으로 몇가지만 살펴볼것이다. 정렬 알고리즘 분류 기준정렬 알고리즘은 여러 기준으로 분류된다. 안정 정렬 vs. 불안정 정렬 "안정 정렬"이란, 정렬조건이 동일한 원소가 여러개 있을 때, 입력 때와 동일한 순서로 정렬되는 정렬 알고리즘이다.반면, "불안정 정렬" 입력 때와 동일한 순서로 졍렬되는 것을 보장하지 않는다. "안정 정렬"은 정렬조건이 동일한 원소들의 순서를 보장해야할 때, 유용하게 사용될 수 있다. 예를 들어, 온라인 쇼핑몰에서 구매자의 구매 요청이 요청 순서대로 쌓인다고 가정해보자. 이때, 등급이 높은 회원부터 배송..
[Algorithm] 알고리즘이란?
2024. 7. 8. 13:00
CS/Algorithm
수학 혹은 컴퓨터 과학(Computer Science)에서 "알고리즘"이란 어떠한 문제를 풀기 위한 "유한한 갯수의 일련의 시퀀스"이다. 이때, 알고리즘은 컴퓨터 프로그램으로 대부분 구현되나, 전기 회로 혹은 기계 등등 다른 수단으로도 구현될 수 있다. 특성 앞서 알고리즘을 "유한한 갯수의 일련의 시퀀스"라고 정의했지만, 여기서 몇가지 조건이 더 붙는다. 입력 : 잘 정의된 입력들을 받아들일 수 있어야 한다.출력 : 정확성을 추론할 수 있는 출력이 있어야 한다.명확성 : 각 단계는 명확하게 정의되어야 한다. 각 단계에서 수행할 작업을 정확하게 지정할 수 있어야 한다. 유한성 : 유한한 수의 명령어의 시퀀스가 수행되면 반드시 종료되어야 한다.유효성 : 모든 명령어는 실행 가능해야 한다. 알고리즘 평가 "..
[PS] BOJ 2457 (공주님의 정원)
2024. 6. 23. 22:26
CS/Algorithm
문제부터 살펴보면 3월 1일부터 11월 30일까지 꽃이 지지 않게 하는 것이 핵심이다. 이때의 입력은 각각 꽃이 피는 날과 꽃이 지는 날이 들어온다. 1번째 접근우선, 가장 먼저 생각나는 것은 특정 날짜 이전에 피는 꽃 중 가장 늦게 피는 꽃을 매 시행시 구하면 된다. 하지만, 매 시행 시 $N$개의 꽃을 살펴보게 되기 때문에, 시작 복잡도는 $O(N^2)$이 된다. 해당 문제에서 $N$은 최대 100,000이기 때문에, $O(N^2)$은 시간 초과가 발생하게 된다. 2번째 접근 매 시행시 특정 날짜 이전에 피는 꽃 중 가장 늦게 피는 꽃을 상수 혹은 로그 시간에 구할 수만 있게 된다면, 시간초과가 발생하지 않고 문제를 해결할 수 있게 된다. 이와 같이 그리디 한 풀이로 접근하면, 매 시행마다 꽃이..
[PS] BOJ 1539(이진 검색 트리)
2024. 6. 18. 23:08
CS/Algorithm
https://www.acmicpc.net/problem/1539 문제 접근가장 먼저 생각할 수 있는 방법은 BST를 직접 구현해, 삽입될 때마다 위치를 확인하는 방법이다. 하지만, N = 250,000이고, BST가 편향 트리가 되는 경우 탐색 시간은 $O(logN)$이 아닌, $O(N)$이 되게 되어, 최종 시간 복잡도는 $O(N^2)$으로 시간초과가 발생하게 된다. 그렇다면, Self-Balancing 트리를 사용하면서 BST상에서 노드의 높이를 알 수 있어야만 한다. 이때, 노드가 삽입될 때, 부모 노드의 높이를 알 수만 있다면, 각 노드의 높이를 계산할 수 있을 것이다. 따라서, Self-Balancing 트리에서 새로운 노드가 삽입되는 부모 노드를 알아야 한다. 트리에서 새로운 노드는 "자..
[PS] BOJ 1019(책 페이지) - C++
2024. 4. 6. 21:05
CS/Algorithm
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 10의 자릿수가 변할 때마다, 1의 자리 0~9까지가 반복된다. 또한, 100의 자릿수가 변할 때마다, 0~99의 숫자가 반복된다. 즉, 각 자릿수마다 특정 패턴들이 반복된다. 각 자릿수 별로 등장하는 패턴들을 예시를 통해 살펴보자. N이 32698723이라고 가정하고, $10^6$의 자릿수에서의 숫자들의 등장 횟수를 살펴보자. 경우의 수는 다음과 같이 나누어진다. N의 $10^6$자릿수보다 작은 경우 N의 $10^6$자릿수보다 큰 경우 N의 $10^6$자릿수와 ..