문제 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 완전한 구현 문제다. 순열을 통해 모든 경우의 수를 구한 후, 연산으로 이루어진 순열을 큐에 담아 rotate 함수에 전달한다. 회전을 구현하는 과정은 조금 지저분하게 구현했다. 이때 좌측 상단의 좌표를 (ux, uy)로, 우측 하단의 좌표를 (lx, ly)로 두고 좌에서 우로, 상에서 하로 값을 덮어 씌웠다. 이를 위해 모서리의 값을 t1, t2, t3 변수에 담아두었..
문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 백준 1753번 문제인 최단경로 문제와 유사한 문제다. 마찬가지로 다익스트라 알고리즘을 적용하여 해결할 수 있다. 다만, 이 문제 같은 경우 두 정점(v1, v2)을 반드시 거쳐야 한다는 제약조건을 고려해야 한다. 1번 노드부터 출발하여 n번 노드까지 이동하는 경로는 다음과 같이 두 가지로 나뉜다. 1) v1번 노드를 먼저 방문한 후, v2번 노드를 방문하..
문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 로봇 청소기와 점프를 합쳐 놓은 듯한 문제였다. 문제 유형은 다이나믹 프로그래밍이면서도, 구현 능력도 요구하는 문제였다. 문제에서 고려할 중요한 조건은 다음과 같다. 1) 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 2) 파이프가 놓여진 방향에 따라 회전 방향이 결정된다. 3) 회전 방향에 따라 특정 칸이 무조건 비어있어야 한다. dir..
문제 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 이항 계수라는 개념을 모르면 풀기가 어려운 문제였다. 비슷한 문제인 이항 계수 1 같은 경우 N이 최대 10으로 작기 때문에 재귀적으로 코드를 작성하거나 itertools모듈을 이용해도 풀이가 가능했다. 하지만, 이 문제는 N이 최대 1000으로 O(N^2)시간의 알고리즘을 구성해야 한다. 따라서 바텀업(Bottom-up) 방식으로 이항 계수를 구현했다. MOD계산을 해주는 것도 잊으면 안된다. 코드 import sys n, k = map(int, sys.stdin.re..
문제 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 일반적인 그래프 탐색 문제와 달리 z축까지 고려해야 하는 문제였다.최소 일수, 즉 최단 거리를 구해야 하기 때문에 BFS를 이용해야 한다. 모든 익은 토마토의 좌표를 큐에 담아주는 것이 중요하다. 어느 지점에서 탐색을 시작하는지 여부에 따라 최단 거리가 상이하게 구해지기 때문이다. 코드 import sys, collections def bfs(): result = 0 q = c..
