본문 바로가기

All posts123

[알고리즘][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.
[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. 3. 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. 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.
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. 6. 5.
대형배포 끝 (?), 그렇게 9개월차가 되다 - part 1. 🌟 신입 개발자 적응기 / 4, 5, 6, 7 월 지난 4월부터 생각했던 것보다 무척이나 바쁜 시기를 보냈다. 우리 팀은 서비스 개발 조직이다보니 아무래도 산출된 일정에 맞춰 기능을 개발하기 위해 일일 근무량을 초과하는 경우가 많다. 그런데 3월부터 투입되었던 프로젝트는 기능 한 두가지를 추가하거나 개선하는 것이 아니라 전체 서비스 리뉴얼 + 이를 위한 대규모 마이그레이션 + 몇 가지 기능 추가/개선이 목적이다보니 팀원 모두가 기존보다 더 강도 높은 업무량을 소화하며 달려왔다. (5, 6월은 다들 주말, 공휴일에도 쉬지 못하고 일했으니..) 불행인지 다행인지 글을 올리는 오늘은, 드디어 그간의 작업들을 배포하는 날이다. 덕분에 나도 이제서야 그동안 배우고 느꼈던 점들을 여유롭게 정리할 수 있는데... 과.. 2022. 8. 1.
공부를 제발 더 열심히 하자 🌟 신입 개발자 적응기 / Week 17 ~ 23 : 개발을 잘하고 싶다. 잘하려면 어떻게 해야 하는가. 공부를 더 열심히 하면 된다. ㅇㅋㅇㅋ 💫 리팩토링 스터디 아무도 시키지 않았지만 팀 내 JS 개발자들과 함께 책을 읽고 토론을 하는 스터리를 열었다. 지금까지 약 6번의 스터디 세션을 진행했는데, 각 스터디 세션은 내가 예상했던 것보다 훨씬 유익하고, 유의미했다. 그 이유는 간단히 정리하자면 다음과 같다. 하나, 우리 코드에 대해 온전히 '고민' 만을 하는 시간을 마련할 수 있었다. 책을 읽을 때는 책의 내용을 이해하느라, 평소 업무를 볼 때는 빠르게 처리할 일들을 해치우느라 코드의 질을 높이는 방법에 대해 차분히 고민하기 쉽지 않다. 그런데 스터디를 위한 토론 주제를 준비하고, 다른 사람들이 올린.. 2022. 4. 4.
일을 잘한다는 허상 이것은 잃어버린 10주... 의 기록이다... Week 6 이후로 갑자기 회사 일도 많아지고 개인적인 일도 계속 밀려와 정신이 없었다. 지난 주에 큰 일 하나를 치르고 드디어 마음에 여유가 조금 생겨 다시 신입 적응기에 힘을 써보려 한다. 많이 밀린 만큼 지난 시간 동안 느꼈던 점들, 그리고 크게 배웠던 점들 위주로 기술하며 다시 개발자로서의 성찰을 해보자. 🌟 신입 개발자 적응기 / Week 7 ~ 16 : 일을 잘한다는 허상 💫 초보들이 일을 두 번 하는 이유 보통 일을 잘하는 사람들은 한 번에 빠르고 정확하게 처리하며, 그렇지 않은 사람들은 시간을 더 들여도 결과물이 그에 못 미치는 경우가 많다. 그리고 보통 초보들은 일을 잘 못한다. 아직 개발 주니어로써, 그리고 업무에 익숙해져 가는 신입으로써 .. 2022. 2. 15.

티스토리툴바