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

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 위상정렬 + bfs를 적용한 느낌의 문제.

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 접근 방법이 백준 키로거 문제와 흡사하다. [Python] 백준 5397. 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에.. insp..

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net bfs, dfs 둘 다 시간초과 나는 걸 보고 DP로 풀어야겠다고 직감함. 풀이 접근방법은 예전에 풀었던 '등굣길'과 거의 동일하다. [Pyt..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 내 풀이방법은 Python 3에서 시간초과를, PyPy3에서는 통과했다. 테트로미노의 저 다섯 가지 shape를 어떤 식으로 정의했..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net bfs를 사용해서 그래프에 연결된 모든 노드를 확인하는 문제.

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 최대 10개인 도시를 두 개의 그룹으로 분리한다. 2. 각 그룹별로 bfs를 돌며, 그룹의 모든 원소가 연결되어 있는지 확인한다. 3. 두 개의 그룹이 전부 연결되어 있다면, 두 그룹 인구수의 차를 구한다.

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 각 방향으로 기울일 때 고려할 점이 많아서 어려운 문제. 1. 위 / 아래로 기울인다 = 2d list를 traspose해서 해결한다 2. 값이 왼쪽으로 합쳐질 때 / 오른쪽으로 합쳐질 때의 연산방법이 다르다.

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net Brute Force + Deque 활용한 배열 회전으로 풀 수 있는 문제. 1. 제한사항에서 K가 최대 6이므로, 경우의 수..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 삼성SW역량평가 기출이고, DFS를 활용한 brute force 문제. 구슬이 같은 위치에 놓일 때 선후관계를 구분해서 처리하는..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net 이분탐색 문제. 이분탐색 값의 기준은 '공유기 사이의 거리'이고, 공유기 사이의 거리를 토대로 주어진 문제 조건에 맞게 공유기 개수를 증가시키면서 이분탐색으로 최적의 '공유기 사이의 거리'를 구하는 문제.