OSNIM

문제 출처: 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/14890 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 나의 접근법 저는 row를 길을 세는 함수와 col의 길을 세는 함수를 다르게 작성하여 풀었습니다. 그리고 다음과 같이 예외를 추가하며 길의 수를 세었습니다. 1. 높이 차이가 2 이상인 경우 제외 2. 높이가 증가하다가 감소하는 경우, 감소하다 증가하는 경우 3. 높이가 낮은 칸의 개수가 L 보다 큰 경우 저는 이렇게 3가지를 구분하여 문제를 풀려고 했고 다음과 같이 코드를 작성하..

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

문제 출처: https://www.acmicpc.net/problem/18405 나의 접근법 위 문제는 이것이 코딩테스트다 with 파이썬 에 수록된 문제입니다. 먼저 답을 읽지 않고 제 스스로 풀어보려고 노력했습니다. 바이러스의 위치를 x,y좌표로 기억하여 번호 마다 리스트에 저장하였습니다. 그리고 시간 S 만큼 반복하여 바이러스를 퍼뜨렸습니다. 일반 케이스 말고 특이 케이스도 생각해봤습니다. 만약 1번 바이러스가 2번 나오면 어떡하지? 만약 1~K번의 바이러스가 연속으로 나오지 않고 랜덤으로 나오면 어떡하지? 저는 위와 같은 경우의 수도 고려하며 풀려고 노력했습니다. 첫번째 풀이법 import sys from collections import deque def BFS(virus, virusPositi..

문제 출처: https://www.acmicpc.net/problem/14502 깊은 복사와 얕은 복사 파이썬에서는 리스트를 크게 얕은 복사와 깊은 복사 2가지로 복사하고 있습니다. 얕은 복사 객체의 주소값을 복사하는 경우입니다. 대입 연산자 (‘=’) 를 사용해서 리스트를 다른 리스트에 대입하는 방식입니다. 변형(mutable) 객체는 복사한 객체의 내용을 변경하면 원본 리스트의 내용도 변합니다 불변형(immutable) 객체는 복사한 객체의 내용을 변경해도 원본에는 영향이 없습니다. 깊은 복사 객체의 데이터만을 복사하는 경우입니다. copy 모듈의 copy() ,deepcopy() 함수를 사용합니다. 1차원 리스트는 copy()를 사용하고 2차원 이상의 배열은 deepcopy() 함수를 사용합니다. ..

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

문제 출처: https://www.acmicpc.net/problem/1931 풀이 제 코드는 다음과 같습니다. import sys N = int(sys.stdin.readline().rstrip()) a = [] for i in range(N): start, end = map(int, sys.stdin.readline().split()) diff = end - start a.append([start, end, diff]) a.sort(key=lambda x:(x[1], x[0], x[2])) end = a[0][1] count = 1 for i in range(1, N): if end

문제 출처: https://www.acmicpc.net/problem/10610 풀이 제 코드는 다음과 같습니다. import sys num = sys.stdin.readline().rstrip() def sol(): if '0' not in num: #입력에 0 이 없으면 30 배수 안되므로 -1 print(-1) return num_list = list(num) # num_list.sort(reverse=True) # SUM = 0 for i in range(len(num_list)): # 각 자리수의 합이 3의 배수이면 num은 3의 배수 SUM += int(num[i]) if SUM % 3 == 0: print("".join(num_list)) return else: print(-1) return..

문제 출처: https://www.acmicpc.net/problem/11652 풀이 제 코드는 다음과 같습니다. import sys n = int(sys.stdin.readline()) a =[] for i in range(n): a.append(int(sys.stdin.readline().rstrip())) a.sort() count = 1 result = [[a[0], count]] for i in range(1, n): if result[-1][0] == a[i]: count += 1 result[-1][1] = count else: count = 1 result.append([a[i], count]) result.sort(key = lambda x:(-x[1], x[0])) sys.stdout...

문제 출처: https://www.acmicpc.net/problem/10989 오답 분석 저는 먼저 파이썬에 내장된 정렬 함수인 sort를 이용해서 풀려고 했습니다. 하지만 저번 2751 수 정렬하기 2 문제와 다르게 메모리 초과가 발생했습니다. 그 이유는 입력되는 정수의 개수 N과 입력되는 정수의 최대 값 n의 차이를 제대로 파악하지 못했으며, 메모리 범위를 고려하지 않아 문제가 발생하였습니다. 아래는 제가 처음 제출한 코드입니다. 이 문제의 핵심은 메모리의 최대값은 8MB인 것과 입력되는 정수의 개수 N의 범위는 (1 ≤ N ≤10,000,000)라는 것입니다. 파이썬에서 정수 값은 기본적으로 4byte 메모리를 할당합니다. 만약 모든 데이터의 입력을 리스트에 저장한다면 4byte * 10,000,..

문제 출처: https://www.acmicpc.net/problem/2751 오답 분석 저는 먼저 파이썬에 내장된 정렬 함수인 sort와 sorted를 이용해서 풀려고 했습니다. 하지만 모두 시간 초과가 발생했습니다. 이를 해결하기 위해 바로 구글링을 하여 답을 찾지 않고 다음과 같은 생각과 과정을 통해 문제를 해결 하려고 했습니다. 파이썬의 정렬 내장함수인 sort와 sorted가 O(NlogN) 시간 복잡도를 가지고 정렬을 한다는데 이 정렬 알고리즘보다 더 빠른 퀵정렬 알고리즘을 사용해야 하나? -> 정답은 아니었습니다. 퀵정렬 또한 O(NlogN) 이라는 시간복잡도를 가지고 있어 똑같이 시간초과라는 문제가 발생했습니다. 1번도 아니라면 계수 정렬이라는 특수한 정렬알고리즘을 사용해야하나? -> 결과..

문제 출처: https://www.acmicpc.net/problem/11055 오답 정리 이 문제의 점화식과 규칙은 11053 문제의 유형과 너무 비슷했기 때문에 빠르게 찾을 수 있었다. 하지만 사소한 실수로 인해 시간을 너무 많이 뺏기고 문제를 풀지 못하는 불상사가 발생했습니다. 어디가 문제였는지 틀린 코드와 맞은 코드를 한눈에 비교하면서 분석해보도록 하겠습니다. 위 그림에서 차이점을 찾을 수 있나요? 저는 처음에 큰 문제가 없을 줄 알고 왼쪽처럼 코딩을 했습니다. 하지만 이렇게 코딩을 한 경우 예제는 커버가 되지만 모든 tast case를 만족 시킬수 없었습니다. 그럼 어디서 문제가 발생하였을까요? 다름 아니라 dp의 초기값에서 문제가 발생했습니다. 저는 DP문제를 풀 때 무의식적으로 dp = [0..