본문 바로가기
728x90

백준브실골124

백준 2176, 합리적인 이동경로 개요문제 링크골드 2, Graph, DP, Dijkstra두 점 사이를 가까워지며 이동하기접근오랜만에 푸는 백준. 퇴사 후 옛 생각에 한 문제 풀어봤다. 문제는 1번 노드에서 2번 노드로 갈 때 갈수록 가까워지는 것이다.엥 그냥 플로이드-워셜이랑 비슷한거 아닌가? 근데 왜 1에서 2로 가는 경로만 묻는걸까? 싶을 수 있다. 가까워지며 이동하는 것이 헷갈리는 게념인데, 아래와 같이 생각해보자.출발점 A에서 도착점 D로 이동할때 B와 C의 갈랫길이 있다고 생각하자.D까지 거리는 B가 5, C가 10이다.A에서 B,C까지 이동거리는 모두 1이다.그럼 최적의 선택지는 A->B->D로 6이다. A의 최소 이동거리는 6이다. 이때는 도착점까지 최소 거리가 6->5->0으로 최소거리가 줄어드는 조건을 만족한다.하지만.. 2025. 1. 13.
백준 13258, 복권 + 은행 개요 문제 링크 골드 5, 수학 가진돈 만큼의 확률로 J원을 줄 때 C기간 뒤 금액의 기댓값 접근 고등학생 때 확통을 열심히 배워야 하는 이유. 기댓값이란 어떤 확률적 시행에 대해 모든 경우의 수를 따져봤을 때 내가 얻을 수 있는 값이다. 쉽게 생각해 A (1% 확률로 100억) vs B (50% 확률로 1억) 중 더 이득인 것을 고를 때 기댓값을 사용한다. 1%의 확률로 100억이 더 손해일 것 같지만 A의 기댓값은 1억, B의 기댓값은 5000만원이라 A가 이득이다. 비슷하게 이 문제를 바라보자. 다음의 과정을 거치기만 하면 문제를 풀 수 있는데, 1회 시행 후 누군가는 J원을 얻는다. 어떤 $a_i$원을 가진 i번째 사람이 얻을 값은 $p_i$ × J = ($a_i$ / $a_i$의 총합) × J원.. 2024. 2. 7.
백준 22887, Reversort Engineering 개요 문제 링크 골드 5, 정렬, 구성적 i의 위치를 찾아 뒤집으며 정렬할 때 뒤집는 부분수열의 길이의 합이 C가 되는 수열 구하기 접근 재밌는 구성적 문제, 코포의 단골문제이다. 핵심은 만약 i를 찾아 뒤집었다면, a[i]=i를 항상 만족하고, j (n * (n + 1)) / 2 - 1) return false; vec ans(n); for (int i = 0; i = 1; i--) { rev(ans, i - 1.. 2023. 7. 16.
백준 22886, Moons and Umbrellas 개요 문제 링크 골드 5, DP, Greedy CJ 또는 JC가 나타날 때마다 X,Y의 비용을 지불할 때 비용의 최솟값 구하기 접근 DP의 정석같은 문제, 끝이 C, J일때를 기준으로 DP를 돌리면 된다. 만약 현재 끝이 J라면 min(이전J, 이전C+CJ), 끝이 C라면 min(이전C, 이전J+JC)를 해주면 된다. 끝이 ?라면 각각 C, J일때에 대해 각각 생각해주면 된다. 문제가 헷갈리는 부분은 두가지인데, 문제를 그리디하게 생각해버리면서 생긴다. 그런데 완탐을 해도 문제가 없고 그리디로 생각하면 한없이 복잡해진다. 먼저 x나 y가 양수라는 가정하에는 C만 계속 연속되거나 J만 계속 연속되는 것이 이득이라 생각할 수 있다. 그래서 그리디로 접근할 수 있는데 그럴 필요가 없다. CJ또는 JC를 번갈아.. 2023. 7. 16.
백준 25097, Controlled Inflation 개요 문제 링크 골드 2, DP, Greedy N명의 P개 작업을 최소한의 조작으로 마무리하기 접근 Codejam 2022 문제, codejam 문제는 시간을 많이줘서 생각이 맞으면 크게 틀리는 일이 없다. 문제는 생각이 어려움. 해법은 완탐을 하면 되는데, 완탐 조건이 약간 까다롭다. 먼저 완탐의 방식부터 생각하면 한 구간의 시작과 끝을 기준으로 잡고 모든 (s,e)에 대해 최솟값을 구하면 된다. 즉, for (s1:start) { for (e1:end) { for (s2:start) { for (e2:end) { value[s1][e1] = Minimum(previous[s2][e2]) } } } } 이런 느낌으로 가면 되고 Minimum은 앞에있는 모든 경우를 돌아보면서 최적값을 구해주는 것이다. .. 2023. 7. 16.
백준 25091, Chain Reactions 개요 문제 링크 골드 1, Greedy, DP, Tree 리프노드부터 아직 방문하지 않은 부모를 방문하며 구한 구간의 최댓값의 합의 최댓값 접근 요즘 코포가 완전히 박살이 나서 코포식 운영을 해보려고 한다. 쓰잘데기 없는 기하학 문제는 그만풀고 구글 코드잼같은 메이저 대회의 문제들을 풀면서 시간도 재보고 하려고 한다. 문제는 코포 연습하기 진짜 좋은 문제다. 스타일이 똑같다. 문제로 돌아오면, 참 괴상한 문제인데 핵심은 자신이 어떤 리프에 의해 init되느냐 하는 것이다. 2번 예시를 약간 변형해서 보자. 그림을 그려보면 이렇게 되는데, 각각 무엇을 통해 init이 되는 것이 최선인지 확인을 해보자. 우선 위 예시의 정답은 4,3,5,6 순으로 init하는 것이므로 210이 된다. 먼저 2를 보자. 2은.. 2023. 6. 22.
백준 11112, Eight puzzle 개요 문제 링크 골드 1, Graph, BFS 격자퍼즐을 풀 수 있는 최소 시행 횟수 구하기 접근 퍼즐형 BFS, 1525의 심화버전이다. 1525를 풀때는 나도 string을 썼는데, 이번에는 int를 써서 해결해봤다. 방법은 크게 복잡하지 않다. 빈공간의 주변의 2-4개 점을 다음점으로 하고, cnt+1해서 queue에 넣어 BFS를 돌리면 된다. 그런데 문제는 이게 100개의 데이터에 대해 전부 다 BFS를 돌려버리면 시간에서 터진다는 것이다. 그래서 해결법은? 정답부터 시작해서 전체 가능한 경우의 count를 전부 저장해버린다. 즉 완탐을 한 번 돌리고 들어가는 것이다. 이게 사실 문제의 핵심이고 나머지는 1525와 다를게 없어서 안된다면 1525부터 풀어보는 것이 좋다. string을 int로 .. 2023. 5. 12.
백준 3665, 최종 순위 개요 문제 링크 골드 1, Graph m개 쌍의 전후관계가 바뀔 때 다른 쌍의 전후관계를 유지하며 변경 가능한지 출력하기 접근 그래프의 개념이나 수학적 센스를 기르기 매우 좋은 문제. 우선 출력조건을 잘 보면 순위를 찾을 수 없는 경우 "?"를 출력하라고 나와있는데, 순위를 찾을 수 없는 경우는 존재하지 않는다. 왜인지가 쉽게 생각되지 않는 이유는 "데이터에 일관성이 없다" 라는 말이 전혀 이해가 안되기 때문인데, 세 번째 테케를 이해하는 것부터 해보자. [1 2 3 4]에서 1,2 앞뒤가 바뀌고, 2,3, 3,4 바뀌면 엥 [4 3 2 1]이면 되는거 아님? 하고 생각할 수 있다. 하지만 핵심은 저 세 가지 바뀌는 관계 외에, 원래 존재하던 나머지 세 개 (1,3 / 1,4 / 2,4)의 전후관계가 유.. 2023. 5. 12.
백준 15670, 도로 공사 개요 문제 링크 골드 2, 누적합 구간 L,R을 뒤집었을 때 증가하는 연속부분수열 개수 구하기 접근 먼저 N을 보자. 10만이니까 O(NlogN)이상은 사용할 수 없다. 아하 O(N)안에 끝내라는 말이구나. O(N)안에 끝내는 가장 좋은 방법은 연산에 필요한 데이터를 만들어두고, O(1)안에 연산을 마치는 것이다. 보통 이런 유형의 문제에 누적합을 사용한다. 누적합을 어떻게 사용하냐? 하면 우선 문제를 풀 방법부터 생각해보자. 배열을 직접 뒤집어서 매번 오르막을 세어주는 것이 가장 쉽게 생각할 수 있는 방법이고 가장 오래걸린다. 뒤집는데 O(N), 세어주는데 O(N)이 걸리니까 O(MN)으로 1e10번 연산이 필요하다. 시간초과. 그럼 (L,R)에 대한 오르막과 내리막을 전부 저장한 뒤, (1,L-1)의.. 2023. 5. 12.
백준 21940, 가운데에서 만나기 개요 문제 링크 골드 4, Graph 주어진 점으로부터의 거리의 최댓값이 최소가 되는 지점 접근 전형적인 플로이드 워셜 문제, 다익스트라를 써도 되겠지만 한점->여러 점의 경로를 구하는 것이 아닌 여러점-> 여러점의 경로를 구하는 문제이고, N이 200으로 작으니까 플로이드 워셜로 완전탐색을 해주면 된다. 플로이드 워셜은 중간점을 잡는 방법이라고 생각하면 쉽다. i부터 j로 이동할 때 어떤 중간점을 경유해서 가는 것이 이득이면 업데이트 해준다. 마지막으로 단방향 경로가 제공되므로 기준점 s에 대해 (s,i)+(i,s)의 거리를 기준으로 업데이트 하면 된다. Pseudo code adj = {1e8} // 최댓값으로 초기화 // 두 값의 합이 int 범위 내에 있어야하니 1e9이내로 for (m) adj[.. 2023. 5. 12.
728x90

티스토리툴바