본문 바로가기

알고리즘/백준

 (36)
[백준]16953 A->B(Python) https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B 1. 2를 곱한다. 2. 1을 수의 가장 오른쪽에 추가 1, 2의 연산을 반복해서 A => B로 바꾸는데 필요한 연산의 최솟값 + 1 or -1 출력 문제 접근 그리디라는 생각은 들었지만 2번 연산이 좀 까다롭다고 느껴졌다. top-down방식을 사용해 B를 A로 만든다고 가정하면, 일의 자릿수가 1이라면 1을 제거 그렇지 않다면 2로 나누기 코드 시간 초과 import sys input = sys.stdin.readline cnt = 1 A, B = map(int, input().split()) ..
세그먼트 트리(Segment Tree) & [백준]2042 구간합(Python) 개념 및 특징 완전 이진 트리를 기반으로, 각 노드가 구간의 정보(구간합, 구간의 최솟값 등에 대한)를 저장하고 있는 자료구조 리프 노드들은 길이가 1인 각각의 구간을 소유 부모 노드는 자신의 자식 노드들의 구간의 합 소유 => 루트 노드는 전체 구간을 포함 모든 구간은 연속적 시간 복잡도 및 공간 복잡도 원하는 구간합을 구하고자 한다면, 시간 복잡도: O(logN) => 장점 공간 복잡도: 메모리가 많이 필요 => 구간합을 모두 저장해야하므로 => 단점 구현 1. Top → Down : 재귀 사용 ✔ 2. Bottom → Up : For 반복문 사용, 코드 구현 간편 초기화 def init(start, end, node): if start == end: # 리프 노드 tree[node] = nums[s..
[백준]11437 LCA(Python) https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 접근 LCA(Lowest Common Ancestor): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 ♣ 동작 방식 모든 노드에 대한 깊이(depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이가 동일하도록 거슬러 올라간다. (첫 번째 while문) 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. (두 번째 ..
[백준]16927 배열 돌리기2(Python) https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 문제 접근 우선, 규칙성을 찾아서 반복문 내에 조건식을 작성해야겠다고 생각했다. 행과 열이 동시에 바뀌는 경우는 존재하지x 1. j = 0, i ≠ N-1 인 경우: 행이 아래로 이동 열은 고정 i => i + 1 j => j 2. j = 0, i = N-1 인 경우: 열이 오른쪽으로 이동 i => i ..
[백준]2096 내려가기(Python) https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 코드 import sys input = sys.stdin.readline # 3열이 N개의 계단이 존재 N = int(input()) # 첫 번째 계단(0) row = list(map(int, input().split())) max_dp = row min_dp = row # 두 번째 계단부터 마지막 계단까지 for i in range(1, N): l, m, r = map(int, input().split()) ..
[백준]3665 최종순위(Python) https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 문제 접근 5번과 3번의 상대적인 순위 관계가 바뀐다면, 5번그래프에 3번을 빼주어야 하고 3번 그래프에 5를 넣어주어야 한다. => 3번으로 들어오는 간선이 하나 줄어들고, 5번으로 들어오는 간선이 하나 늘어났으므로 차수(indegree)도 변경 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력 한 번에 2개 이상의 원소가 들어간다는 것은 진입차수가 0..
[백준]1766 문제집(Python) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 접근 선행 문제를 풀어야 후행 문제를 풀 수 있다는 점에서 위상정렬 알고리즘을 사용해야한다. 하지만 답이 여러 개인 경우에는 아무거나 출력한다는 조건이 없기에 정답은 하나이다. 이 문제의 조건에서는 "가능한 쉬운 문제부터 풀어야 한다"라는 조건이 있다. 코드 from collections import deque import sys import heapq inpu..
[백준]1005 ACM Craft(Python) https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 접근 시도1. (실패) 어제와 정리한 위상정렬 함수를 변형해서 작성하였다. 1. 건물의 건설 시간을 담을 리스트를 인덱스에 대응시켜서 만든다. 2. 특정 건물(W)까지 짓는데 걸리는 시간을 total_cost라는 변수에 누적해서 결과로 출력한다. => 예제 1 출력 결과: 121 52 수정(성공) 코드 시도1 from collections import deque import sys in..

티스토리툴바