OSNIM

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

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

문제 출처: 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() 함수를 사용합니다. ..

탐색 (Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정으로 그래프, 트리등의 자료구조 안에서 탐색이라는 과정을 사용합니다. 대표적인 탐색 알고리즘으로는 DFS, BFS이 있습니다. 이러한 탐색 알고리즘을 사용하기 위해서는 스택(Stack)과 큐(Queue)라는 자료구조를 사용합니다. 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 push(삽입), pop(삭제) 함수들을 사용합니다. push(삽입), pop(삭제)를 사용하기 위해서는 오버플로우(Overflow), 언더플로우(Underflow)를 고려해야 합니다. 오버플로우(Overflow): 스택과 큐 등의 자료구조의 용량이 가득 찬 상태에서 push()를 수행할 경우 발생합니다. 언더플로우(Underflow): ..

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

SQL JOIN SQL에서 JOIN이란 두 개 이상의 테이블(릴레이션)을 연결하여 데이터를 검색하는 방법으로 두 테이블에서 관련된 튜플을 결합하여 하나의 튜플로 만들어 출력합니다. JOIN은 DML중 SELECT에서 조건을 추가할 때 사용하는 방법으로 보통 기본키(PK)와 외래키를 사용하여 JOIN을 합니다. JOIN의 종류를 밴 다이어그램으로 표현하면 다음과 같습니다. 위 그림을 SQL로 표현하면 다음과 같습니다. SELECT FROM [기준 테이블 명] LEFT JOIN [JOIN 되는 테이블] ON [기준 테이블.외래키] = [JOIN 테이블.기본키] 꼭 외래키와 기본키일 필요는 없지만 대부분 외래키, 기본키를 이용하여 코드를 작성한다고 생각하여 위와 같이 작성했습니다. RIGHT JOIN은 LEF..

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