도니 개발노트

1. 문제 2. 소스코드 (Python3) DFS 코드 (성공) def inRange(n, m, i, j): if i=n or j=m: return False return True def DFS(image, visit, n, m, i, j): # 상하좌우 di = [-1, 1, 0, 0] dj = [0, 0, -1, 1] stack = [(i, j)] while stack: i1, j1 = stack.pop() visit[i1][j1] = True for d in range(4): i2 = i1 + di[d] j2 = j1 + dj[d] if not inRange(n, m, i2, j2): continue if visit[i2][j2]: continue if image[i1][j1] == image[i2..

1. 문제 2. 소스코드 def solution(s): # len(s)개 단위로 잘라 압축하는 경우 answer = len(s) # 1 ~ len(s)-1개 단위로 잘라 압축하는 경우 for l in range(1, len(s)-1): # 첫번째 압축 문자열 comp = [1, s[:l]] # 다음 문자열들에 대해서 처리 for i in range(1, len(s)//l + bool(len(s)%l)): word = s[i*l:(i+1)*l] # 앞 문자와 같으면 숫자 +1 if word == comp[-1]: comp[-2] += 1 # 앞 문자와 다르면 새로 추가 else: comp += [1, word] # int -> string으로 변환, 1이면 삭제 for i in range(0, len(co..

1. 문제 2. 소스코드(Python3) def Eratos(n): if n N번 반복 j에 대한 for loop -> N/i번 반복 따라서 위 함수의 시간 복잡도는 O(N^2)이다. 2) add : 세 소수를 더하는 함수 1) 알고리즘 odd의 세 원소를 꺼낸다. 세 값을 더한 결과가 주어진 수 n과 같은지 비교하여 횟수를 센다. 2) 시간복잡도 odd의 원소 개수가 N이라고 하자. odd의 세 원소에 대해 삼중 for문 -> O(N^3) 3) solution : main함수 1) 알고리즘 n이하의 소수를 모두 구하여 odd리스트에 저장한다. add함수를 이용하여 세 숫자를 더하여 n이 되는 경우의 수를 센다. 2) 시간복잡도 Eratos함수의 시간 복잡도는 O(N^2)이다. add함수는 주어진 입력이..

1. 문제 2. 소스코드 def solution(s): stack = [] match = {'(':')', '{':'}', '[':']' } for x in s: # 여는 괄호 if x in match: stack.append(x) # 닫는 괄호 else: if not stack: return False if match[stack.pop()] != x: return False return not stack 3. 고찰 1) 알고리즘 여는 괄호이면 스택에 push 닫는 괄호이면 (1) 스택이 비어있는지 검사 (2) 스택의 top과 매치하는 괄호인지 검사한다. 문자열 s의 모든 괄호에 대해 위 과정을 반복한 후 스택이 비어있으면 True를 리턴한다. 2) 시간복잡도 문자열 s의 모든 괄호에 대해 for loo..

1. 문제 2. 소스코드 (Python3) def solution(seat): answer = len(seat) Set = {} for s in seat: index = 100000*s[0] + s[1] if index in Set: answer -= 1 else: Set.add(index) return answer 3. 고찰 1) 알고리즘 모든 seat에 대해서 set에 넣고, 이미 해당 좌석이 set에 들어있다면 정답에서 한 명씩 빼는 알고리즘. 이때 좌석은 100000 * 100000 크기로 2차원이므로 좌석의 좌표는 x좌표 * 100000 + y좌표로 계산하였다. 2) 시간복잡도 모든 seat의 원소에 대해서 for loop -> O(N) Set에 해당 좌표(index)가 있는지 확인 -> O(N..

1. 문제 programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 2. 소스코드 (Python3) import heapq def solution(scoville, K): answer = 0 scoville = [s for s in scoville] heapq.heapify(scoville) while True: tmp1 = heapq.heappop(scoville) if tmp1 >= K: break if not sc..

1. 문제 programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 2. 소스코드 (Python3) def solution(number, k): stack = [] for n in number: while stack and stack[-1] O(N) 리스트.pop() -> O(1) 리스트.append() -> O(1) 따라서 위 코드의 시간복잡도는 O(N)이다.

1. 문제 programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 2. 소스코드 (Python3) import functools def comp(a,b): if int(a+b) int(b+a): return -1 return 0 def solution(numbers): strnum = [str(n) for..