본문 바로가기

💻 DEV/Algorithms & Data Structure7

[알고리즘][C++] 트라이 (Trie) 백준 14425: 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 접근 방향 및 디버깅 트라이 구현 - find 를 활용하면 훨씬 시간도 빠르고 구현도 간단한 문제이나, 트라이 자료구조를 학습하는 차원에서 트라이로 구현 - 개별 노드를 담당할 struct 를 구성하고, 단어가 입력될 때마다 각 글자를 트리 형태로 형성 - 단어가 집합에 존재하는지 찾을 때는 구성된 트리를 탐색 - 중요한 점은, 트리를.. 2024. 3. 13.

[알고리즘][C++] 세그먼트 트리 백준 2042: 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 접근 방향 및 디버깅 "범위" 별 재귀 핸들링에 집중 [1] 찾는 범위를 미포함하는 호출일 때 [2] 찾는 범위를 전부 포함하는 호출일 때 [3] 찾는 범위를 일부 포함하는 호출일 때 정수형 데이터 타입 고민 - 문제 조건 중 "입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같.. 2024. 3. 13.

[알고리즘][C++] 우선순위큐, 힙큐 백준 11279: 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 접근 방향 및 디버깅 [1] 최대힙 깡구현 - insert(), pop() 시 트리를 상/하단으로 탐색하여 아이템 간 대소비교를 통해 값 swap 하는 전역 함수 생성 - insert() 시에는 값을 최하단 노드에 추가하여, 부모 노드가 나보다 값이 나보다 클 때까지 swap - pop() 시에는 최상단 값을 제거하고, 자식 노드가 나보다 값이 작.. 2024. 3. 11.

[알고리즘][C++] Dijkstra (다익스트라) / 최단 경로 탐색 백준 5972 : 택배 배송 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 접근 방향 및 디버깅 [1] 최초 접근 - N * N 배열을 만들어 정점별로 연결된 정점과의 거리를 표시하고, 이후 우선순위큐와 Visited 배열을 사용해 탐색을 진행하고자 함 - 해당 접근으로 TC 답은 나왔으나, 메모리가 128 MB 로 제한되어 있어서 약 3% 대부터 메모리 터짐 - 당연함.. N 의 최대값이 50000 이라는 점을 제대로 확인하지 않음 [2] 수정된 접.. 2024. 3. 11.

[Algorithms] 시간복잡도 (Big-O Notation) 란? ✨ 시간복잡도 알고리즘의 로직을 코드로 구현할 때, 입력값에 따라 출력값을 내는데 걸리는 시간의 비율을 의미한다. 시간 복잡도는 보통 Big-O Notation (Big-O 표기법) 을 활용하여 나타낸다. Big-O Notation 이외에도 Big-Omega(big-Ω),Big-Theta(big-Θ) Notation 등이 존재한다. Big-Omega는 알고리즘 효율을 하한선을 기준으로 하고, Big-Theta는 상한선과 하한선의 사이를 기준으로 판단한다. 이에 비해 Big-O 는 알고리즘 효율을 상한선 기준으로 표기하기 때문에 자주 사용된다. 즉, 알고리즘을 실행하는데 걸리는 시간의 최대값을 표기하기 때문에 효율성 점검에 자주 사용된다. 시간 복잡도와 아울러 공간 복잡도 (Space Complexity).. 2021. 7. 8.

[Data Structure] 스택(Stack) 과 큐(Queue) 스택과 큐는 가장 자주 활용되는 자료구조 중 하나이다. ✨ 스택(Stack) 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조이며, 입출구가 하나이다. 후입선출 (LIFO; Last in First Out) 의 구조를 가지고 있다. 삽입과 삭제가 일어나는 위치를 Top 이라고 한다. 비어있는 스택에서 원소를 추출하려고 할 때는 stack underflow, 스택이 넘치는 경우는 stack overflow 이다. ✨스택 예시 모바일 화면의 경우, 사용자가 현재 보고 있는 화면이 Top 이다. 다음 화면 클릭 시, 새 화면을 Stack 에 추가하고 이동한다. 이전 화면으로 돌아갈 시, 현재 화면을 Stack 에서 지우고 이동한다. ✨ 큐(Queue) 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조이며, .. 2021. 7. 7.

[Algorithm] 깊이우선탐색(DFS) 과 너비우선탐색(BFS) DFS 와 BFS 는 각각 Depth-First Search 와 Breadth-First Search 로, 깊이우선탐색과 너비우선탐색을 뜻한다. 둘의 차이점과 코드 구현 방법을 구체적으로 알아보고자 한다. BFS 그래프 자료구조형에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 큐를 이용하여 구현할 수 있다. 구현 단계 큐에 탐색 시작 노드를 삽입한다. 큐의 front 를 방문할 때마다 방문 표시를 하고, popleft() 를 한다. 현재 방문하고 있는 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 큐에 넣는다 현재 방문하고 있는 노드에 방문하지 않은 인접 노드가 없다면 큐의 front 을 꺼낸다 반복 실행하여 큐가 완전히 빌 때 종료한다 from collections import deq.. 2021. 6. 30.

이전 1 다음

티스토리툴바