본문 바로가기

알고리즘/백준

 (263)
[백준] 16235번 : 나무 재테크 16235번: 나무 재테크 해당문제는 구현 문제로, 봄,여름,가을,겨울을 각각 나누어서 기능들을 구현 하면 문제를 쉽게 해결 할 수 있습니다. 봄 나무가 자신의 나이만큼 양분을 먹는다 1x1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 자신의 나이만큼 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다. 💡 봄에서의 가장 큰 포인트는 나이가 어린 나무부터 양분을 먹으므로 우선순위 큐를 사용해야합니다. 여름 죽은 나무가 양분으로 변하게된다, 죽은 나무는 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 가을 나무가 번식하고, 나무는 나이가 5의 배수이어야하며 인접한 8개의 칸에 나무가 1인 나무가 생긴다. 상도의 땅을 벗어..
[백준] 15685번 : 드래곤 커브 해당 문제는 구현문제로 n+1 세대의 드래곤의 커브는 n드래곤커브를 회전시킨뒤 확장하는 구현을 해야합니다. 또한 정사각형의 네 꼭지점이 모두 드래곤 커브의 일부인 것의 개수를 카운팅 하는것을 구현해야한다. n세대의 드래곤 커브 만들기 드래곤 커브를 만들때 만드는 과정을 저장해야한다. 시작점이 0,0 이고, 방향이 0인 0세대의 드래곤 커브는 (0, 0), (0,1) 이다. 그다음 1세대 드래곤 커브는 0세대의 드래곤커브를 복사, 90도 회전시킨뒤 기존에 있던 0세대의 드래곤커브에 추가한다. 90도를 회전시킬때에는 기존에 있던 n-1 세대의 드래곤커브의 방문 큐값을 시계방향으로 회전시킨다 정사각형 네 꼭지점이 모두 드래곤 커브의 일부인것의 개수를 카운팅한다. 특정 점으로부터 (1,0) (0,1), (1,1..
[백준] 14718번 : 빗물 14719번: 빗물 해당 문제는 stack 자료구조를 활용하여 문제를 해결하였습니다. 각각의 열을 순회합니다. 각각의 열의 순회에 대하여 스택에 빗물, 블록을 구분하여 추가합니다. 현재 블록을 만났고, 바로 직전에 빗물이 나왔다면 모든 스택을 꺼냅니다. 모든 스택을 꺼냇음에도 블록이 나오지않았다면 빗물은 가둬질 수 없으므로 무시합니다. 모든 스택을 꺼냇을때 블록이 하나이상 나왔다면 빗물은 가둬질 수 있으므로 가중치에 결과를 누적합니다. H, W = map(int, input().split()) table = [[0 for _ in range(W)] for _ in range(H)] temp = list(map(int, input().split())) for i in range(len(temp)): h =..
[백준] 9012번 : 괄호 9012번: 괄호 해당문제는 스택이라는 자료구조를 활용하여 문제를 해결 할 수 있습니다. 괄호는 반드시 “(”와 “)” 쌍으로 이루어 져야 합니다. 이를 바탕으로 문제를 해결 할 수 있습니다. 문자열이 주어졌을때 “(”가 나온다면 스택에 넣습니다. “)”가 나온다면 이전에 스택에 “(”인지 확인합니다. “(” 가 아니라면 괄호는 성립될 수 없습니다. “)”가 나온다면 “)”를 스택을 꺼낸뒤 이어갑니다. 모든 문자열을 순회한뒤 스택이 비어있지 않다면 “(”뒤에 “)”가 나와야하는데 나오지 않았음으로 쌍이 맞지 않습니다. T = int(input()) for _ in range(T): char = input() stack = [] flag = True for i in range(len(char)): if c..
[백준] 20040번 : Cycle Game 해당 문제는 서로소 집합 문제로 사이클이 생겼는지 안생겼는지에대한 판별을 하는 문제이다. 💡 여기서 실수한건 union 함수에서 각각의 원래의 부모의 값을 업데이트 해주어야 하는데, 자기자신의 부모값을 업데이트 하는 실수를 하였다. 또한 M 번째에서 사이클이 발생할 경우도 예외 처리를 해주어야한다. import sys input = sys.stdin.readline N, M = map(int, input().split()) parent = [i for i in range(N)] def find(v1): if parent[v1] != v1: parent[v1] = find(parent[v1]) return parent[v1] else: return v1 def union(v1, v2): p1 = find(..
[백준] 10775번 : 공항 10775번: 공항 해당 문제는 소로소 집합 문제로 G(i)가 4일경우 첫번째 방문을 할때에, 부모를 3으로 가르키게 한다. 3을 가리키게 함으로서 4번 도킹에는 비행기를 이륙 시킨 셈이다. 따라서 이후에 4번이 들어온다고해도 3번을 가르키기 때문에 3번 도킹에 이륙하게된다. import sys input = sys.stdin.readline G = int(input()) P = int(input()) parent = [i for i in range(G+1)] def find(v1): if parent[v1] != v1: parent[v1] = find(parent[v1]) return parent[v1] else: return parent[v1] def union(v1, v2): p1 = find(v1..
[백준] 1189번 : 컴백홈 1189번: 컴백홈 해당 문제는 RxC 2차원 배열이 주어졌을때 왼쪽 아래에서 오른쪽 위까지 갈 수 있는 모든 경우의 수를 탐색하면 된다. R, C가 매우 작으므로 모든 경우의 수를 탐색하여 경우의 수를 카운팅 하면된다. 💡 여기서 중요한점은 이미 방문한 경로를 여러번 샐 수 있는 경우의 수를 고려해야한다. import sys si = sys.stdin.readline R, C, K = map(int, si().split()) move = ((0, 1), (0, -1), (1, 0), (-1, 0)) graph = [ si().strip() for _ in range(R)] s_y = R-1 s_x = 0 e_y = 0 e_x = C-1 visit = dict() ans = 0 def dfs(i,j, v..
[백준] 7579번 : 앱 7579번: 앱 해당 문제는 다이나믹 프로그래밍 문제로 배낭문제와 비슷 합니다. dp[i][j]는 메모리의 크기라고 하면 i는 Ai번째를 추가하는경우와 추가하지 않는 경우이며 j는 j의 비활성화의 가중치 값이다. 앱 Ai를 추가할때와 추가하지 않을때의 최대값을 구한다. 메모리가 빠르게 채워지면서 메모리가 M이상 채워 졌을때 j값의 최소값을 찾으면 된다. 아래는 예제 문제 1번을 테이블로 그려보았다. import sys input = sys.stdin.readline N, M = map(int, input().split()) A = [0] + list(map(int, input().split())) C = [0] + list(map(int, input().split())) dp = [[0 for _ in ..

티스토리툴바