백준

단계별 풀이 중 최단경로 단계에서 첫번째 문제인 최단경로 문제이다.오늘 다익스트라 알고리즘을 여러문제 풀 것 같아서 어제밤에 미리 알고리즘 영상들을 많이 봐둔게 오늘 문제 푸는데 도움이 많이 된 것 같다.먼저 다익스트라 알고리즘에 대해서 관찰 알아봐야 할 것 같다.다익

이번 문제는 최단 경로 문제에서 조건이 붙는 경우의 문제이다.주어진 조건은 임의로 주어진 두 정점을 반드시 통과했을 때의 최단경로이다.v1과 v2를 꼭 지나야한다는 조건이라고 하자.그럼 경우의 수는 두 가지가 있다. start->v1->v2->end, start->v2

저번에 DFS/BFS 단계별 문제에서 풀어보았던 BFS 문제이다.이번 조건에서는 순간이동을 하는 경우만 가중치가 0으로 따져야 하는 문제이다.start부터 -1,1,2배를 탐색하며 조건에 부합할 경우 distance 최단 경로를 업데이트 하는데 \-1과 1의 경우는 가

이번 미확인 도착지 문제도 특정한 최단 경로와 매우 비슷한 문제이다.특정 구간을 꼭 지나가야한다는 조건이 같고 여러 도착지가 있을 수 있다는 조건이 달린 문제이다.문제에서는 주어진 조건인 상태에서 최단 경로인 상황인 도착지들을 출력하는 문제이다.제일 처음에는 문제를 제

기본 다익스트라 알고리즘 문제에서 가중치가 -가 있을 경우 음수 간선의 순환이 발생할 수 있다.음수 간선의 순환이란 가중치에 음수가 섞여있을 때 최단 거리가 음의 무한인 노드가 발생하는 상황을 의미한다.이렇게 될 경우 최소 비용이 어디든지 -무한대가 될 수 있는 상황이

주어진 문제에서는 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성해야 한다.이번 문제 같은 경우는 최단 경로를 구하는 알고리즘 중 플로이드 워셜 알고리즘을 사용하는 문제이다.즉 주어진 도시의 개수가 N개라면 i번째 줄에 0~N개까지의 최단 경로를

해당 문제는 두 마을 즉, 두 개의 정점을 왕복할 수 있는 사이클을 찾고 그 사이클중에서의 최솟 값을 찾으라는 문제이다.주어진 조건 중 정점 V와 간선 E의 범위를 보았을 때 V가 400이하 인 것을 보았을 때 플로이드 워셜 알고리즘의 시간복잡도인 O(N^3)에 들어가

무려 7번 틀리고, 2번 시간 초과가 난 다음에 10번째로 맞은 문제이다.그래도 이 모든 과정이 1시간안에 이루어진 과정이라 다행이다.제일 처음 풀이법은 3중 for문을 이용해서 답을 구하는 과정이었는데 물론 이 방법엔 오류도 있었고 구현이 된다고 해도 시간초과로 틀리

스택의 성질을 이용하는 문제이기에 쉽게 풀 수 있었던 문제이다.1부터 n까지 미리 저장해둔 temp에서 1부터 꺼내와서 stack에 넣기 시작한다.만약 stack의 -1값과 지금 들어가야할 정답값과 동일하면 stack과 arr에서 둘다 pop을 해주고 result에 -

이 문제는 기본적인 큐 자료구조를 사용하기 위해 deque를 이용하였다.

오늘은 백준 단계별로 풀어보기에서 투 포인터 부분을 풀 차례이다.투 포인터 개념 자체가 크게 어렵지 않아서 여기에 있는 5문제 모두 풀었다.어렵지 않더라도 개념자체는 많은 곳에서 효율적으로 쓰일 수 있는 알고리즘이라 정확하게 이해하고 어느 부분에 쓰일 수 있을지를 파악

해당 문제는 두 값의 합이 0에 가까울 경우의 조합을 구하는 문제이다.시간복잡도를 O(N)의 투 포인터로 풀기 위해 입력받은 리스트를 정렬을 해준다.투 포인터를 양 끝에서 시작하며 두 수의 합의 절댓값을 비교한다.두 수의 합의 절댓값을 비교 변수와 비교해주고 비교 변수

해당 문제는 주어진 길이 N짜리 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는 것중 가장 짧은 것의 길이를 구하는 문제이다.해당 문제는 주어진 수열을 그대로 사용해야하는 문제이기 때문에 정렬하지 않은 상태에서 문제를 풀어야 한다.s = start, e =

해당 문제는 위의 문제와 유사하지만 소수들이 배열을 이용해야 한다는 차이점이 있다.결국 소수를 또 효율적으로 구해줘야 하는 문제이기에 에라토스테네스의 체를 이용한다.제일 처음에는 set자료형을 이용해서 빠르게 구하는 방식을 사용했는데 이 방식을 사용했을 때 메모리 초과

해당 문제는 N개의 물건을 가지고 있고, 최대 M만큼의 무게를 넣을 수 있는 가방에 N개의 물건을 가방에 넣는 방법의 수를 구하는 문제이다.결국 모든 경우의 수를 다 구해야하는 문제이기에 효율적인 알고리즘을 사용해야하는게 포인트이다.효율적인 시간복잡도MITM을 사용하지

동적 계획법과 최단거리 역추적 단계이다. 지금까지 했던 동적 계획법에서 최단거리 역추적을 어떤 방법으로 할지 정하면 되는 문제들로 구성되어 있다. 기본적으로 역추적 할 때의 상황은 값이 업데이트 될 때 마다 이루어진다. 그 후로는 기준이 되는 값에서 부터 해당 inde

가장 긴 증가하는 부분 수열은 i와 j가 있을 때 (i > j) ,(arri > arrj)인 조건이 만족할 때 di = dj + 1을 할 수 있는 알고리즘을 가지고 있다.만약 해당 조건에 만족해서 di가 업데이트 될 때, di < dj + 1 and arri >

프로그래머스 [Summer/Winter Coding(~2018)] : 배달 (Lv. 2 48%) 다익스트라 알고리즘을 이용한 기본 문제이다. 추가로 두번째 예제를 보았을 때 [3,5,2] [3,5,3]으로 같은 경로에 다른 가중치가 있을 수가 있다. 이를 주의하고 g

BaekJoon 9252번 : LCS 2 (G4 37.888%) LCS 2 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 이전의 LC

지금까지 풀어보았던 BFS 숨바꼭질의 역추적을 더한 문제이다.이전에 풀었던 숨바꼭질 문제는 순간이동의 가중치가 달랐기 때문에 Dijkstra로 풀었지만 이번 문제는 가중치가 1로 같으므로 BFS를 이용해서 풀 수 있다.반복문을 통해 -1, 1, x(자신)의 값을 통해

플로이드 워셜 알고리즘을 이용해 최단경로를 구하고 해당 최단경로를 역추적 하는 문제이다.플로이드 워셜 알고리즘 자체를 구현하는 것은 어렵지 않았다. a부터 b까지 다이렉트로 가는 값과 k를 거쳐 가는 값을 비교해가며 더 작은 값으로 업데이트를 하면 되는 문제이기 때문이

DP 역추적 문제중에 가장 어려웠던 문제인 것 같다. 사실은 아직도 완벽히 이해했다고 보기 어려운 문제인 것 같다.이번 문제에서 dp를 어떻게 설정할 것이냐부터 고비가 있었다. 사실 dpi라 하였을 때 i를 1번 경찰차의 마지막 사건, j를 2번 경찰차의 마지막 사건이

bfs를 이용한 최단거리 문제 + 역추적 조건이 달린 문제이다. 다른 문제들에 비해 시간 제한이 까다로운 문제라서 정답률이 상당히 낮은 것 같다.각 D,S,L,R의 x를 변형하는 조건이 다르기 때문에 이 부분에서의 점화식만 잘 생각하면 될 것 같았다.D는 기본적으로 x

다익스트라 알고리즘을 이용한 가중치가 다른 노드 사이에서 최소 비용을 구하는 문제에 역추적 조건이 더해진 문제이다.기본적인 다익스트라 알고리즘을 구현한다. 다익스트라 알고리즘은 heapq 자료구조를 이용해서 문제를 풀게된다. heapq 자료구조를 이용해서 가장 가까운,

BaekJoon 11725번 : 트리의 부모 찾기 (S2 42.454%) 트리의 부모 찾기 문제 느낀점

BaekJoon 1167번 : 트리의 지름 (G2 33.981%) 트리의 지름 문제 이번에는 BFS or DFS를 두 번 이용하여 가장 긴 길이를 찾는 문제이다. 느낀점

BaekJoon 1967번 : 트리의 지름 (G4 40.726%) 트리의 지름 문제 느낀점

BaekJoon 1991번 : 트리 순회 (S1 66.940%) 트리 순회 문제 개선된 코드

BaekJoon 2263번 : 트리의 순회 (G1 32.695%) 트리의 순회 문제 느낀점 inorder, postorder, preorder의 특징

BaekJoon 5639번 : 이진 검색 트리 (G4 37.780%) 이진 검색 트리 문제 > #### GPT 오른쪽 자식 노드의 시작 지점 설정: root 변수는 현재 노드(현재 서브트리의 루트 노드) 다음에 오는 첫 번째 오른쪽 자식 노드의 인덱스를 나타냅니다.

BaekJoon 4803번 : 트리 (G4 32.231%) 트리 문제

BaekJoon 1717번 : 집합의 표현 (G5 28.095%) 집합의 표현 문제

BaekJoon 1976번 : 여행 가자 (G4 36.931%) 여행 가자 문제

BaekJoon 4195번 : 친구 네트워크 (G2 26.552%) 친구 네트워크 문제 비슷하지만 더 간결한 풀이

BaekJoon 20040번 : 사이클 게임 (G4 50.415%) 사이클 게임 문제

BaekJoon 9372번 : 상근이의 여행 (S4 60.783%) 상근이의 여행 문제

BaekJoon 1197번 : 최소 스패닝 트리 (G4 41.216%) 최소 스패닝 트리 문제

BaekJoon 4386번 : 별자리 만들기 (G3 58.423%) 별자리 만들기 문제

BaekJoon 1774번 : 우주신과의 교감 (G3 30.827%) 우주신과의 교감 문제

BaekJoon 6497번 : 전력난 (G4 34.396%) 전력난 문제

BaekJoon 17472번 : 다리 만들기 2 (G1 33.169%) 다리 만들기 2 문제

DFS를 이용한 트리 탐색 + DP문제이다.주어진 루트 노드를 이용하여 DFS를 통해 리프노드까지 내려갔다가 올라오면서 해당 루트 노드의 개수를 업데이트 하는 방식을 이용한다.DFS를 통해 방문할 때 마다 방문여부를 확인해주고 만약 이미 방문한 노드라면 dp 업데이트를

📝 BaekJoon 2213번 : 트리의 독립집합 (G1 48.748%) 🔎 트리의 독립집합 문제 📌 아이디어 💭 풀이 >#### 💻 코드

📝 BaekJoon 2533번 : 사회망 서비스(SNS) (G3 37.490%) 🔎 사회망 서비스(SNS) 문제 📌 아이디어 💭 풀이 💻 코드

📝 BaekJoon 1949번 : 우수 마을 (G2 53.907%) 🔎 우수 마을 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 2166번 : 다각형의 면적 (G5 25.592%) 🔎 다각형의 면적 문제 📌 아이디어 신발끈 공식을 이용하여 순서대로 정렬된 좌표들에 대하여 다각형의 면적을 구하는 문제이다. 💭 풀이 >- 다행히도 문제에서 인접한 좌표들을 순서대로 주

📝 BaekJoon 11758번 : CCW (G5 60.914%) 🔎 CCW 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 25308번 : 방사형 그래프 (G4 65.370%) 🔎 방사형 그래프 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 17386번 : 선분 교차 1 (G3 36.347%) 🔎 선분 교차 1 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 17219번 : 비밀번호 찾기 (S4 70.842%) 🔎 링크텍스트 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 20149번 : 선분 교차 3 (P4 21.497%) 🔎 선분 교차 3 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

선분들을 순회하며 교차하는지 판별후 Union-Find알고리즘을 이용해서 묶어주는 방식을 이용기본적으로 교차하는 선분을 판별하기 위해 ccw알고리즘을 이용해 판별하기 위해 이전에 풀었던 선분 교차2와 똑같은 알고리즘을 사용해준다.만약 해당 선분이 교차한다고 하면 Uni

📝 BaekJoon 7869번 : 두 원 (G2 30.111%) 🔎 두 원 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 1069번 : 집으로 (G3 32.795%) 🔎 집으로 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 11723번 : 집합 (S5 29.505%) 🔎 집합 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

위상정렬(Topological Sorting) 알고리즘을 이용한 기본문제이다.먼저 위상정렬(Topological Sorting)이란 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 '순서가 정해져있는 작업'을 차례로 수행해야

이전에 풀었던 문제와 비슷하게 위상정렬과 우선순위큐 힙 자료구조를 이용하여 사전순으로 정렬을 해준다.위상정렬을 위해 각 노드들의 진입차수를 계산해주고 진입차수가 0인 노드들을 q에 먼저 넣어준다. 이때 deque()자료구조를 사용하지 않고 heapq 자료구조를 사용하여

📝 BaekJoon 3665번 : 최종 순위 (G1 38.532%) 🔎 최종 순위 문제 📌 아이디어 위상정렬 알고리즘 문제로 진입차수만 확인하면 되는 문제이지만 작년의 순위에서 변동된 올해의 순위를 어떻게 관리할 것인지가 관건인 문제이다. 💭 풀이 >- 먼

📝 BaekJoon 3584번 : 가장 가까운 공통 조상 (G4 51.954%) 🔎 가장 가까운 공통 조상 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 17435번 : 합성함수와 쿼리 (G1 52.213%) 🔎 합성함수와 쿼리 문제 📌 아이디어 💭 풀이 느낀점 💻 코드

📝 BaekJoon 3176번 : 도로 네트워크 (P4 37.678%) 🔎 도로 네트워크 문제 📌 아이디어 Binary Lifting, LCA 알고리즘에서 가중치가 추가된 문제이다. 💭 풀이 느낀점 💻 코드

📝 BaekJoon 13511번 : 트리와 쿼리 2 (P3 28.565%) 🔎 트리와 쿼리 2 문제 📌 아이디어 💭 풀이 💻 코드