OSNIM

구현, Level 2 문제 : https://programmers.co.kr/learn/courses/30/lessons/77485 문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다. 다음은 6 x 6 크기 행렬의 예시입니다. 이 행렬에 (2, 2, 5, 4) 회전을 적용하..

문제 출처: https://www.acmicpc.net/problem/19238 나의 접근법 그래프에 남은 연료를 넣기 위해 벽을 -1로 변경 손님들의 위치 정보와 도착정보를 따로 저장 BFS() 1. 먼저 현재 위치에 손님이 있는지 확인 2. BFS로 거리 1차이 나는 거리 확인 -> q에 넣기 3. 같은 거리에 또 다른 손님이 있는지, 첫 손님은 찾았는지, 거리가 같은지 -> custList에 추가 4. 현재 g에 넣는 연료 (남은 연료)가 첫 손님을 찾았을 때 남은 연료보다 작은지 -> 작다면 거리가 같은 손님은 다 찾은 것 -> 정렬 후 행이 낮고 열이 낮은 손님부터 목적지 찾기 5. 가까운 손님을 첫손님을 찾은 경우 -> custList에 추가 5-1 만약 그 첫 손님이 마지막 칸에 있는 경우 ..

문제 출처: https://www.acmicpc.net/problem/17779 나의 접근법 처음에는 마름모를 기준으로 위, 오른쪽, 아래, 왼쪽을 맵 경계까지 1부터 4를 차례로 넣고 BFS로 graph의 꼭지점을 시작으로 탐색하려고 했으나 경계의 네 변의 길이가 모두 같은 경우는 쉽지만 마름모의 두 쌍의 길이가 다를 때는 범위 파악이 힘들었고 이렇게 해도 경계는 그려야 하기 때문에 BFS를 하지 않고 바로 반복문을 돌렸습니다. 구간을 5개로 나누는데 경계선 내부인 5번 선거구는 값을 넣지 않습니다. 구간을 나누는 방법은 x, y를 한 쌍을 기준으로 잡아 4부분으로 나누어 for문을 돌려 경계를 나누었습니다. 그리고 예를 들어 4번 지역은 행이 감소하면서 열이 증가하는 순서로 탐색하면 자칫 탐색을 못하..

문제 출처: https://www.acmicpc.net/problem/12100 나의 접근법 처음에는 알고리즘이 바로 생각안나서 알고리즘만 보고 힌트를 얻었습니다. 백트래킹과 브루트포스를 보고 DFS로 depth가 5일 때 종료해주면 된다고 생각해서 상,하,좌,우로 이동하는 것만 잘 만들어 주면 쉽게 해결할 수 있다고 생각했습니다. 첫번째 코드 def move(arr, i): # 위로 이동 if i == 0: for y in range(N): for x in range(1, N - 1): if arr[x][y] == arr[x + 1][y]: arr[x][y] = arr[x][y] + arr[x + 1][y] arr[x + 1][y] = 0 elif arr[x][y] == 0: arr[x][y] = ar..

문제 출처: https://www.acmicpc.net/problem/5373 나의 접근법 첫번째 저는 처음에 윗면을 기준으로 규칙성을 찾으려고 했습니다. 하지만 시간이 너무 오래걸리고 다른 면에서의 규칙성과 윗면에서의 규칙성을 못찾아서 위 방법은 포기했습니다. 그리고 결국 제가 정한 시간이 초과되어 구글링을 통해 다른 사람들은 어떻게 규칙을 찾았는지 검색해보았습니다. 하지만 대부분의 답에서 일일이 각 면에 해당하는 코드를 작성한 것을 보고 저도 규칙성 보다는 일일이 구현하기로 결정했습니다. 이 방법이 귀찮기는 하지만 때로는 가장 확실한 방법인 것 같습니다. 두번째 세번째 풀이 두번째 풀이에서 전개로를 활용했습니다. 각 회전하는 면을 기준으로 상하좌우 3칸만 회전하는 변화만 파악하여 빠르게 파악하여 if..

문제 출처: https://www.acmicpc.net/problem/15685 나의 접근법 처음 문제를 접했을 때 너무 특이한 문제라서 당황했습니다. 90도 시계방향 회전을 어떻게 다뤄야 할지 감이 안잡혔습니다. 그래서 최대한 규칙을 찾으려고 노력했습니다. 일단 제일 눈에 띄는 점의 좌표 변화를 파악하여 규칙성을 찾으려고 노력했습니다. 하지만 세대가 커질수록 점의 좌표는 이전 세대의 좌표들과 너무 크게 벌어지고 규칙성도 없다는 느낌이 들어서 빠르게 포기했습니다. 다음은 방향의 변화들로 규칙성을 찾으려고 노력했습니다. 방향을 기준으로 하니 답이 보였습니다. 4 4 1 3 의 경우 윗 방향으로 3세대까지 드래곤이 커브를 하는데 다음 커브의 순서가 이전 커브 역순에서 +1 한 것이었습니다. 자세한 그림은 다..

문제 출처: https://www.acmicpc.net/problem/15683 나의 접근법 먼저 그리디 인지 DFS인지 고민을 했습니다. cctv의 번호가 높을 수록 많은 범위를 감시하는 것 같아서 그리디로 먼저 풀었습니다. 그래서 번호가 높은 cctv를 역으로 정렬하여 탐색했습니다. 하지만 그리디로 풀 경우 현재 값이 다음 값에 영향을 받을 수 있다는 것을 office를 출력해서 알게 되었습니다. DFS로 작성하기 위해서는 원래의 office에 #을 추가한 office을 따로 구분해야 했습니다. 또한 #을 추가한 office을 임시로 저장하고 DFS 탐색이 끝난 뒤 return 했을 때, 또 새로운 office를 DFS 단계에 넘겨줘야 하는데 여기서 해답을 찾지 못했습니다. 마지막으로 cctv 번호 ..

문제 출처: https://www.acmicpc.net/problem/14891 나의 접근법 먼저 문제를 보고 생각한 저의 제 플로우 차트입니다. 플로우 차트를 제대로 그린 것이 아니라 프로그램이 고려해야 되는 순서만을 빠르게 작성하고 디테일한 설정은 코드에서 구현하였습니다. 정답 코드 import sys from collections import deque def checkRight(idx, clockWise): if idx > 3 or gears[idx-1][2] == gears[idx][6]: return if gears[idx-1][2] != gears[idx][6]: checkRight(idx+1, -clockWise) gears[idx].rotate(clockWise) def checkLeft..

문제 출처: https://www.acmicpc.net/problem/14503 나의 접근법 저는 이 문제를 처음에는 BFS로 빠르게 풀려고 했습니다. 그런데 BFS는 경우 모든 장소를 탐색하지만 이 문제는 로봇청소기의 규칙대로 움직이기 때문에 연결된 모든 장소를 탐색하는 기존의 BFS 와는 조금 다른 방법으로 풀어야합니다. 이 문제를 풀면서 추가로 고려해야 할 점들이 조금 있었습니다. 사실 BFS라기 보다는 구현, 시뮬레이션, 완전탐색 문제에 가깝습니다. 1. 평범한 BFS 문제는 처음 방문하면 방문 표시를 해서 단 한번만 방문을 하게 하지만 이 문제는 뒤로가기를 하기 위해 방문했던 곳을 다시 방문할 수 있게 해야합니다. 2. 회전의 순서가 방향 순서와 다릅니다. 방향 순서 (북쪽기준, 시계방향) : ..

문제 출처: https://www.acmicpc.net/problem/2873 처음 생각한 접근법 R행 C열 크기의 직사각형을 모눈종이에 그려보고 최대한 많은 경로를 이동하는 방법을 생각했습니다. 여러가지 경우의 수를 생각하다 보니 몇 가지 패턴이 보였습니다. 먼저 R 또는 C 가 홀수일 경우 모든 경로를 탐색 할 수 있었습니다. 즉 기쁨의 숫자와 상관 없이 R, L, U, D 를 조합하면 되었습니다. R이 홀수인 경우는 다음과 같은 패턴으로 이동합니다. C이 홀수인 경우 다음과 같은 패턴으로 이동합니다. 마지막으로 R과 C가 모두 짝수인 경우는 1칸만 방문 못하고 모든 곳을 방문한다고 생각했습니다. 하지만 여기서부터 잘못 생각하여 시간이 많이 뺏겼고 답을 도출해내지 못했습니다. 다음은 제가 생각한 경우..