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

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://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우 문제. 매번 윈도우 위치를 변경할 때마다 min함수를 사용할 경우, 시간복잡도가 O(n**2)가 된다. deque를 활용해 삽입/삭제를 빠르게 수행하되, deque에 값을 저장하는 방식을 약간 변경하면 효율적으로 연산을 수행할 수 있다. 아래 풀이에서 더 상세한 해설을 볼 수 있다. 백준 11003번 문제 (최솟값 찾기) with Java · 쾌락코딩 백준 11003번 문제 (최솟값 찾기) with Java 03 D..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 원판 회전을 위해 deque를 사용하고, 인접한 숫자를 체크하기 위해 bfs를 활용한다. 이차원 배열로 구현하되 1. 이차원 배열..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 깐깐한 시뮬레이션 문제. 내 코드는 Python3으로는 시간초과가 났고, pypy3으로는 통과했다. 더 효율적으로 코드를 작성할 방법이..

bfs로 값이 1인 좌표를 탐색하는 문제. 한 번 1인 지점을 방문하면, 그 지점의 값을 0으로 바꾸는 식으로 중복탐색을 막을 수 있다.

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백준 브루트 포스 문제유형. combinations로 모든 경우의 수를 탐색하면 된다.

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net bfs + heapq로 풀어낼 수 있는 문제. 현재 위치에서 1. bfs로 '잡아먹을 수 있는 물고기 좌표'를 탐색한다. 2. 탐색..