전체 글

👇 관련 백준 문제https://www.acmicpc.net/problem/1753 그래프에서 사용하는 최단경로 알고리즘한 노드에서부터 도달할 수 있는 모든 노드까지의 최단경로를 찾는다.힙을 사용해서 구현하는방법과 선형탐색으로 구현하는 방법이 있는데, 힙을 사용하는 편이 동작속도가 빠르므로 힙을 사용해서 구현하는 방법만 다루겠습니다. ❓ 힙을 사용하는게 빠른 이유 ❓다익스트라 알고리즘에서는 매번 시작노드와의 거리가 가장 짧은 노드만을 선택해야 합니다. 그 이유는 최단거리를 갱신하는 알고리즘이기 때문에 현재 탐색한 경로 외에 더 짧은 미탐색 경로가 있을 경우 제대로 갱신되지 않을 수 있기 때문입니다.따라서 선형탐색으로 가장 짧은 노드를 일일이 확인하는 것 보다 노드 길이를 기준으로 힙에 넣어서 최단거리를..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com ✅ 문제 설명NxN 크기의 공간이 있다. 이 공간에는 섬과 같은 지나갈 수 없는 장애물과, 주기적으로 사라졌다 나타나는 소용돌이 같은 장애물이 존재한다. (섬 - 1, 소용돌이 = 2, 나머지는 바다 = 0) 이때 소용돌이는 생성되고 2초동안 유지되다가 1초간 잠잠해진다. (0초에 생성된다. 0초,1초까지 유지되고 2초에 사라짐, 3,4초에 생성되고 5초에 사라짐.. 반복 + 한번 통과한 소용돌이 위에는 머물러 있을 수 있다.) 이런 조건 하에서 시작점 -> 도착점까지 도달할 수 있는 최단 시간을 찾으면 되는 문제였다.  ✅ 접근 방식우선 시작점-> 도착점까지 최단 ..

https://www.acmicpc.net/problem/7579 ✅ 문제 설명M바이트의 메모리가 필요하다. 활성화되어있는 앱 A1~AN중에서 몇개를 비활성화해서 M 이상의 메모리를 추가 확보하자. 이 때 비활성화했을 때의 비용의 최소화하여 M이상의 바이트를 확보하자!✅ 접근 방식처음에 DP문제인 0-1 knapsack인 것까진 파악을 했다.근데 왜 못 풀었지..?음.. 나는 너무 메모리에 대해서만 집중하고 가격에 대해서 for문을 돌 생각을 못했던 것 같다.knapsack[i][j]는 i번째 앱까지 고려했을 때, j비용으로 얻을 수 있는 최대 메모리 값이다.가로축을 비용, 세로축을 선택지으로 두고, 표의 안쪽을 얻을 수 있는 가치로 기록한다고 생각하면 된다. ✅ 코드 설명import sysn, m = ..

https://www.acmicpc.net/problem/11000 ✅ 문제 설명Si에 시작해서 Ti에 끝나는 N개의 수업이 주어질 때, 최소의 강의실을 사용해서 모든 수업이 가능하게 하자!수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다. 즉 3초에 끝난 수업이 있다면 같은 강의실에서 다른 수업을 3초에 시작할 수 있다는 것이다.)✅ 접근 방식나는 우선순위 큐에 (시간, 타입)으로 튜플을 넣어줬다.31 32 43 5 이런식으로 들어온다면(1, "S")(3, "E")(2, "S")(4, "E")(3, "S")(5, "E") 그래서 우선 순위큐를 돌면서 pop하면서 S이면 강의실을 하나 늘렸고, E면 강의실을 하나 줄였다.근데 이때, ..

https://www.acmicpc.net/problem/2015 ✅ 문제 설명수열이 주어졌을 때, 부분합이 K인 것이 몇개나 있는 지 구하는 문제다.✅ 접근 방식처음에는 인덱스 0부터 N-1까지 돌면서 해당 인덱스부터 시작하는 배열의 부분합을 구해, K가 나오는 수를 계산하려고 했다.-> 근데 이 방법은 1 ≤ N ≤ 200,000이므로, O(N^2)이 소요되면 40,000,000,000(4백억..) 절대 2초만에 들어올 수 없을 것이다. 그래서 나도 사실 답을 보고 왔다!알고리즘 분류에 해시, 트리를 사용한 집합과 맵이라 되어있어 이게 뭘까..? 딕셔너리를 사용하는 걸까 싶었는데,역시 딕셔너리를 사용하더라! 똑똑해.. ✅ 코드 설명dict = {0: 1} # 누적합을 기록해둘 딕셔너리우선 인덱스 0부..

17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net ✅ 문제 설명 1번 정점(루트)에 W만큼의 물이 고여있고, 다른 정점들에는 물이 고여있지 않은 상태입니다. 이때 모든 정점은 아래의 작업을 매초 마다 반복합니다. 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 동일한 확률로 그 중 하나를 고른다. 만약 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아 둔다. 위 작업이 다 끝나서 더 이상 물이 움직이지 않을 때..

2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net ✅ 문제 설명 BOJ_4256 문제와 비슷한 문제입니다. (https://wnszero.tistory.com/10) 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더를(전위순회) 구하는 문제입니다. ✅ 접근 방식 중위순회, 후위순회 2개의 결과를 종합하여 각각의 결과에서의 루트와 왼쪽서브트리, 오른쪽 서브트리를 알아내고, 이를 이용해서 (루트)(왼쪽 서브트리)(오른쪽 서브트리)순으로 탐방순서를 배치해 전위순회를 시행하면 원하는 결과를 얻을 수 있습니다. ✅ 코..

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net ✅ 문제 설명 이진 트리의 전위순회, 중위순회 결과가 주어졌을 때, 후위 순회의 결과를 유추하는 문제입니다. 이때, 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어집니다. ✅ 접근 방식 저번 포스팅이었던 이진 검색 트리에서 썼던 로직과 같은 로직을 이용했습니다. (참고) [BOJ_5639] 이진 검색 트리 (python) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작..