Algorithm Study
[백준 파이썬] #10799. 쇠막대기
풀기 전 생각해보기😮 stack 문항 각각의 경우를 따져서 풀 수 있다 풀이🛫 # 스택 # 모든 경우대로 조건문을 나열 arr = list(input()) stack = [] cnt = 0 for i in range(len(arr)): if len(stack) == 0 and arr[i] == '(': # stack이 아직 만들어지지 않았을 경우 stack.append('(') else: # stack이 존재할 때 # 이전에 들어온 값과 현재 입력되는 값을 비교 # 모든 경우의 수는 4가지 밖에 되지 않음 if arr[i-1] == '(' and arr[i] == '(': # case1 stack.append('(') elif arr[i-1] == '(' and arr[i] == ')': # case2 ..
[백준 파이썬] #2493. 탑
풀기 전 생각해보기😮 stack 문제에 해당 풀이🛫 N = int(input()) # 500,000 이하 -> 완전탐색으로 구현하면 시간초과 발생 우려 towers = list(map(int, input().split())) lst = [(0, 0)] # 초기 값으로 (0, 0)을 보유 ans_lst = [] # 정답 리스트 for i in range(len(towers)): # stack에 쌓여있는 마지막 높이보다 현재의 탑이 더 높을 경우 if lst[-1][0] 현재 탑보다 큰 높이가 나올 때까지 while lst[-1][0] < towers[i]: lst...
[백준 파이썬] #2636. 치즈
풀기 전 생각해보기😮 치즈가 모두 녹는 지점 파악하기 풀이🛫 # 구하려는 것 : 치즈가 모두 녹아 없어지는 시간, 모두 녹기 한 시간 전에 남아있는 치즈조각 # 딥카피 연습: copy_arr = [arr[i][:] for i in range(len(arr))] from collections import deque dcol = [1, 0, -1, 0] drow = [0, -1, 0, 1] # melt() 치즈의 테두리 표시 def melt(): visited = [[0] * R for _ in range(C)] temp_lst = [] queue = deque() queue.append((0, 0)) while queue: col, row = queue.popleft() for v in range(4): ..
[백준 파이썬] #2146. 다리만들기
풀기 전 생각해보기😮 간척 사업 아이디어 적용해보기 중복해서 인식되는 지점을 어떻게 해결할 것인지 메모리 초과 오류 발생 해결 풀이🛫 from collections import deque dcol = [1, 0, -1, 0] drow = [0, 1, 0, -1] def divide_island(): cnt = 1 # 주어진 arr의 모든 부분 탐색 시도 for col in range(N): for row in range(N): if arr[col][row] == 1: # 어느 한 섬에 도달하면 cnt += 1 # 몇 번째 섬인지 표시하기 위해 cnt 활용 queue = deque() # BFS 진행 queue.append((col, row)) checked[col][row] = 1 while queue:..
[백준 파이썬] #14503. 로봇청소기
풀기 전 생각해보기😮 이차원 배열의 탐색은 범위를 항상 조심할 것 구현 문제 풀이🛫 dcol = [0, 1, 0, -1] drow = [-1, 0, 1, 0] def check(col, row, dir): # dir: 바라보는 방향 if dir == 0: if 0
[백준 파이썬] #1018 체스판 다시 칠하기
풀기 전 생각해보기😮 이차원 배열의 탐색 풀이🛫 N, M = map(int, input().split()) # N개의 행, M개의 열 arr = [list(input()) for _ in range(N)] white = [[0] * 8 for _ in range(8)] black = [[0] * 8 for _ in range(8)] for col in range(8): for row in range(8): if (col+row)%2 == 0: white[col][row] = 'W' black[col][row] = 'B' else: white[col][row] = 'B' black[col][row] = 'W' li = [] for col in range(N-8+1): for row in range(M-8+..
[백준 파이썬] #2605 줄세우기
풀기 전 생각해보기😮 insert 함수를 이용해서 리스트의 원하는 인덱스 지점에 값을 추가할 수 있다. 풀이🛫 N = int(input()) arr = list(map(int, input().split())) li = [] for i in range(N): if i == 0: li.insert(0, i+1) else: li.insert(arr[i], i+1) for i in reversed(li): print(i, end=" ") 핵심 정리🎁 N = int(input()) arr = list(map(int, input().split())) li = [] for i in range(N): li.insert(-arr[i], i+1) print(*li) 위 코드 처럼 insert의 음수를 이용해서 출력했을 때..
[백준 파이썬] #2309 일곱 난쟁이
풀기 전 생각해보기😮 아홉명 중 조건에 적합하지 않은 2명을 어떻게 구분할까? 풀이🛫 arr = [int(input()) for i in range(9)] arrSum = 0 odd1, odd2 = 0, 0 # 정렬 : 버블 정렬 사용 연습 for i in range(9): for j in range(i+1, 9): if arr[i] > arr[j]: arr[i], arr[j] = arr[j], arr[i] for i in arr: arrSum += i for i in range(9): for j in range(i+1, 9): if arr[i]+arr[j] == arrSum-100: odd1, odd2 = arr[i], arr[j] for i in arr: if i == odd1 or i==odd2: ..
[알고리즘] DFS 구현
# V개의 노드, E개의 간선이 주어질 때 V, E = map(int, input().split()) graph = [[] for i in range(V+1)] # 그래프 구성 for e in range(E): u, v = map(int, input().split()) graph[u].append(v)# 단방향일 때 #graph[v].append(u)# 양방향일 때 # 방문 정보를 저장할 공간 visited = [0] * (V+1)# 인덱스 에러(혼동)을 방지하기 위해 V+1만큼 메모리 생성 # DFS 함수 구성 def dfs(v): # 해당 정점을 방문 visited[v] = 1; # print(v, end=" "); # 방문 정보가 궁금할 때 확인 가능 # v의 방문하지 않은 인접 정점을 탐색 for..
[알고리즘] 패턴 매칭 알고리즘 소스코드
- 한번만 찾는 경우 # 패턴이 있을 수 있는 가능한 시작 위치 for i in range(n-m+1): # 패턴의 길이 만큼 비교 for j in range(m): # 일치하지 않으면 다음으로 넘어감 if p[j] != t[i+j]: break else: # 매칭 성공 break - 모든 패턴을 찾을 때 : 방법1 i = 0 while i