채마스의 개발창고

접근 방식(알고리즘 분류) 재귀 내 풀이 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..

접근 방식 (알고리즘 분류) 이진탐색 내풀이 from bisect import bisect_left, bisect_right import sys input = sys.stdin.readline m, n, l = map(int, input().split()) sade = list(map(int, input().split())) sade.sort() check_x, check_y = [], [] for i in range(n): x, y = map(int,input().split()) check_x.append(x) check_y.append(y) result = 0 for point in range(n): tmp = bisect_left(sade, check_x[point]) flag = 0 # 사대의 젤..

접근 방식(알고리즘 분류) 문자열 내 풀이 from collections import deque testcase = int(input()) answer = [] for _ in range(testcase): s = input() n = int(input()) temp = input() temp2 = temp.split(",") if len(temp2) == 1: if temp2[0][1] == "]": temp2 = [] else: temp2 = [temp2[0][1:-1]] else: temp2[0] = temp2[0][1:] temp2[-1] = temp2[-1][:-1] number = deque([i for i in temp2]) flag = 0 check = False for i in s: if..

접근 방식(알고리즘 분류) DFS + DP 내 풀이 import sys #재귀할때 이거 안해주면 가끔 런타임나옴 sys.setrecursionlimit(10**9) input = sys.stdin.readline N = int(input()) Tree = [[] for _ in range(N+1)] visited = [True for _ in range(N+1)] for _ in range(N-1): u, v = map(int, input().split()) Tree[u].append(v) Tree[v].append(u) #[1,0]으로 초기화 해주는 이유는 현재 dp에 저장할 값은 얼리 어답터가 아닌 노드의 수를 구하는 것이기 때문이다. DP = [[1,0] for _ in range(N+1)] def..

접근 방식(알고리즘 분류) KMP 내 풀이 # 일치하는 부분 문자열의 최대 길이를 기록하는 테이블 생성 def make_table(s): table = [0 for _ in range(len(s))] j = 0 for i in range(1, len(s)): #같을때까지 j를 뒤로 건너뛰면서 후퇴 while j > 0 and s[j] != s[i]: j = table[j-1] #같아집면 table에 j+1값을 대입 --> i, j 둘다 1씩 증가 if s[j] == s[i]: table[i] = j + 1 j += 1 return table def KMP(origin, pattern): result = [] table = make_table(pattern) j = 0 for i in range(len(o..

접근 방식(알고리즘 분류) KMP 내 풀이 # 일치하는 부분 문자열의 최대 길이를 기록하는 테이블 생성 def make_table(s): table = [0 for _ in range(len(s))] j = 0 for i in range(1, len(s)): #같을때까지 j를 뒤로 건너뛰면서 후퇴 while j > 0 and s[j] != s[i]: j = table[j-1] #같아집면 table에 j+1값을 대입 --> i, j 둘다 1씩 증가 if s[j] == s[i]: table[i] = j + 1 j += 1 return max(table) s = input() result = 0 for i in range(len(s)): result = max(result, make_table(s[i:len(..

백준 1184번 접근 방식(알고리즘 분류) DP + Indexing 내 풀이 #한쪽 대각선만 생각했음 n = int(input()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) def arrSumRight(arr, a, b): sArr = [[0 for _ in range(n-b)] for _ in range(n-a)] aArr = [[0 for _ in range(n-b)] for _ in range(a)] sArr[0][0] = arr[a][b] aArr[a-1][0] = arr[a-1][b] resultS = [arr[a][b]] resultA = [arr[a-1][b]] # 교차점 기준 오른쪽 아래 for i in..

함수형 인터페이스란 아래와 같이 추상 메소드를 딱 하나만 가지고 있는 인터페이스 public interface RunSomething { void doIt(); // abstract 가 생략된 것이다. } static void printName(){ System.out.println("이름"); } default void printAge(){ System.out.println("28"); } static 메소드나 default 메소드의 유무와는 상관없이 추상메서드가 1개이면 함수형 인터페이스이다. SAM (Single Abstract Method) 인터페이스 @FuncationInterface 애노테이션을 가지고 있는 인터페이스 람다 표현식 위에서 정의한 RunSomething 인터페이스를 람다를 사용하..