개발 일기

✅ 문제 💡 문제 이해 최대 k개의 집중국의 수신 가능 영역 길이의 합의 최솟값을 구하는 문제 1. 센서를 묶어 k개의 집중국으로 나눔 2. 각 집중국 내의 센서 간 수신거리의 합이 최소가 되는 경우 = 집중국간 경계의 거리가 최대가 되는 경우 ✅ 풀이 문제 자체를 이해하는데 한참 걸렸다. 그리디 알고리즘 방식으로 접근하면 된다고는 생각했지만 실제적으로 구현이 좀 어려웠음 💡 문제 풀이 Point 1. 집중국이 k개일 때 집중국 경계 영역은 k-1개 2. 원점으로부터 거리 -> 오름차순 정렬 후 인근 센서 사이 거리 구하기 3. 센서 간 거리를 배열에 담고 오름차순하여 가장 큰 수 k-1개를 제외한 나머지 합을 구하기 아래에 예제 입력 2가지 경우를 모두 그림으로 그려 보았다. 각 센서간 거리를 구한 다..

✅ 문제 💡 문제 이해 1. 섬 개수 구하기와 비슷하지만 R, G, B로 섬 구분 2. 적록색약의 경우 R, G 구분이 안가므로 R+G / B로 구분 3. 각 구역 수 count 후 출력 ✅ 나의 코드 💡 문제 풀이 Point 1. 적록색약의 여부를 isblind로 구분해서 dfs 탐색시 같이 넘김 2. dfs 탐색 시 2-1) 적록색약인 경우 B인 경우와 B가 아닌 경우를 나누어서 탐색 2-2) 적록색약이 아닌 경우 일반적인 dfs 탐색 import sys input = sys.stdin.readline sys.setrecursionlimit(10000) def dfs(x, y, color, isblind): for i in range(4): nx = x+dx[i] ny = y+dy[i] if 0

✅ 문제 원하는 위치로 나이트를 이동시킬 때의 최단 거리를 구하는 문제 최단 경로를 구하는 문제라서 bfs 방식으로 풀었다. ✅ 나의 코드 import sys from collections import deque input = sys.stdin.readline # 이동 좌표 dx = [-2, -1, 1, 2, -2, -1, 1, 2] dy = [1, 2, 2, 1, -1, -2, -2, -1] def bfs(x, y, x2, y2, visited): q = deque() q.append((x,y)) while q: currentX, currentY = q.popleft() if currentX == x2 and currentY == y2: # 이동이 끝나면 이동거리 -1 반환(현재 위치 제외) print..

✅ 문제 - 두 정렬 리스트의 병합 이진트리에서 두 노드 간 가장 긴 경로의 길이를 출력하는 문제! ✅ 풀이 💡 Point 1. 1부터 시작해서 각 노드별로 좌, 우 서브트리를 dfs 방식으로 확인 2. 더이상 서브트리가 없을 경우 0 반환하고 부모 노드로 다시 올라감 3. 부모노드 기준 좌, 우 서브트리 확인하여 더 깊은 쪽 길이에 +1 4. 항상 최댓값을 반환하므로 가장 긴 길이를 출력할 수 있다. 출력 샘플 그림으로 그려보며 이해해 봤다. 1부터 시작하여 서브트리 순회를 각각 하는데, 2로 내려가면 또 4, 5 서브트리가 있으니 더 이상 서브트리가 없을 때까지 dfs 탐색을 한다. 서브트리가 없으면 0을 반환하며 다시 부모 노드로 올라가는데 이때 좌 우 트리깊이 중 더 깊은 값에 +1을 해준다. 2..

✅ 문제 ✅ 풀이 solution 1) 힙 이용 - 시간 초과 💡 Point 1. 인덱스와 함께 리스트를 힙 정렬함(최소 순으로 정렬) 2. 조건 확인 후 1) 현재 탑보다 숫자가 커야 함(숫자가 작으면 송신 불가) 2) 최초 리스트 기준 왼쪽으로 순회한다는 말 = 현재 탑보다 인덱스가 작아야 함 3. 결과 리스트 0으로 세팅해 두고, 현재 탑의 자리에 발사한 레이저를 송신한 탑의 인덱스+1 값을 넣어줌 n = int(input()) top = list(map(int, input().split())) # 송신탑 자리번호를 매겨 최소힙으로 만들어 정렬 top_list = [(num, i) for i, num in enumerate(top)] heapq.heapify(top_list) result = [0]..

✅ 문제 ✅ 풀이 이 문제는 이전에 풀어본 괄호를 이용한 문제와 굉장히 비슷하다. 👇 괄호 문제 풀이 보기 더보기 [Leetcode] 20. Valid Parentheses ✅ 문제 - 유효한 괄호 이 문제는 s의 괄호 짝이 맞는 경우 true, 맞지 않는 경우 false 반환하는 문제이다. ✅ 풀이 코드 이 문제는 전형적인 스택 구조이다. 예를 들어, s가 {[]} 라면 [ 가 나중에 들 writtenbyrla.tistory.com [baekjoon] 9012. 괄호 ✅ 문제 💡 사용자에게 정수 하나를 입력받아 그 수만큼 문자열을 입력받고 괄호가 모두 쌍이 있는 경우 YES 출력(VPS에 해당), 괄호가 남는 경우 NO 출력 ✅ 첫 번째 시도 - 실패 # 파이썬에서 사용 writtenbyrla.tist..

✅ 문제 ✅ 풀이 이 문제는 생각보다 간단하다. 최솟값만을 이용하니 힙정렬을 이용하자 💡 Point 가장 작은 수를 지닌 카드 두 개(x, y)를 더한 값을 다시 카드 리스트에 넣어줘야 함 1) 두 카드를 제거 - heappop() 2번 2) x+y 값으로 덮어씀 - heappush() 2번 import heapq # 카드 합체 놀이 # n: 카드 개수, m=합체 횟수 n, m = map(int, input().split()) cards = list(map(int, input().split())) #리스트를 힙으로 변환 heapq.heapify(cards) for i in range(m): # 제일 작은 수 두개 뽑아내기 x = heapq.heappop(cards) y = heapq.heappop(car..

✅ 문제 예제 입력을 보면서 이해를 해보자. 첫 줄에는 터널로 진입할 차량의 수 n, 터널에 들어간 순서대로 차량 번호 n개, 터널에서 나온 순서대로 차량 번호 n개 따라서 ZG206A 말고는 들어간 순서대로 나왔으니 이 차만 추월해서 답은 1이다. ✅ 풀이 💡 Point 1. 들어가는 순서대로 딕셔너리에 담음(key = 차번호, value=들어간 순서) 2. 나오는 순서대로 리스트에 담음 3. 추월 조회 1) 나온 순서대로 2) 그 차가 몇 번째 들어갔었는지, 그 다음 차가 몇 번째 들어갔었는지 비교하여 3) 들어갈때보다 나온 순서가 크면 추월한 것으로 count 올린 후 다음 차 조회 n = int(input()) input_list = {} output_list = [] # 입구에서 들어가는 순서로..

✅ 문제 ✅ 풀이 이 문제는 하나의 커서로 이동하는 특징을 고려해서, 스택으로 풀 수 있다. 💡 Point * 일반 문자, 왼쪽 커서 이동(''), 백 스페이스('-') 네 가지 조건 나누기 1. 일반 문자: pwd 배열에 그대로 입력 2. 백 스페이스: pwd 배열에서 마지막 글자 제거 - 스택의 pop() 이용 3. 왼쪽 커서 이동 - 현재 커서가 있는 곳중간부터 입력이 들어가야 하므로 오른쪽 문자를 제거해놓아야 함 1) pwd의 마지막 글자를 제거하여 임의의 배열(cursor)에 담아 놓고, 2) 다른 연산이 끝난 후 다시 뒤에다가 붙이기(붙일 땐 거꾸로) 4. 오른쪽 커서 이동 - 임의의 배열에 담아둔 글자가 있다면 그 글자 다음에 새로운 문자를 입력받아야 함 1) cursor의 마지막 글자를 제..

✅ 문제 - 두 정렬 리스트의 병합 내부적으로 정렬된 연결 리스트 2개를 오름차순으로 병합하여 하나의 연결리스트로 만드는 문제! ✅ 풀이 💡 Point 1. 각 리스트의 노드 값을 비교하여 list1에 더 작은 수가 가도록 값을 바꿔줌 ++ list1이 비어있다면 list2를 list1으로 보내야 하기 때문에 조건문에 not list1도 함께 걸어줌 2. list1의 마지막 노드가 참조할 값은 현재 list2로 함 → mergeTwoList를 이용하여 list1의 마지막 노드가 list2의 첫 노드를 참조하게 함으로써 사실상 병합작업임 3. 정렬, 병합이 끝난 연결 리스트를 반환함 코드 class Solution: def mergeTwoLists(self, list1: Optional[ListNode],..