공부하고 기록하는, 경제학과 출신 개발자의 노트

백준 77

[Python] 백준 2156. 포도주 시식

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net DP문제. 점화식은 잘 구했는데, 점화식에 맞춰서 arr를 생성하는 과정에 또 시간소모가 심했다. table[i] = i번째 위치에서 마실 수 있는 최댓값이라고 정의하면 i-1번째와 i-2번째 둘 다 마신 경우 = i번째 위치를 마실 수 없으므로 table[i-1] i-1번째를 마시지 않은 경우 = table[i-2] + arr[i] i-2번째를 마시지 않은 경우 = table[i-3] + arr[i-1] + a..

[Python] 백준 11066. 파일 합치기

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 �� www.acmicpc.net 문제 자체도 난해한데, Python3의 느린 연산속도 때문에 시간초과까지 겹쳐서 푸는 데 정말 오래 걸렸다. 이 풀이는 PyPy3으로만 통과하며, Python3으로는 시간초과가 난다. C++이나 Java의 로직으로는 통과하지만... 전제: '인접한 페이지'끼리만 합칠 수 있다. 문제의 예시라면, C2와 C4를 바로 합치는 건 불가능하고, C2 + (C3 + C4) 또는 (C2 + C3..

[Python] 백준 3109. 빵집

https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴� www.acmicpc.net 그리디 알고리즘 + BFS 문제. 최대한 많은 가스관을 배치하기 위해서는, 가급적이면 가스관이 우상향이 되어야 한다. 따라서 우상향 / 직진 / 우하향 순서대로 파이프를 설치할 수 있는지 DFS로 확인해야 한다.

[Python] 백준 2458. 키 순서

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 이전에 프로그래머스에서 풀었던 것과 유사한 문제. 자신의 키가 얼마인지 알기 위해서는, "자신보다 키 큰 학생의 수 + 자신보다 키 작은 학생의 수 == 전체 학생수 -1" 여야 한다. 또한 학생 i보다 키 작은 학생 -> 학생 i보다 키 큰 학생보다는 무조건 작다. 학생 i보다 키 큰 학생 -> 학생 i보다 키 작은 학생보다는 무조건 크다. 두 가지 조건을 토대로 구현하는 문제.

[Python] 백준 9461. 파도반 수열

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net DP문제. 그림 덕분에 쉽게 점화식이 유추 가능하다. n번째 삼각형 = n-1번째 삼각형 + n-5번째 삼각형이므로 table[n] = table[n-1] + table[n-5] 형태의 함수를 구현하면 된다.

[Python] 백준 3197. 백조의 호수

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net Python3으로는 통과한 사람이 없는 문제. PyPy를 써야 통과 가능하다. 매 초마다 빙하가 녹는 지점을 찾고, 백조끼리 연결이 가능한지 확인하다 보면 R, C

[Python] 백준 16918. 봄버맨

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net bfs 기반 시뮬레이션. Python으로 풀었을 때, 시간이 4000ms를 넘는 경우가 있고 200ms에서 끝나는 경우가 있다. 내 풀이방법은 4000ms를 초과하는 풀이이므로 시간 면에서는 효율적이지 못함. 200ms 풀이의 경우 특정 패턴이 반복된다는 사실을 파악한 풀이로 보인다.

[Python] 백준 12015. 가장 긴 증가하는 부분수열 2(LIS)

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열의 크기가 백만 단위라서 N^2 의 DP로는 문제로 풀 수 없다. Binary Search를 활용해서 O(NlogN)으로 풀어낼 수 있다. 자세한 풀이는 최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기 LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다. 개인적..