분류 전체보기
-
[백준] 1081 합 with PythonPS 2022. 7. 22. 20:06
📌 BOJ 1081 합 💡 조건 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 문제. 0 ≤ L ≤ U ≤ 2,000,000,000 수학 유형의 문제 🔖 예제 및 실행결과 예제 24660 308357171실행결과 11379854844⌨️ 문제 풀이 가장 먼저 문제를 보며 주목해야할 부분은 L과 U의 범위이다. L과 U의 범위는 최대 20억까지로, 일일히 검사했을 때 최악의 경우에는 0부터 20억까지의 모든 수를 검사해야하기 때문에 문제에서 주어진 2초라는 시간 안에 절대 해결할 수가 없다. (1)번에서 정리한대로, 우리는 L과 U의 범위를 입력받아 일일히 숫자 하나씩 검사하는 방법을 피해 각 숫자의 자릿수를 더해 답을 출력해야 한다. L, U 를 입력받아 L보다 크거나 같고..
-
[백준] 1005 ACM Craft with PythonPS 2022. 7. 17. 22:33
📌 BOJ 1005 ACM Craft 💡 조건 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경..
-
[백준] 17086 아기 상어 2 with PythonPS 2022. 7. 17. 22:03
📌 BOJ 17086 아기 상어 2 💡 조건 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. N과 M(2 ≤ N, M ≤ 50) 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다. 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다. 안전 거리가 가장 큰 칸을 구하는 문제. heapq, 우선순위 큐 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n, m =..
-
그래프의 개념과 표현자료구조 2022. 7. 17. 18:51
📌 그래프의 개념과 표현 💡 그래프 소개 그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 - 지하철 노선도, SNS 친구 관계, 컴퓨터 네트워크 💡 그래프 데이터 타입 그래프 G의 두가지 구성요소 V(G) : G에 포함된 Vertex(정점)들의 집합 E(G) : G에 포함된 Edge(간선)들의 집합 무방향성 그래프(Undirected Graph) Vertex 의 쌍을 나타내는 Edge가 방향성이 없다. (u, v), (v, u) 는 동일한 Edge 를 표현하는 것이다. EX) 지하철 노선도 방향성 그래프(Directed Graph) 각 Edge에 방향성이 존재하는 그래프 (u, v) : v -> v 인 Edge를 표현하는 것이다. u : Tail v : Head 💡 그래프에서 사..
-
이진 검색 트리자료구조 2022. 7. 17. 16:46
📌 이진 검색 트리 💡 이진 검색 트리(Binary Search Trees) 히프의 문제점 임의의 데이터를 갖는 노드를 삭제할 경우의 시간 복잡도 : O(N) 트리에서 특정 데이터를 갖는 노드를 검색하는 시간 복잡도 : O(N) 이진 검색 트리란? 트리 내에서 특정 데이터(Key 값) 을 갖는 노드를 효율적으로 검색 - O(Log N), 하지만 정렬된 상태를 유지해야한다. 이진 검색 트리의 정의 모든 노드는 유일한 키 값을 가지고 있다. 왼쪽 서브 트리에 저장된 키 값 루트 노드의 키 값 양쪽 서브 트리도 이진 검색 트리이다. 💡 검색 연산 기본 개념 if(key == root -> data) return if(key data..
-
히프의 개념과 응용자료구조 2022. 7. 17. 03:18
📌 히프의 개념과 응용 💡 히프(Heap)의 정의 최대 트리와 최대 히프 최대 트리(Max Tree) 트리의 모든 노드에 대해서 노드의 데이터 값이 자식 노드의 데이터 값보다 크거나 같은 트리 최대 히프(Max Heap) 최대트리 이면서, 완전 이진트리. 최소 트리와 최소 히프 최소 트리(Min Tree) 트리의 모든 노드에 대해서 노드의 데이터 값이 자식 노드의 데이터 값다 작거나 같은 트리 최소 히프(Min Heap) 최소트리 이면서, 완전 이진트리. 최대 히프의 root 노드는 항상 모든 노드들보다 큰 값을 가지고 있다. 최소 히프의 root 노드는 항상 모든 노드들보다 작은 값을 가지고 있다. 이는 가장 큰 값과 가장 작은 값을 찾기 쉬운 자료구조이다. 💡 우선 순위 큐(Priority Queue..
-
스레드 이진트리자료구조 2022. 7. 17. 02:41
📌 스레드 이진트리 💡 스레드 이진트리(Threaded Binary Tree) 스레드 이진트리의 기본 개념 n개의 노드를 갖는 이진 트리에는 2n 개의 링크가 존재한다. 2n 개의 링크 중에 n+1 개의 링크 값은 null이다. null 링크를 다른 노드에 대한 pointer 로 대체한다. (= Threads) 니는 루트를 제외한 모든 노드는 부모 노드가 있기 때문에 트리의 링크 수는 n-1 개이다. 스레드의 이용 ptr -> left_child = NULL 일 경우, ptr -> left_child 를 ptr의 중위행선자를 가리키도록 변경한다. 중위행선자(inorder predecessor) : 중위 순회에서 현재 노드 바로 앞에 나오는 노드 ptr -> right_child = NULL 일 경우, p..
-
[백준] 14495 피보나치 비스무리한 수열 with PythonPS 2022. 7. 17. 01:39
📌 BOJ 14495 피보나치 비스무리한 수열 💡 조건 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구하는 문제. 자연수 n의 범위는 (1 ≤ n ≤ 116) 이다. DP 유형의 문제 🖥 소스 코드 from sys import stdin dp = [0 for _ in range(120)] dp[0:3] = [1, 1, 1, 2] for x in range(4, 117): dp[x] = (dp[x - 3] + dp[x - 1]) print(dp[int(stdin.readline()) - 1])🔖 예제 및 실행결과 예제 10..
-
[백준] 10159 저울 with PythonPS 2022. 7. 17. 01:25
📌 BOJ 10159 저울 💡 조건 무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.) [1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5] 우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다..
-
이진트리의 추가 연산자료구조 2022. 7. 15. 00:57
📌 이진트리의 추가 연산 💡 이진트리의 추가 연산 추가 연산의 종류 이진트리의 복사 이진트리가 동일한지 검사 이진트리의 노드 수 계산 이진트리의 단말 노드 수 계산이진트리의 모든 노드들을 모두 한번씩 다 방문해야 한다. 트리의 모든 노드들을 방문할 필요성 이진트리의 순회 알고리즘 등을 응용한다. 💡 이진트리의 복사 문제 설명 입력 이진트리의 노드 구조와 동일한 새로운 이진트리를 생성하고 루트 노드의 주소 반환 후위순회 알고리즘을 사용한다. 💡 이진트리의 복사 알고리즘 struct node *copy(struct node *original){ # original 트리를 복사한 새로운 이진트리를 반환한다. struct node *temp; if(original != NULL){ temp = (struct n..