Magin-playground Magin-playground

문제) 알고리즘) - 시간복잡도를 생각하지 않고 문제를 본다면 대부분 for문과 sum 함수를 반복해서 사용해서 코드를 짜면 될 것 같지만 예시) for i in range(N-X+1): #윈도우의 크기와 graph의 크기를 고려해서 움직일 수 있는 횟수만큼 반복 now = sum(graph[i:i+X]) #매번 sum함수로 해당 윈도우안에 해당하는 값 sum 이 경우 시간복잡도에서 걸리게 되어 시간초과가 됩니다.(for문과 sum 동시에 반복시 n^2의 시간복잡도 갖는다 최악!!) - 핵심은 이름 그대로 Sliding Window처럼 지나가면서 윈도우에서 벗어나는 값은 빼고 새로 들어오는 값 더하기 start += graph[i] #들어오는 값 start -= graph[i-X]빠져나가는 값 코드) #..

문제) 알고리즘) -그래프의 대표적인 bfs 활용 - bfs탐색을 통해 이어져 있는 단지의 크기와 개수를 출력하는 것 - 방문처리는 1 => 0으로 변환하며 처리 코드) #단지번호붙이기 import sys input = sys.stdin.readline n = int(input()) g = [] size = [] move_x = [-1, 0, 1, 0] move_y = [0, -1, 0, 1] for _ in range(n): g.append(list(map(int, input().strip()))) def dfs(y,x): global cnt #단지별 사이즈 if x = n or y = n: #범위밖 조선 return 0 if g[y][x] == 1: #확인된 자리 g[y][x] = 0 cnt += 1..

문제) 알고리즘) 그리디 알고리즘 대표적인 문제 -동전을 내림차순으로 정렬 -큰값부터 차례로 나눠준다 (나눌때 몫을 카운트) 동전 수 출력 코드) #다시 풀이 # 동전0 import sys from collections import deque input = sys.stdin.readline cnt, price = map(int, input().split()) result = 0 coin = [] for _ in range(cnt): coin.append(int(input())) coin.sort(reverse= True) coin = deque(coin) while coin: current = coin.popleft() if current > price: continue result += (price//..

문제) 알고리즘) 풀이 핵심) - 토너먼트의 특징을 잘 생각해보자 풀이) -주어지는 두값은 무조건 생존 -각 라운드마다 절반으로 감소한다 ex) f_1 20 10 5 2 1 f_2 31 15 7 3 1 해당 사이클로 만나게 되는 라운드 값 출력 코드) #토너먼트 import sys input = sys.stdin.readline n, f_1, f_2 = map(int ,input().split()) cnt = 0 while f_1 != f_2: f_1 -= f_1//2 f_2 -= f_2//2 cnt += 1 print(cnt)

문제) 알고리즘) DP 계단의 수가 3개미만 일 경우 총 합이 최종 값이다. 그외) n번째에 해당 계단마다 갈 수 있는 최댓값을 d[n]에 할당 한다. 해당 사이클을 반복 후 출력을 원하는 위치의 계단 값을 출력이 바로 최댓값이다. 코드) #계단오르기 import sys n = int(sys.stdin.readline()) #계단 갯수 stair = [] #계단 저장 for _ in range(n): #N개만큼 계단 생성 stair.append(int(sys.stdin.readline())) d = [0]*n #계단 갯수만큼 확보 d[0] = stair[0] if n

문제) 알고리즘) 그래프 목표: 농장에서 배추가 있는 구역의 수 구하기 입력부 이후 -배추의 위치를 찾고 그로부터 인접한 배추 위치 파악 현재 위치에서 십자가 형태로 탐색 반복문에서 빠져나오면 +1 => 반복문 탈출 인접해 있는 배추 한 구역을 모두 탐색한 것 최종적으로 result 출력 배추의 구역 수 코드) #유기농 배추 import sys from collections import deque input = sys.stdin.readline move_row = [0, 1, 0, -1] move_col = [-1, 0, 1, 0] def bfs(row, col, graph): d = deque() d.append([row,col]) graph[row][col] = 0 while d: x,y = d.po..

문제) 알고리즘) DP - 기준 값은 목표 금액(d), 계산 순서는 오름차순 동전 값(coins) ex) c = 3 (현재 동전) d[5] += d[5-3] 목표 금액 5 += 3원을 사용하기 전의 d[2]의 값 모든 계산을 마치고 목표금액의 마지막 값을 출력 코드) #동전 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): n = int(input()) coins = list(map(int, input().split())) goal = int(input()) d = [0]*(goal+1) #goal(목표 금액)까지 DP d[0] = 1 for c in coins: #오름차순 코인 for i in range(c, goal+1..

문제) 알고리즘) -첫시도 deque의 특징을 살려 pop(), popleft(), append(), insert() 등으로 조건에 맞게 배열을 회전시킨 후 결과 출력 -아래 코드- 첫 시도의 pop(), popleft(), append(), insert() 등을 rotate()를 활용해 한번에 구현 가능 ex) a = [1, 2, 3, 4, 5] a.rotate(1) => [5, 1, 2, 3, 4] a.rotate(-2) => [2, 3, 4, 5, 1] *주의사항 배열의 회전시 pop()한 데이터 인지하며 회전 수 설정 코드) #풍선 터트리기 import sys from collections import deque input = sys.stdin.readline n = int(input()) q =..