🎈Recent posts
-
[알고리즘][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.03.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.03.13
-
[TIL] C++ 에서 INF 값 사용하기, 메모리 계산하기, 외
C++ 에서는 최대값을 어떻게 사용하나? - 다른 언어에서는 Number.MAX_SAFE_INTEGER (JS) 라던지 Double.POSITIVE_INFINITY (Java) 라던지 최대 정수를 상수로 사용할 때 쉽게 접근할 수 있었으나 C++ 에서는 이를 어떻게 할지 몰랐음 - 동기의 도움으로 헤더를 쓰면 INT_MAX 값을 사용 가능하다는 것을 알게 됨 - 이외에도 INT_MIN, FLOAT_MAX, CHAR_MAX 등의 유용한 상수가 많은 것으로 보아 종종 사용하게 될 것 같음 2차원 배열의 메모리 크기 구하는 법 - N[50000][50000] 에 달하는 2차원 배열을 만들었다가 (당연하게도) 메모리 초과로 실패했던 문제를 맞닥뜨림 - 배열의 크기를 바이트 단위로 계산하는 법: 배열의 크기 (2..
2024.03.12
-
[알고리즘][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.03.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.03.11
-
How is code allocated in memory?
This post covers the subject "How code is allocated in the computer's memory." Types of Memory When we typically bring up the concept "memory", we usually refer to RAM (Random Access Memory). However the term is not constrained to RAM itself, but rather refers to a broader range which includes both RAM and Disk. # RAM RAM is also known as a computer's primiary memory, and is in charge of running..
2023.06.05