백준

[pypy3] 백준 12015 풀이 ( 가장 긴 증가하는 부분 수열 2 , LIS , 이분 탐색 )

이번에는 진짜 너무 어려웠다. 정답비율이 40%문제인데 다들 대단한거 같다. 물론 문제 자체가 기본적인 LIS유형중 한개로 쉽게 풀리지만 알지 못하는 상태에서 생각해 내기 굉장히 어려운거 같다. 따라서 나도 LIS를 공부하고 기본 코드로 풀이를 할 수 있었다. 우선 문제를 보자 문제는 간단하다. 수열이 주어지고 여기서 "최장 증가 부분 수열"을 구하면 된다. 내가 풀이를 쓰는 것보다 더 좋은 풀이가 있어서 고수님의 글을 참고하면 좋을것 같다. https://chanhuiseok.github.io/posts/algo-49/ 알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 결론적으로 LIS의 풀이 방법은 2가지가 있다. 1. DP를..

[python3] 백준 1389 풀이 ( 케빈 베이컨의 6단계 법칙, 플로이드 워샬 )

이번 문제는 케빈 베이컨의 6단계 법칙이다. 케빈 베이컨이 할리우드의 핵 인싸라는 것을 인지하고 문제에 들어가자. 문제를 보자 문제가 상당히 길다. 읽어보면 그냥 네트워크 안에서 여러 사람들과 연결되어 있을때 모든 타인과 몇번만에 연결되어 있는지를 알아내어 최솟값을 가지는 즉, 허브 역할을 하는 사람을 구하면 된다. 문제를 잘 읽어보면 결국 N정점에서 N정점으로의 갈 때 얼마나 걸리는지를 구해야 한다. 그래야 한 노드에서 모든 노드에 방문할 때 케빈 베이컨의 수를 구할 수 있다. 즉, 모든 쌍 최단 거리 알고리즘을 사용하면 구할 수 있다. 모든 쌍 최단 거리 알고리즘의 대표적인 놈이 "플로이드 워샬"이다. 그러나! 플로이드 워샬은 O(N^3)이 걸리기 때문에 N값이 너무 크면 문제가 발생할 수 있다. 다..

[python3] 백준 14360 풀이 ( 구슬 탈출 2, BFS, 방문체크 없음 )

이번 문제는 저번 주 스터디에서 풀지 못한 문제였는데, 생각할 시간이 상당히 많았기 때문에 겨우 풀었다. 우선 문제를 살펴보자 문제를 요약하면 상하좌우로 움직일 수 있는 판을 가지고 있을 때, 빨간공만을 출구로 뽑아내는 경우 얼마나 시간이 걸리는지 알아내는 문제이다. 이때 한 방향으로 움직이는 경우 두 공이 못 움직일 때까지 움직인다. 우선 우리는 최소로 움직여서 공을 뽑아낼 것이다. 즉, 최단 거리나 최단 경우의 수를 구할 때는 역시 BFS를 사용해야한다. 두번째로 우리는 2공(빨강,파랑)을 상하좌우로 움직일 것이다. 움직일 때는 한번에 움직이지 못하고 한 칸씩 이동하면서 움직여야한다. 왜냐하면 그래야 겹치는 경우를 피할 수 있다. 그런데 겹치는 경우를 위해 한 칸씩 움직인다고 한다면 방향에 따라 두 ..

[python3] 백준 16236 풀이 ( 아기상어, 그래프, BFS, sort, pq? )

이번 문제도 역시나 좀 헤맸다. 이번 문제는 BFS로 쉽게 풀릴 줄 알고 살짝 깝쳐 봤으나 역시나 생각치 못한 케이스가 존재해서 결국 다시 코딩한 문제이다. 문제를 쓰악 읽어보자. 우선 문제는 아기상어의 성장에 관한 이야기다. 스토리처럼 느껴져서 문제 읽는 동안 재밌었다. 여튼 문제에서 나오는건 아기 상어가 성장하기 위해서 물고기를 먹어야한다. 그런데 먹이를 먹는데 여러 조건이 존재한다. 조건 1. 먹을 수 있어야함. (자기보다 크기가 작아야함.) 2. 거리가 가까워야 함. 3. 위 물고기 선호 4. 왼쪽 물고기 선호 1번 조건과 2번 조건은 BFS로 최단 경로를 찾으며 먹을 수 있는 물고기를 찾으면 된다. 3번 조건과 4번 조건은 같은 거리에 존재하는 물고기들의 좌표를 비교하여 조건에 맞는 물고기부터 ..

[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 )

이번 문제 풀이 사실 봐버렸다. 거의 풀었다고 생각했는데 내가 생각한 방법으로는 도저히 풀리지가 않아서 그냥 풀이를 봤다. 바로 문제를 보자 문제를 읽어보면 낮은 방향으로만 진행한다고 한다. -> 사이클이 존재하지 않는 그래프이다. 가장 빠른게 도착하는게 아닌 도착하는 경우의 수를 구한다. -> BFS가 아닌 DFS를 여러 번 써야한다. 문제를 통해 2가지를 확인할 수 있다. 그런데 DFS만을 쓰는 경우에는 너무 많은 케이스가 존재한다. 실제로 DFS만으로 제출한다면 시간초과가 뜬다. 따라서 DFS만이 아닌 DP를 함께 활용해 주어야한다. 그럼 DP를 어떻게 활용해야 할지 고민을 해본다. DFS만 써서 시간초과가 나는 것은 빙빙 돌아 목적지에 도착하는 경우까지 기다려야 하기 때문이다. 그렇다면 빙빙 돌아..

[python3] 백준 2293 풀이 ( 동전 1, 다이나믹 프로그래밍 )

아주 상당히 헤매면서 풀었다. 실버 1이라 어려울 것이라 생각했는데 정답비율이 높았다. 난이도는 높지만 알고리즘만 이해하면 코드 구현을 쉬웠기 때문인거 같다. 우선 나는 노가다를 해가며 풀었다. k가 1일때부터 1,2,5가 가능한 조합을 전부 때려 넣어가며 숫자를 보았는데 규칙 일랑 하나도 보이지 않았다. 그래서 덩어리를 생각하며 풀어보기로 했다. 그래서 생각한 것이 이차원 배열로 나타내는 것이었다. 문제에서 주어진 예제가 아닌 다른 예제로 생각해 보겠다. 2 10 2 3 K 0 1 2 3 4 5 6 7 8 9 10 2 1 0 1 0 1 0 1 0 1 0 1 3 coin이 2인경우 k값에 따라 만들 수 있는 경우는 2로 나누어 떨어지는 경우이다. 이때는 2만 들어 가기 때문에 한가지 경우만 존재한다. 따..

[python3] 백준 9465 풀이 ( 스티커, 다이나믹 프로그래밍, 이차원 배열 )

문제를 쓱 읽어 보면 DP의 냄새가 솔솔솔~ 난다. 딱 봐도 그리디로 풀 수 없고 완전 탐색을 진행해야만 풀 수 있는 상황이다. 그렇다면 역시 DP로 풀어야한다. DP로 풀기 위해서는 다음 단계에 영향을 미쳐야 한다. 즉, 선택한 스티커의 상하좌우에 위치한 다른 스티커를 선택할 수 없다. 우선 dp를 이차원배열이라 한다. 또한 dp에는 각 행별로 열까지의 최댓값을 가진다. 따라서 천천히 생각해보자 만약 0열의 i를 뽑을 것이라면 0열의 dp[0][i-1]을 뽑을 수 없다. 따라서 0열이 아닌 1열의 i-1까지인 dp[1][i-1]을 더할 수 있다. 그러면 식은 dp[0][i] = dp[1][i-1] 이다. 또한 한가지를 더 생각해 보아야 한다. i-1의 열의 스티커의 값이 형편 없다면 이걸 무시하고 i-..

[c++] 백준 1629 풀이 ( 곱셈, 분할 정복을 이용한 거듭제곱, long long )

이 문제는 예전에 파이썬으로 풀었던 적이 있다. 그러나 c++풀이는 또 다른 포인트가 있기때문에 다시 풀어보기로 했다. 일단 문제를 쓱 보자 문제를 보면 A를 B승하고 C로 나눈 나머지를 구하라는 뜻이다. A,B,C 모두 21억을 넘는다. 이는 int의 최댓값 범위이다. 그렇다면 A^2일때 int를 넘어가서 오버플로우가 난다. 따라서 int보다는 long long을 사용하여 함수를 작성하는게 좋을 것 같다. long long의 범위는 9,223,372,036,854,775,807 이다. 그런데 A는 21억이기 때문에 long long범위를 초과할 가능성도 있다고 생각했다. 21억에 붙은 0은 9개, long long 범위의 0개수는 18개이다. 즉, 연산중에 long long범위를 초과할 가능성이 존재하..