채마스의 개발창고

접근 방식(알고리즘 분류) 문자열 문제 내 풀이 def solution(files): answer = [] for f in files: head, number, tail = '', '', '' number_check = False for i in range(len(f)): # 문자열 자르기 if f[i].isdigit(): # 처음 나오는 숫자부터는 NUMBER로 number += f[i] number_check = True elif not number_check: # NUMBER가 나오기 전까지는 HEAD head += f[i] else: # NUMBER가 이미 나왔고, 숫자가 아닌 문자가 나오면 TAIL tail = f[i:] break answer.append((head, number, tail))..

접근 방식(알고리즘 분류) 연산문제 내 풀이 def solution(n): ans = 1 while n != 1: if n % 2 == 0: n = n // 2 else: ans += 1 n -= 1 return ans 풀이 설명 5000 --> 2500 --> 1250 --> 625 --> 624 --> 312 --> 156 --> 78 --> 39 --> 38 --> 19 --> 18 --> 9 --> 8 --> 4 --> 2 --> 1 1을 빼줄때만 +1을 해줌 느낀점 1에서 5000으로 올라갈때 최대한 빨리 올라가려고 재귀함수를 통해 5000에 가장 가까운 위치까지 간 후 백트래킹을 통해 조건을 만족시키려고 했다. 문제를 너무 어렵게 접근한 것 같다. 1에서 부터 시작해서 5000으로 가는 것이 ..

접근 방식(알고리즘 분류) 이진트리 내 풀이 #전위 순회 def pre(root, tree, now): global pre_result pre_result.append(now) if tree[root][0][0] != 0: pre(tree[root][0][0], tree, tree[root][0][1]) if tree[root][1][0] != 0: pre(tree[root][1][0], tree, tree[root][1][1]) #후위 순회 def post(root, tree, now): global post_result if tree[root][0][0] != 0: post(tree[root][0][0], tree, tree[root][0][1]) if tree[root][1][0] != 0: pos..

접근 방식(알고리즘 분류) 백트래킹 내 풀이 from collections import defaultdict def solution(tickets): def recur(now, graph, route): #global result if len(route) == len(tickets) + 1: temp = route[:] result.append(temp) return for i in graph[now]: if i[1] == False: route.append(i[0]) i[1] = True recur(i[0], graph, route) i[1] = False route.pop() graph = defaultdict(list) result = [] for i in tickets: graph[i[0]].ap..

접근 방식(알고리즘 분류) 알고리즘 내 풀이 from collections import Counter def solution(a): elements = Counter(a) answer = -1 for k in elements.keys(): if elements[k]

접근 방식(알고리즘 분류) 투포인터 내 풀이 1차 풀이 def solution(gems): answer = [] idx = [] _len = len(set(gems)) for i in range(len(gems)): temp = set(gems[i:]) if len(temp) == _len: idx.append(i) for k in idx: for i in range(len(gems)-1, k-1, -1): if len(set(gems[k:i+1])) == _len: end = i answer.append([k+1,end+1]) return answer[0] solution(["AA", "AB", "AC", "AA", "AC"]) 1차 풀이 설명 우선적으로 [첫번째: 마지막] , [두번째:마지막] .....

접근 방식(알고리즘 분류) 다익스트라 내 풀이 import heapq def solution(N, road, K): graph = [[] for _ in range(N+1)] for i in road: graph[i[0]].append((i[2], i[1])) graph[i[1]].append((i[2], i[0])) distance = [1e9] * (N+1) def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[0] if c..

접근 방식(알고리즘 분류) 재귀 내 풀이 result = [] def hanoi(n, start, end, mid): global result # 옮기는 블럭이 1개일때까지 if n == 1: result.append([start, end]) else: hanoi(n-1, start, mid, end) result.append([start, end]) hanoi(n-1, mid, end, start) return result def solution(n): global result hanoi(n, 1, 3, 2) return result 풀이 설명 큰 덩어리가 작은 덩어리로 나뉘지만 덩어리 마다 하는 작업은 똑같다. 재귀를 단순 반복문으로 생각하기 보다는 일정한 규칙이 찾은 부분에서 똑같이 수행될때 재귀를..

접근 방식(알고리즘 분류) 스택 + 큐 내 풀이 from collections import deque def solution(s): answer = [] for string in s : stack = [] count = 0 for s in string: # 문자열이 0이면 if s == '0': # 앞에 2개가 1, 1인지 확인 if stack[-2:] == ['1', '1']: count += 1 stack.pop() stack.pop() # 앞에 2개가 1, 1이 아니면 그냥 0을 추가 else: stack.append(s) # 문자열이 0이 아니면 그냥 추가 else: stack.append(s) # 110이 없기 때문에 변화 불가능 print(count) if count == 0: answer.a..

접근 방식 (알고리즘 분류) 다익스트라 (단방향) 내풀이 import heapq, sys input = sys.stdin.readline INF = sys.maxsize n, m, k, start = map(int, input().split()) graph = [[] for _ in range(n+1)] distance = [INF] * (n+1) for i in range(m): #a번에서 b번 노드로 가는 비용 c 저장 a, b = map(int, input().split()) graph[a].append((1,b)) def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heap..