OSNIM

문제 : https://www.acmicpc.net/problem/2133 풀이 N 일때 dp[N]의 위 그림 오른쪽처럼 3개로 나누어 집니다. 1. dp[N] = dp[N-2] x 3 2. dp[N] += i는 2부터 N-4 까지 dp 값에 2를 곱하고 모두 더한 부분 3. N이 2씩 증가할 때 마다 나타나는 새로운 타일 배열 : +2 제출 코드 def solve(): n = int(input()) dp = [0] * (30+1) dp[1] = 0 dp[2] = 3 for i in range(4, n+1): if i%2 == 1: continue dp[i] = dp[i-2]*3 for j in range(0, i-2, 2): dp[i] += dp[j]*2 dp[i] += 2 print(dp[n]) re..

22.05.05 추가) PC에서 검색하고 들어오면 화면이 모바일 버전으로 나옵니다. 다른 페이지는 문제가 없는데 어항정리만 뒤에 url에 "/m/" 이 추가되는 것을 확인했습니다. https://osnim.tistory.com/entry/%EB%B0%B1%EC%A4%80-23291-%EC%96%B4%ED%95%AD%EC%A0%95%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC 위 사이트로 이동해서 글을 보시면 모바일 화면이 아닌 PC 화면으로 글을 보실수 있을 것입니다 빨리 문제를 해결하겠습니다. 문제 : https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이..

구현, 시뮬레이션 문제 : https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 문제 요약 및 정리 ''' 4x4, 물고기 M 마리, 이동방향 1부터 8까지 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 상어와 물고기 같은 칸 가능, 둘 이상의 물고기 같은 칸 가능 마법 한번 다음과 같은 작업 순서 1. 복제 마법 시전 (5번에서 물고기 복제) 2. 모든 물고기 한 칸 이동 상어가 있는 칸 X, 물고기 냄새가 있는 칸 X..

문제 : https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 요약 ''' 1. NxM, 오른쪽 동쪽, 위쪽 북쪽, 주사위 각 면 1~6, 전개도 2. 전개도 2 4 1 3 5 6 3. 지도 윗 면 1, 동쪽을 바라보는 방향이 3 인 상태, 지도와 맞닿은 부분 6 4. 가장 처음 주사위 이동 방향 : 동쪽 주사위 이동 방식 1. 이동방향으로 한칸 구름, 칸이 없다면 반대방향으로 한 칸 구름 2. 도착한 칸 점수 획득 3. 주사..

문제 : https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 조건을 간단하게 정리하면 다음과 같습니다. ''' 1. 각 칸에 바구니, 바구니에 저장할 물의 양 제한 X 2. 1번행과 N 번 열이 연결되어 있음, 즉 맵 벗어나도 상관 x 3. 비바라기 > 맨 아래 1열 2열 맨 아래 위 행 1열 2열 비구름 생성 4. 비 구름을 M 번 이동, 방향 8개, 방향 d, 거리 s, 5. 방향 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 1. 모든 구름..

문제 : https://www.acmicpc.net/problem/2579 첫번째 풀이 (재귀, 시간초과) start: 시작 인덱스, seq: 연속 2개 선택하는 것 판단 result: 현재까지 선택한 계단의 합 def dfs(start, seq, result): global ans if seq > 2: return if start > N: return if start == 5: ans = max(ans, result) return if start + 1 < N: dfs(start + 1, seq+1, result+a[start+1]) if start + 2 < N: dfs(start + 2, 1, result+a[start+2]) N = int(input()) a = [] ans = 0 for i in..

문제 출처: https://www.acmicpc.net/problem/20055 첫번째 풀이 최적화 이전 방법 (Python3는 시간초과, pypy3 는 통과) 1. 한 칸 회전 deque의 rotate를 이용하여 구현, robot을 벨트 위 index로 저장 popleft를 사용하여 처음 넣은 로봇이 처음 이동하게 만듦 robot에 저장된 인덱스를 1씩 증가 시켜 벨트 N번 칸이 아닐 경우만 로봇을 저장 2. 모든 로봇 한 칸씩 이동 popleft로 먼저 올라간 로봇 먼저 로봇의 위치를 저장한 robots 배열에서 현재 로봇이 다음 칸에 로봇이 있는지 확인 not in 으로 확인 처음 로봇이 N번째 위치에 있다면 robots 배열에 다시 삽입 X 3. 로봇 추가 4. count로 내구도 0인 벨트 개수..

문제 출처: 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번 지역은 행이 감소하면서 열이 증가하는 순서로 탐색하면 자칫 탐색을 못하..

packet (패킷) : chunks of data packet switching = foward packet, 패킷을 전달한다 host들이 응용 계층에서 메세지를 패킷으로 쪼개는 것 switch (스위치) : =라우터 router (라우터) - 3계층 장비, LAN과 LAN을 연결하거나 LAN과 WAN을 연결하기 위한 인터넷 네트워킹 장비 - 패킷의 위치를 추출하여, 그 위치에 대한 최적의 경로를 지정하며, 이 경로를 따라 데이터 패킷을 다음 장치로 전송시키는 장비 - 라우팅 프로토콜은 경로 설정을 하여 원하는 목적지까지 지정된 데이터가 안전하게 전달되도록 함 host (호스트) - end system, 단말기를 의미하며 data를 chunks 형태인 packet을 보냄 - host는 L 길이와 R 전..

문제 출처: https://www.acmicpc.net/problem/17142 나의 접근법 먼저 바이러스 중에서 M개를 선택하는 조합의 경우를 모두 구합니다. 그리고 난 뒤 그래프의 모든 곳을 방문해야 하는데 이를 위해 DFS와 BFS중 무엇을 사용할지 고민 했습니다. 구현을 바로 하기 전에 먼저 DFS로 머리 속에서 시뮬레이션을 돌려봤습니다. 1. DFS로 할 경우 첫번째로 선택한 바이러스의 위치가 모든 곳을 탐색하고 이동할 때 마다 시간을 적습니다. 2. 그 다음 바이러스가 탐색할 때 첫번째 바이러스가 저장한 장소 중 자신이 탐색하는 시간보다 큰 경우에만 탐색을 하며 시간을 업데이트 합니다. 위 방식으로 하게 되면 불필요한 계산이 생기고 방문했던 곳을 또 방문하게 된다면 visited 판단에서 에러..

문제 출처: https://www.acmicpc.net/problem/17140 나의 접근법 먼저 행과 열의 최대길이를 구분하여 계산합니다. R 연산 checkList 배열에 [숫자, 개수]를 함께 묶어 저장하여 not in으로 중복을 해결했습니다. 정렬은 sort함수의 lambda를 사용했습니다. 행이나 열의 최대 길이는 maxLen을 통해 값을 저장하여 maxLen 보다 작은 행 또는 열의 길이를 가진 경우 차이만큼 0을 추가해줍니다. C 연산 반복문으로 열을 바로 계산하면 R x C 만큼 더 늘어나야 하므로 for i in range(clen): checkList = [] col = list(zip(*arr))[i] 열 마다 zip 함수를 이용하여 편하게 행으로 바꿔 작업하였습니다. 행 연산 보다 ..

문제 출처: https://www.acmicpc.net/problem/14501 나의 접근법 상담 일정 전체를 탐색하는 반복문 안에 일정이 가능한지 확인하며 일정과 T를 확인하며 N+1이 넘어갈 때까지 while로 체크하며 해결하려고 했습니다. 하지만 이렇게 할 경우 예제1 은 1일 -> 4일 -> 5일은 찾지만 예제 4의 1일 -> 6일 -> 7일은 찾았지만 1일 -> 6일 -> 8일의 경우는 못 찾았습니다. 이 문제점을 찾았더니 DFS와 백트래킹이 생각나서 바로 구현 방식을 틀고 다음과 같이 작성하였습니다. 첫번째 코드 def dfs(startDate, period, pay): global ans # 상담하면 퇴사날이 넘어 가는 경우 for i in range(startDate+period, N+1)..

문제 출처: https://www.acmicpc.net/problem/14499 나의 접근법 먼저 이해가 안되어서 문제를 그림으로 펼쳐서 주사위를 하나 하나 이동시키고 윗면(x표시)을 확인했습니다. 처음에 전개도가 나와서 시작부터 전개도 모양인줄 알고 따라했는데 도처히 예제처럼 답이 안나와서 헤맸는데 제가 문제를 제대로 읽지 않았습니다. 처음 시작은 주사위의 모든 면이 0 입니다! 그 후 각 이동 명령에서 주사위의 이동을 다음과 같이 표현하며 규칙이나 성질을 찾아봤습니다. 위와 같이 동쪽으로 이동할 경우 윗면이 동쪽으로 이동하므로 배열에서 4번으로 이동하게 됩니다. 동, 서, 남, 북 모두 규칙을 찾아 구현을 하니 쉽게 정답을 맞을 수 있었습니다. 제출 코드 def check(x, y): if 0

문제 출처: https://www.acmicpc.net/problem/14500 나의 접근법 저는 처음에 풀 방법이 딱 한가지 밖에 생각이 안났습니다. 바로 테트로미노의 모든 회전과 대칭 좌표를 직접 찾아 반복문을 돌려가며 일일이 확인하는 것이었습니다. 그런데 제가 이번에도 문제를 제대로 확인하지 않아 회전만 구하고 대칭은 놓치고 구현했습니다. 그런데 제가 생각한 테트리스에는 대칭이 없어서 문제를 제대로 숙지 안하고 예측하여 푼 것이 화근이었습니다. 어쨌든 대칭까지 구현했는데 역시나 처음에는 틀렸습니다. 다행히 좋은 반례들을 모아놓은 분이 계셔서 그 반례 덕분에 코드 오류를 잡을 수 있었습니다. 그 반례는 맨 아래 첨부하겠습니다. 첫번째 코드 def check(tetro): x1, y1, x2, y2, ..

문제 출처: 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..