본문 바로가기

728x90

전체 글148

[TIL] 동적 프로그래밍 문제 풀이3 1. 문제 풀이 연습 1. 11660번 - 구간 합 구하기 5 import sys N, M = map(int, sys.stdin.readline().split()) table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 누적합을 저장할 이차원 배열 dp = [[0] * (N+1) for _ in range(N+1)] for i in range(1, N+1) : for j in range(1, N+1) : dp[i][j] = table[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] # 원하는 구간합 구하기 for _ in range(M) : x1,y1,x2,y2 = map(int, s.. 2023. 5. 2.

[TIL] 그리디 문제 풀이 + 기계 수준 표현1 1. 그리디 문제 풀이 1. 1931번 - 회의실 배정 import sys N = int(sys.stdin.readline()) # meeting[0] : 시작 시간 / meeting[1] : 끝나는 시간 meeting = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] meeting.sort(key= lambda x : (x[1], x[0])) count = 1 prev = meeting[0][1] # 앞 회의 끝나는 시간 for i in range(1, N) : # 만약 현재 회의 시작 시간이 앞 회의 시간보다 크거나 같으면 if prev people[i][1] : count += 1 interview = people[i][1] pr.. 2023. 5. 1.

[TIL] Algorithm - Greedy 기본 문제 풀이 1. 그리디 알고리즘 (탐욕 알고리즘) 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다. 언제나 최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 구해줄 수 있다. 1. 11047번 - 동전 0 import sys N, K = map(int, sys.stdin.readline().split()) # 오름차순으로 입력을 받는다. coin = [int(sys.stdin.readline()) for _ in range(N)] count = 0 # 동전의 가치가 가장 큰 동전부터 반복 시작 for i in range(N-1, -1, -1) : if K == 0 : break # 현재 K보다 작은 수.. 2023. 4. 30.

[TIL] 동적 프로그래밍 문제 풀이2 1. 11049번 - 행렬 곱셈 순서 1. 최적 괄호 묶기의 구조 : n개의 행렬을 어떻게 곱할지 애매함을 없애기 위해 괄호로 묶는다. ex) ((A1, A2), A3) or (A1, (A2, A3)) 이 문제는 n개의 행렬들의 체인 이 주어졌을 때 A1, A2, ... , An의 스칼라 곱의 개수를 최소화 하도록 괄호를 묶어라! 라고 하는 것과 같다. AiAi+1...Aj를 괄호호 최적으로 묶기 위해 Ak Ak+1의 사이에서 나눈다고 가정 AiAi+1...Ak Ak+1Ak+2...Aj 위의 두 부분문제는 각각 최적 괄호 묶는 방법이 되어야 한다. 2. 재귀해 i == j 일 경우 0 i < j 일 경우 → k, k+1로 나눈다. Ai = pi-1 * pi 라면 Ai..kAk+1..j = pi-1 *pk.. 2023. 4. 29.

[TIL] 동적 프로그래밍 문제 풀이 1. DP 문제 풀이 1. 9084번 - 동전 import sys T = int(sys.stdin.readline()) for _ in range(T) : N = int(sys.stdin.readline()) coin = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.readline()) dp = [0] * (M+1) # 각각의 금액에 대한 동전으로 만들 모든 방법의 수 저장 dp[0] = 1 # 기저 값으로 지정 for c in coin : for i in range(1, M+1) : if i >= c : dp[i] += dp[i-c] print(dp[M]) 간단하게 생각하면 간단하다고 할 수 있지만 저 방식을 생각해내는 것 자체가 힘들.. 2023. 4. 28.

[TIL] Algorithm - 동적 프로그래밍 기본 1. 그래프 문제 풀이 1. 1388번 - 바닥 장식 import sys N, M = map(int, sys.stdin.readline().split()) graph = [list(sys.stdin.readline().strip()) for _ in range(N)] visited = [[0] * M for _ in range(N)] # 같은 행에 존재하는지 확인해야하므로 열 번호 증가 def col(x, y) : visited[x][y] = 1 stack = [(x, y)] while stack : curx, cury = stack.pop() for i in range(1, M) : ny = cury + i if ny < M and graph[curx][ny] == '-' and visited[curx.. 2023. 4. 27.

[TIL] 위상 정렬 문제 풀이 + Computer System2 1. 위상 정렬 문제 풀이 1. 2637번 - 장난감 조립 import sys from collections import deque N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) basic = [[] for _ in range(N)] inDegree = [0] * N for _ in range(M) : x, y, k = map(int, sys.stdin.readline().split()) basic[y-1].append((x-1, k)) inDegree[x-1] += 1 def topologicalsort() : # component[x][y] -> x를 만드는데 필요한 y의 개수 component = [[0] * N for _ in range.. 2023. 4. 26.

[TIL] Algorithm - 위상 정렬 + 플로이드-워셜 1. 그래프 문제 풀이 1. 2573번 - 빙산 ▶ BFS를 이용한 풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) iceberg = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 빙산 녹이는 함수 def melting() : change = [] for i in range(1, N-1) : for j in range(1, M-1) : if iceberg[i][j] != 0 : sea = 0 # 현재 위치에서 0과 맞닿아 있는 개수 for k in ran.. 2023. 4. 25.

[TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) 1. 다익스트라 알고리즘(Dijkstra algorithm) 모든 간선에 대한 가중치가 항상 0이상임을 가정하고 두 꼭짓점 간의 가장 짧을 경로를 찾는 알고리즘 간선 완화(Edge Relaxation) 시작 정점 s에서 다른 정점 v까지의 초기 거리 값을 부여하고 단계를 거듭하여 개선시키는 것 간선 (u, v)를 완화하는 과정 u를 통해 v까지 가는 지금까지 발견된 최단 경로를 개선할 수 있는지 검사 개선할 수 있다면, v의 최단 경로 추정값을 갱신한다. 시간복잡도 O(|E| + |V|log|V|) https://ko.wikipedia.org/wiki/데이크스트라_알고리즘 1. 다익스트라를 이용한 문제 풀이 1. 1916번 - 최소비용 구하기 import sys import heapq N =.. 2023. 4. 24.

[TIL] 그래프 문제 문제 풀이 1. 그래프 문제 풀이(DFS) 1. 1707번 - 이분 그래프 1. 이분 그래프(bipartite graph)란? 모든 정점을 두가지 색으로 칠하되, 모든 변이 두가지 색의 정점을 포함하도록 하는 그래프 위의 이미지에서 보면 모든 간선이 빨강, 초록 정점을 가지고 있다. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어 있는 그래프 https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html 2. 백준 제출 풀이(DFS - 반복) import sys K = int(sys.stdin.readline()) # dfs 반복문으로 구현 def dfs(g, n) : # n 시작 정점 stack.. 2023. 4. 22.

[TIL] Algorithm - 최소 신장 트리 + 그래프 기본 문제 풀이 1. 그래프 기본 문제 풀이 1. 5639번 - 이진 검색 트리 import sys sys.setrecursionlimit(10**6) nums = [] # 입력이 더이상 들어오지 않을 때 오류 발생 # 오류가 나타나면 while문 종료 while True : try : nums.append(int(sys.stdin.readline())) except : break # nums의 시작 인덱스 = start # nums의 끝 인덱스 = end def post(start, end) : if start == end : # start와 end가 같은 경우 # 한가지 경우만 있으니 출력 print(nums[start]) return root = nums[start] # 현재 루트 노드 mid = start for.. 2023. 4. 21.

[TIL] Graph + 트리 순회 1. 문제 풀이 정리 1. 16120번 - PPAP import sys s = sys.stdin.readline().strip() stack = [] ppap = ["P", "P", "A", "P"] for i in s : stack.append(i) # 현재 스택에 PPAP가 있으면 3번 pop하여 P만 남긴다. if stack[-4:] == ppap : stack.pop() stack.pop() stack.pop() # 최종적으로 P만 남을 경우 if stack == ["P"] : print("PPAP") else : print("NP") 문제에서 조건을 보면 PPAP 는 P로 바꿀 수 있고 P 를 PPAP로 바꿀 수 있다. 즉, 어떤 문자열을 받고 이 문자열이 PPAP 문자열인지 확인하려면 PPAP.. 2023. 4. 20.

[TIL] 스택계산기 + Hashing3 1. 스택을 이용한 계산기 1. 식 표기법 전위 표기법(prefix, 폴란드 표기법) : 연산자를 연산 대상의 앞에 쓰는 연산 표기법 ex) *+234 장점 : 프로그래밍 언어의 인터프리터에 의해 수학적 표현식에 대한 문법으로써 사용되는 경우, 곧바로 추상 문법 트리로 구문 분석되며, 사실 동일하게 전단사 함수를 정의할 수 있다. 단점 : 사람의 눈으로 쉽게 이해하거나 계산하기 힘들다. 중위 표기법(infix) : 연산 대상 사이에 연산자를 쓰는 연산 표기법 ex) (2+3)*4 장점 : 사람에게 친숙하다. 단점 : 우선 순위 규칙에 따라 연산 순서를 결정하여 괄호로 연산이 수행되는 의도된 순서를 가리키는데 필수적이다. 컴퓨터로 구문 분석하기 어렵다. 후위 표기법(postfix) : 연산자를 연산 대상의.. 2023. 4. 19.

[TIL] 분할 정복 연습문제 풀이 + Hashing2 1. 분할 정복 연습문제 1. 10830번 - 행렬 제곱 import sys N, B = map(int, sys.stdin.readline().split()) p = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 두 행렬을 곱하는 함수 def mul (a, b) : result = [[0] * N for _ in range(N)] for r in range(N) : for c in range(N) : for i in range(N) : result[r][c] += a[r][i] * b[i][c] result[r][c] %= 1000 return result # 제곱근을 분할하는 함수 def getResult(p, b) : if b .. 2023. 4. 18.

[TIL] 자료구조 - 우선순위 큐 1. 우선순위 큐(Priority Queue) 우선순위 큐는 추상적인 개념으로 힙이나 다양한 다른 방법을 이용해 구현된다. 각 원소들은 우선순위를 갖고 우선순위 큐에서 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다. 즉, 임의의 순서로 삽입되지만, 정해진 순서로 삭제된다. push() : 하나의 원소를 우선순위를 지정하여 추가 pop() : 가장 높은 우선순위를 가진 원소를 큐에서 제거 후 반환 1. 우선순위 큐 구현해보기(최소힙으로 구현) class PriorityQueue : def __init__(self) : # 여기서 사용할 리스트는 완전 이진트리를 구현 # 0번 인덱스를 사용하지 않기 위해 0번에 None 삽입 self.items = [None] def __len__.. 2023. 4. 17.

[TIL] 백준 풀이 정리2 ※ 평일에 풀지 않고 넘긴 문제 풀이 ※ 1. 8983번 - 사냥꾼 import sys # M : 사대 개수 # N : 동물의 수 # L : 사정거리 M, N, L = map(int, sys.stdin.readline().split()) gun = list(map(int, sys.stdin.readline().split())) # 사대의 위치 gun.sort() animal = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 동물들의 위치 def hunt(gun, animal) : count = 0 # 동물의 위치를 반복 for x, y in animal : min_idx, max_idx = 0, len(gun)-1 # 동물을 잡을 .. 2023. 4. 16.

[TIL] 자료구조 - Queue + Hashing이란? 1. 스택 연습 문제 (10000번 - 원 영역) import sys # https://wonyoung2257.tistory.com/79 참고 N = int(sys.stdin.readline()) circles = [] for i in range(N) : x, r = map(int, sys.stdin.readline().split()) circles.append((x-r, '(')) # 중점을 기준으로 왼쪽에 있는 좌표 circles.append((x+r, ')')) # 중점을 기준으로 오른쪽에 있는 좌표 # x좌표 순으로 오름차순 정렬 & 같을 경우 ')' 문자를 가진 값이 앞으로 오도록 # 아스키 코드 : '(' = 72, ')' = 73 circles.sort(key = lambda x: (x[0].. 2023. 4. 15.

[TIL] Algorithm - 분할정복 + 스택 1. 이분 탐색 개념을 이용한 문제 풀이 (11053번 - 가장 긴 증가하는 부분 수열) import sys # A의 크기 N = int(sys.stdin.readline()) # 수열 A = list(map(int, sys.stdin.readline().split())) # https://namu.wiki/w/최장%20증가%20부분%20수열#s-3.2 참고 def LIS() : # d[i] = A[i]를 마지막 값으로 가지는 가장 긴 증가부분 수열 길이 d = [A[0]] for i in range(1, len(A)) : # d에 저장된 가장 마지막 값보다 현재 값이 크면 if d[-1] 0 ~ len(d)-1 사이.. 2023. 4. 14.

이전 1 ··· 3 4 5 6 7 8 9 다음

728x90

티스토리툴바