관찰과 질문, 그리고 데이터

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

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 풀이의 경우 특정 패턴이 반복된다는 사실을 파악한 풀이로 보인다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com DFS 문제. 한 번이라도 수영장을 가는 날에 한해서 - 1일권 끊는 경우 - 1개월권 끊는 경우 - 3개월권 끊는 경우 로 DFS 탐색하면 된다.

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는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다. 개인적..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net BFS 문제. 2d array 대신 dictionary를 이용했다.

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으 www.acmicpc.net BFS로 해결할 수 있는 문제.

https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 �� www.acmicpc.net 조건대로 구현하면 되는 문제.

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net DFS 문제. 두 달 정도 쉬었더니, 그새 구현방법을 다 까먹어서 엄청 버벅댔다. 잘 만든 코드는 아니니까, 나중에 더 세련된 방법으로 다시 풀어봐야겠다...

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 시뮬레이션 문제. pypy3으로는 통과하지만 Python3으로는 시간초과가 나는데, Python3 통과코드를 보고 어떻게 수정해봐도 내 코드는 더 이상 최적화가 안 된다. 왜지..?

https://programmers.co.kr/learn/courses/30/lessons/42894 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr 구현까지 시간이 오래 걸렸던 문제. 검은 블록을 채울 수 있는 모든 공간에 검은 블록을 채우고, 검은 블록과 설치된 블록을 합쳤을 때 직사각형 블록..