백준 문제풀이 코드저장소 (81) 썸네일형 리스트형 Baekjoon 2263. 트리의 순회 / Python 2263. 트리의 순회난이도 : 골드 1소요 시간 : 10분날짜 : 2024.12.30언어 : 파이썬알고리즘 유형 : 재귀, 트리, 분할 정복설명 보기전에 문제 풀어보러 가기1. 문제 설명트리의 크기 n이 주어짐중위순회(inorder)와 후위순회(postorder)가 주어짐전위순회(preorder)결과를 구하기.2. 해결 방식중위순회는 왼쪽부터 하위트리를 우선으로 트리를 방문 후 루트를 방문하는 방식후위순회는 왼쪽부터 "하위트리를 모두 방문한 후" 루트를 방문하는 방식전위순회는 루트노드부터 시작하여 왼쪽 자식먼저 방문하는 방식재귀함수의 원리 및 사용후위순회의 마지막 요소는 현재 서브트리의 루트 노드이다.중위순회에서의 루트를 기준으로 왼쪽, 오른쪽으로 서브트리를 나눈다.루트 노드를 출력한다.(전위순회)3... Baekjoon 12850. 본대 산책 2 / Python 12850. 본대 산책 2난이도 : 골드 1소요 시간 : 15분날짜 : 2024.12.29언어 : 파이썬알고리즘 유형 : 행렬, 그래프, 분할 정복설명 보기전에 문제 풀어보러 가기1. 문제 설명그래프가 주어진다. 만들어야 한다. 귀찮다....d분동안 산책한다.정보과학관을 돌아오는 경로의 경우의 수를 구한다.2. 해결 방식행렬에 대한 이해를 필요로 하는 문제이다.i분 산책한 경로 배열 * j분 산책한 경로 배열 을 하면 i+j분 산책을 한 경로를 구할 수 있다.이를 활용하면 시간복잡도를 log2(d)로 해결가능.3. 정답 코드# 숭실대 지도 그리기arr = [[0] * 8 for _ in range(8)]arr[0][1], arr[1][0] = 1, 1arr[0][2], arr[2][0] = 1, 1arr.. Baekjoon 28707. 배열 정렬 / Python 28707. 배열 정렬난이도 : 골드 1소요 시간 : 20분날짜 : 2024.12.28언어 : 파이썬알고리즘 유형 : 다익스트라, 그래프, 해시, 트리, 최단 경설명 보기전에 문제 풀어보러 가기1. 문제 설명배열 A가 주어진다.커맨드 l, r, c가 주어진다 : l과 r을 바꾼다. c의 비용이 든다.커맨드들을 이용해서 최소비용으로 정렬하라.2. 해결 방식배열을 문자열로 저장한다.배열을 목표배열까지 가는 최소경로를 구하면 된다.다익스트라를 활용하여 최소비용을 구한다.3. 정답 코드import sysinput = sys.stdin.readlinefrom heapq import heappop, heappushfrom collections import defaultdictn = int(input()) # .. Baekjoon 10775. 공항 / Python 10775. 공항난이도 : 골드 2소요 시간 : 15분날짜 : 2024.12.28언어 : 파이썬알고리즘 유형 : 그리디, 분리집합설명 보기전에 문제 풀어보러 가기1. 문제 설명G개의 게이트와 P개의 비행기가 있다.비행기를 게이트에 도킹해야 한다.$g_i$가 입력으로 주어지고, 1 ~ $g_i$ 의 게이트에 i번 게이트를 도킹해야한다.게이트에 도킹을 할 수 없으면 끝도킹 수의 최댓값을 구하자.2. 해결 방식union-find 알고리즘을 사용한다. - 게이트에 각자의 게이트 번호를 부여한다. - 비행기번호를 union-find를 통해 게이트 집합을 만들어 관리한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.. Baekjoon 19236. 청소년 상어 / Python 19236. 청소년 상어난이도 : 골드 2소요 시간 : 35분날짜 : 2024.12.27언어 : 파이썬알고리즘 유형 : 백트래킹, 구현, 시뮬레이션설명 보기전에 문제 풀어보러 가기1. 문제 설명상어 이동, 물고기 이동 을 반복함.상어 이동경계 안에서만 이동물고기가 있는 곳으로만 이동여러 칸 이동 가능물고기의 방향을 흡수?함이동 불가 : 집으로 감물고기 이동번호 작은 물고기부터 순서대로 이동경계 안에서만 이동한 칸만 이동상어 있는 곳으로 이동 불가다른 물고기가 있다면 자리 교체이동 불가 : 이동 안함"잡아먹은 물고기 번호의 합"의 최댓값을 구하라.2. 해결 방식dfs + 백트래킹상어 이동방향에 맞게 이동시키고 해당 자리의 물고기를 배열에서 없앤다.이동할 때마다 res를 max 값으로 갱신했다.물고기 이동각.. Baekjoon 9527. 1의 개수 세기 9527. 1의 개수 세기난이도 : 골드 2소요 시간 : 25분날짜 : 2024.12.27언어 : 파이썬알고리즘 유형 : 수학, 비트마스킹, 누적 합설명 보기전에 문제 풀어보러 가기1. 문제 설명$(x)$는 $x$를 이진수로 표현했을 때에 1의 개수를 의미 한다.$a, b$가 주어지면 $$\sum_{x=a}^{b} f(x)$$ 를 구한다.2. 해결 방식음 나는 그냥 재귀함수와 수학으로 풀었는데. 알고리즘 유형은 비트마스킹과 누적 합이라고 한다.내가 사용한 비트마스킹은 연산을 전혀 사용하지 않고 2 ** index를 left shift를 이용해서 표현한 것 뿐..$c = 2 ^ n$ 일 때, $$\sum_{x=0}^{c} f(x) = \frac{n * c}{2} + 1$$ 이다.따라서, $x$ 보다 작은 .. Baekjoon 1766. 문제집 / Python 1766. 문제집난이도 : 골드 2소요 시간 : 20분날짜 : 2024.12.26언어 : 파이썬알고리즘 유형 : 위상정렬, 방향 비순환 그래프, 우선순위 큐, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명n개의 문제를 모두 풀어야 한다.문제 번호가 낮으면 더 쉬운 문제이다.쉬운 문제를 먼저 풀어야 한다.먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.2. 해결 방식위상정렬과 우선순위큐를 활용하여 해결한다.먼저 해결해야하는 문제가 주어졌다 == 위상정렬쉬운문제(번호가 낮은 문제)를 먼저 풀어야 한다 == 우선순위 큐그냥 큐를 사용해서 푸는 위상정렬 문제에서 큐를 우선순위 큐로 바꾸면 해결된다.문제 번호 낮은게 먼저 풀어야 하기 때문에, 그냥 우선순위 .. Baekjoon 1509. 팰린드롬 분할 / Python 1509. 팰린드롬 분할난이도 : 골드 1소요 시간 : 40분날짜 : 2024.12.25언어 : 파이썬알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명문자열이 주어진다 (길이 문자열을 팰린드롬으로 분할한다.분할 개수의 최솟값을 구한다.2. 해결 방식dp를 두개 활용했다.팰린드롬 dp : dp_pldm[i][j] = i인덱스부터 j인덱스까지 팰린드롬인가?의 여부길이 1, 길이 2인 팰린드롬을 먼저 저장한다.길이 3이상인 경우 dp 알고리즘을 활용한다. -> 시작, 끝이 같고, 내부가 팰린드롬이면 팰린드롬이렇게 하면 모든 경우의 수를 찾을 수 있음.분할수 dp : dp_res[i] = 0번 부터 i번 까지 팰린드롬 최소 분할 수dp값을 모두 0으로 해준다.끝점(j)의 인덱스를 0부터 문자.. Baekjoon 16946. 벽 부수고 이동하기 4 / Python 16946. 벽 부수고 이동하기 4난이도 : 골드 2소요 시간 : 40분날짜 : 2024.12.24언어 : 파이썬알고리즘 유형 : bfs, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 센다.2. 해결 방식시간 줄이기*맵의 크기가 최대 1000 * 1000 이기 때문에 그냥 bfs를 돌리면 시간복잡도가 10^12로 시간초과가 난다.시간을 줄이기 위해 집합과 인덱싱을 사용한다.인덱싱 -> 유니온파인드 알고리즘과 유사한 방법풀이벽인 곳을 찾는다.벽의 상하좌우에서 벽이 아닌 곳을 찾는다.벽이 아닌 곳에서 bfs를 돌린다.이 때, bfs를 돌려서 이동가능한 공간에 인덱스 번호를 부여하고,인덱스 번호에 맞는 리스트를 만들어.. Baekjoon 2143. 두 배열의 합 / Python 2143. 두 배열의 합난이도 : 골드 3소요 시간 : 25분날짜 : 2024.12.23언어 : 파이썬알고리즘 유형 : 이분탐색, 누적 설명 보기전에 문제 풀어보러 가기1. 문제 설명정수 t와 배열 a, 배열 b 가 주어진다.배열 a와 배열 b에서 각각 모든 원소가 연속된 배열을 선택한다.선택된 배열들의 숫자의 합이 t 가 되는 경우의 수를 구한다.2. 해결 방식배열a 와 배열 b 에서 나올 수 있는 모든 합을 구해서 딕셔너리형태로 저장했다.배열a 를 순회하여 그 값(key)과 개수(value)를 구하고 배열 b에서 t - key의 value(개수)를 찾아서 곱한 후, 결과에 누적한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/pyth.. 이전 1 2 3 4 ··· 9 다음
