목록알고리즘 (45)

리셋 되지 말자

class 4

[백준 1043] 거짓말 - 그래프, 집합, 유니온 파인드(union find), bfs 설명 집합, 그래프(bfs), 유니온 파인드 여러 방식으로 풀 수 있는 문제 여기선 집합을 이용해 풀었다 코드 def solution(n, m, true): # true는 진실을 알고있는 초기 사람들의 집합(set) # 파티들을 저장할 배열 partys = [] # 파티들을 partys에 저장 for _ in range(m): party = list(map(int, input().split()))[1:] partys.append(party) # partys의 각 party와 true에 공통된 사람이 있으면 합친다 # party[0] ~ party[n-1] 까지 n번 반복하면서 각 파티에서 진실을 아는 사람을 전부 합..
알고리즘 2022. 5. 4. 18:57
class 3

[백준 1003] 피보나치 함수 - 다이나믹(dp) 코드 def solution(arr): # 첫번째 원소는 0 출력 횟수, 두번째 원소는 1 출력 횟수 fibo =[ [1, 0], [0, 1] ] # 2~40까지 0과 1을 출력하는 횟수를 저장([i] = [i-2 + i-1]) for i in range(2, 41): first = fibo[i-2][0]+fibo[i-1][0] second = fibo[i-2][1]+fibo[i-1][1] fibo.append([first, second]) # 입력된 각 숫자마다 0과 1을 출력하는 횟수를 출력 for idx in arr: print(fibo[idx][0], fibo[idx][1]) n = int(input()) arr = [] for _ in rang..
알고리즘 2022. 3. 1. 01:54
Tip

정렬 시 비교 함수 사용 lambda 사용 functools의 cmp_to_key 사용 lambda arr = [1, 3, 5, 2, 4] # 오름차순으로 정렬 # [1, 2, 3, 4, 5] arr.sort(key=lambda x: x) print(arr) # 내림차순으로 정렬 # [5, 4, 3, 2, 1] arr.sort(key=lambda x: -x) print(arr) arr2 = [ [1, 9], [2, 3], [2, 4], [2, 5], [3, 1] ] # 첫 번째 원소로 오름차순, 두 번째 원소로 오름차순 # [[1, 9], [2, 3], [2, 4], [2, 5], [3, 1]] arr2.sort(key=lambda x: (x[0], x[1])) print(arr2) # 첫 번째 원소로 ..
알고리즘 2022. 2. 27. 16:14
[백준 18111] 마인크래프트 - 브루트포스

접근 만들어야 하는 높이는 각 좌표의 높이의 사이에 있는 높이일 것이다 (최소높이 ~ 최고높이) 각 높이를 만들 때, 채워야하는 좌표가 있고 깍아야하는 좌표가 있다. 깍으면 블록 개수가 늘어나므로, 이를 잘 고려하여 각 높이를 만들 때 필요한 시간을 계산한다. 필요한 시간이 같은 높이가 여러개라면, 한번에 깍을 수 있다 코드 from collections import Counter def solution(arr, b): # 쌓여있는 블록들의 최소 높이부터 최대 높이 까지의 범위를 저장 heights = [ i for i in range(min(arr), max(arr)+1)] # 높이가 같은 블록의 개수를 Counter를 사용해 저장 cd = Counter(arr) # 걸리는 시간과 높이 저장 time_..
알고리즘 2022. 1. 20. 13:58
[백준 1874] 스택 수열 - 스택

코드 def solution(arr): # stack에 차례대로 넣을 수 배열 nums = [i for i in range(1, len(arr)+1)] # nums의 index nums_idx = 0 stack = [] # push, pop 연산 순서 저장 cals = [] # flag가 True이면 NO 출력 flag = False # pop을 해야하는 타겟 숫자를 차례대로 순회 for target in arr: while True: # stack이 비어있거나, stack의 맨 위가 target과 다르면 nums를 append if len(stack) == 0 or stack[-1] != target: # target을 pop할 수 없으면, flag를 True로 변경한 뒤 break로 반복문 탈출 if..
알고리즘 2022. 1. 19. 18:01
[백준 1966] 프린터 큐 - 큐

코드 from collections import deque def solution(b, arr): # target인 작업 index b에 대한 타겟 여부를 1(타겟) 변경 arr[b][1] = 1 dq = deque(arr) cnt = 1 while len(dq) != 0: # 맨 앞에 있는 작업이 중요도가 제일 높으면 if dq[0][0] == max(dq)[0]: # 중요도가 제일 높은데 타겟이면 cnt 출력 후 종료 if dq[0][1] == 1: print(cnt) break # 중요도가 제일 높은데 타겟이 아니면 작업 pop, cnt 증가 dq.popleft() cnt += 1 # 중요도가 제일 높은 작업이 아니면, 작업을 뒤로 넘김 else: dq.append(dq[0]) dq.popleft(..
알고리즘 2022. 1. 18. 15:38
[백준 4949] 균형잡힌 세상 - 스택

코드 def solution(string): stack = [] no_sts = False for char in string: # print(stack) # 여는 괄호('[', '('가 나오면 stack에 추가 if char == '[' or char == '(': stack.append(char) # 닫는 괄호(']', ')'가 나오면 예외처리 elif char == ']' or char == ')': # 닫는 괄호인데 스택이 비어있으면 no if len(stack) == 0: no_sts = True break else: # 닫는 괄호와 stack의 맨위와 한쌍이 아니면 no if char == ']' and stack[-1] == '(': no_sts = True break # 닫는 괄호와 stac..
알고리즘 2022. 1. 18. 14:42
[백준 1080] 체스판 다시 칠하기 - 브루트포스

코드 def solution(arr): answer = 2e9 # black 시작하는 체스판 b_arr = [ list('BWBWBWBW'), list('WBWBWBWB'), list('BWBWBWBW'), list('WBWBWBWB'), list('BWBWBWBW'), list('WBWBWBWB'), list('BWBWBWBW'), list('WBWBWBWB') ] # white 시작하는 체스판 w_arr = [ list('WBWBWBWB'), list('BWBWBWBW'), list('WBWBWBWB'), list('BWBWBWBW'), list('WBWBWBWB'), list('BWBWBWBW'), list('WBWBWBWB'), list('BWBWBWBW'), ] # height, width를 -..
알고리즘 2022. 1. 18. 11:17
Prev 1 2 3 4 ··· 6 Next