B_log

문제 풀이 과정의 고민 시뮬레이션으로 문자열을 직접 탐색하는 것도 방법일 수 있다고 생각했어요. DFS처럼 탐색하지만 탐색 조건을 변경하면서요. 하지만 그런 방식은 상황이 너무 복잡해지고 작은 디테일에서 오류가 쉽게 발생할 수 있다고 생각해서 노드를 직접 만드는 것으로 생각했어요. 이 글에서 전위, 중위, 후위 순회에 대한 설명을 하진 않을 계획이에요. 다만, 각 탐색 메서드에서 명백하게 출력의 우선순위를 보여주는 것이 중요하다고 생각해요. 전위는 말 그대로 부모 노드의 데이터를 먼저 보여주는 것, 중위는 왼쪽 노드부터 탐색한 후 부모 노드의 값을 출력해주고 오른쪽 노드를 탐색하는 것처럼이요. 언어를 조금 고민했어요. 파이썬 풀이도 추가로 올릴 예정이지만, 아무래도 Node 클래스를 이용해 풀이하는 데에..

문제 풀이 과정의 고민 이 문제는 단순한 구현 문제가 아니라 Union Find의 개념을 이해해야 풀기 쉬웠어요. Union Find의 개념을 간단히 설명해볼게요. 키 포인트는 노드 간에 부모 - 자식 관계를 만드는 거예요. 즉, 같은 그룹인지 확인하는 방법을 같은 부모를 가지고 있는지 확인하는 것으로 대신하는 거죠. 쉽게 생각하면 같은 그룹에 속할 경우 그 요소들에 그룹 번호를 부여한다고 볼 수도 있는데, 그 그룹 번호가 새롭게 생성되는 것이 아닌 특정 요소를 부모로 해서 그 요소 자체를 그룹 번호로 설정하는 거예요. 예시를 통해 살펴볼게요. 아래와 같이 4개의 노드가 존재한다고 가정해요. 이 상태에서는 어떤 연결도 없기 때문에 각 노드의 부모는 자기 자신이 될 거예요. 노드 1 2 3 4 부모 1 2..

문제 풀이 과정의 고민 출력할 문서의 위치를 어떻게 이동시킬지 고민했어요. 방법은 다양할 수 있는데, 출력 위치가 0번 인덱스로 고정되어 있기 때문에 원형 큐처럼 인덱스를 따라 돌게 만들기로 했어요. enumerate를 통해 인덱스와 중요도를 튜플로 묶으면 생각하기 편하긴 하지만 자료의 수가 늘어날수록 성능에 영향을 미치게 되어 정수 하나의 인덱스로 관리하는 게 더 낫다고 판단했어요. 파이썬에서 제공하는 기본 리스트 자료구조의 경우 내부적으로 더블 링크드 리스트이지만 사용 시 스택처럼 작동하기 때문에 pop(0)을 사용하는 것을 피하려고 했어요. 인덱스 1번부터 요소가 존재한다면 전부 시프팅이 일어나기 때문이에요. 그래서 대안으로 생각한 것은 주어진 자료구조를 reverse 해 pop(0)가 아닌 pop..

📎 간략한 문제 정리 파일을 이름으로 검색할 때 하나의 검색어로 여러 파일을 검색해야 할 경우가 있습니다. 결과가 주어지고 이 결과를 얻기위해 입력해야하는 가장 짧은 검색어를 입력하는 문제입니다. 📈 문제 분석 파일 이름들의 길이가 모두 동일하고 정규표현식처럼 압축 표현 등 다양한 옵션이 없이 물음표만으로 표시합니다. 전체 순회를 통해 검색 가능합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 글자 압축의 옵션이 있다면 조금 더 복잡한 문제가 되겠지만 이 경우는 상대적으로 매우 쉬웠습니다. 특정 위치를 관찰할 때 모든 글자에서 같은 알파벳이라면 그 알파벳을 추가하고 아니면 물음표를 추가합니다. 💻 풀이한 코드 from sys import stdin input = stdin.readline N = int(in..

📎 간략한 문제 정리 주어진 수열에서 요소가 오름차순이 되는 부분 수열 중 가장 길이가 긴 부분 수열의 길이를 구합니다. 📈 문제 분석 DP에서 가장 유명한 문제 중 하나로 일반적으로 DP로 해결합니다. 하지만 이 문제는 DP로 풀 경우 속도 이슈가 발생합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 from sys import stdin input = stdin.readline N = int(input()) A = list(map(int, input().split())) dp = [1 for _ in range(N)] for i in range(1, N): for j in range(i): if A[j] < A[i]: dp[i] = max(dp[j]+1, dp[i]) print(max(dp)) 💻 풀이한..

📎 간략한 문제 정리 트리의 루트가 1이고 나머지 요소들의 연결 상태가 주어질 때, 나머지 요소들의 부모 노드를 출력하는 코드를 작성합니다. 📈 문제 분석 연결 상태를 관찰하며 각 요소의 부모 노드를 출력하는 문제입니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 dictionary를 통해 연결 상태를 정의하고, 각 요소별로 부모 노드를 검색하면 O(1)으로 탐색 가능합니다. 💻 풀이한 코드 from sys import stdin, setrecursionlimit from collections import defaultdict setrecursionlimit(10**9) input = stdin.readline N = int(input()) adj = defaultdict(list) parents = [0 f..

📎 간략한 문제 정리 기존의 토마토 문제(https://jayb-log.tistory.com/126) 를 3차원으로 변경한 문제입니다. 익은 토마토 주변의 토마토는 익게 되는데, 모든 토마토가 익게 될 때까지 걸리는 시간을 측정하는 문제입니다. 📈 문제 분석 BFS/DFS 문제로 조건에 맞춰 주변을 탐색합니다. 기존 토마토 문제와 다른 점은 3차원이기 때문에 dx, dy로 2방향만 보는 것이 아니라 위 아래도 관찰하는 dz도 관찰해야 하는 차이가 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 각 시점에 따라서 주변에 상황이 변해가는 것이므로 DFS보다 BFS가 적합합니다. 💻 풀이한 코드 from sys import stdin from collections import deque input = stdi..

📎 간략한 문제 정리 2차원 배열 A의 요소는 다음과 같이 정의됩니다. A[i][j] = i*j 이 리스트를 1차원으로 만든 후 k번째 요소를 찾는 문제입니다. 📈 문제 분석 배열을 일반적으로 정렬하기 위해서는 O(NlogN)의 속도가 발생합니다. 문제에 주어진 N의 범위가 100000이므로 NlogN은 약 1600000 정도로 속도 이슈가 발생하지 않을 것 같습니다. -> 메모리 이슈가 발생합니다. 속도에는 문제가 없을지 모르지만 메모리에 문제가 발생합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 병합정렬은 O(NlogN)으로 tim sort 역시 O(NlogN)이라서 우선 tim sort를 활용해보겠습니다. 위의 방법은 메모리 이슈가 발생하므로 메모리와 속도가 tim sort보다 동시에 여유가 있는 H..