성준이의 개발블로그 성준이의 개발블로그

문제 링크https://www.acmicpc.net/problem/17837문제 이해이문제는 체스판 위에 말이 있는데 말 위에 다른 말을 쌓을 수 있고, 4개의 말이 쌓였을 때 게임이 종료되고 턴을 출력하는 문제입니다.체스판 위에서 말이 이동할 수 있는 방향은 상하좌우 입니다.1 : 오른쪽(→)2: 왼쪽(←)3: 위쪽(↑)4: 아래쪽(↓)턴이 진행되면 1번부터 k번째 말까지 순서대로 이동방향으로 이동합니다.이 때 체스판의 색깔에 따라 이동하는 방법이 다릅니다.1번말이 이동하는 것을 예시로 들겠습니다. 1번말의 상태는 1번위에 2번이 쌓여있는 상태입니다.1번말이 이동하려는 칸이흰칸이면 1번 위에 있는 말들이랑 다 같이 이동하는데, 원래 있던 말 위에 1,2번을 쌓습니다.빨간칸이면 다 이동하고 쌓여있는 순서..

문제 링크https://www.acmicpc.net/problem/1063문제 이해이 문제는 체스판에서 킹을 이리저리 움직이다가 마지막에 킹의 위치와 돌의 위치를 구하는 문제입니다.킹은 상하좌우, 대각선으로 전부 이동할 수 있습니다.그리고 킹이 움직이는 자리에 돌이 있다면 돌도 킹이 움직였던 방향으로 움직입니다.킹이 오른쪽으로 한칸 움직였다면 돌도 오른쪽으로 한칸 움직입니다.한번 움직였을 때, 킹이나 돌 중 하나가 체스판을 벗어날 경우 해당 움직임을 건너뜁니다.아이디어그래서 떠올린 아이디어는 다음과 같습니다.킹의 좌표와 돌의 좌표를 숫자로 저장한다.킹이 먼저 이동할 위치를 확인하고, 그 자리에 돌이 있으면 돌까지 이동할 위치를 확인한다.위치 확인 시 둘중 하나라도 체스판 밖이라면 건너뛴다.확인한 위치로 ..

문제 링크https://www.acmicpc.net/problem/2980문제 이해이 문제는 상근이가 신호등을 거치며 도로의 끝까지 가는데 걸리는 시간을 구하는 문제입니다. 우선 첫번째 입력을 예시로 들었을 때거리 3에 있는 신호등은 1~5초는 빨간불 6~10초는 초록불거리 5에 있는 신호등은 1~2초는 빨간불 3~4초는 초록불 이렇게 반복이 됩니다. 그래서 신호등에 도착했을 때의 현재 시간을 보고 어떤 불인지 계산하여 이동하면 됩니다.빨간불이 처음 바뀔 때부터 다음 바뀔때까지의 걸리는 시간은 (초록불 시간 + 빨간불 시간)이 걸립니다.그래서 전체시간 % (초록불 시간 + 빨간불 시간) 연산을 해준다면 사이클 시작 기준(0초)으로 어떤 신호등이 켜져있는지 확인할 수 있습니다.저 결과가 1~5초라면 빨간불..

문제 링크https://www.acmicpc.net/problem/3048문제 이해우선 문제를 확인하면 첫번째 그룹 ABC, 두번째 그룹 DEF면 초기 상태는 “CBADEF” 입니다.첫번째 그룹은 A부터 오른쪽으로 이동해서 A / B A / C B A 상태가 되는거고 두번째 그룹은 D부터 왼쪽으로 이동 해서 D / D E / D E F 상태가 됩니다.어쨌든 시간별로 상태를 보면 다음과 같이 개미의 상태가 변합니다.T0 : CBADEFT1 : CBDAEFT2 : CDBEAFT3 : DCEBFA아이디어제가 생각한 아이디어는 다음과 같습니다.첫번째 그룹의 개미가 두번째 그룹의 개미를 만난다면 둘의 위치를 바꾸고 인덱스 +2인덱스를 + 2 해주는 이유는 한번 이동했던 개미는 같은 시간대에 다시 이동하지 않기 때..

문제 링크https://www.acmicpc.net/problem/2206아이디어 이 문제는 (1,1) 부터 (N,M) 까지 가는 최단 경로를 구하는 문제입니다.0은 이동할 수 있는 곳(길)이고, 1은 이동할 수 없는 곳(벽)입니다.여기까지만 하면 보편적인 bfs 문제라고 생각할 수 있는데, 이 문제는 벽을 1개 부술수 있는 기회가 주어집니다. 벽을 3개 세우는 문제에서 백트래킹을 사용해서 벽을 세우고 바이러스가 최소로 퍼지게 했기 때문에 처음에 백트래킹을 사용해서 벽을 하나씩 부셔가며 bfs를 돌려 했지만 입력이 1000씩 이였습니다.bfs의 시간 복잡도는 O(V + E)로 간선의 개수는 "1000 X 1000 = 100만" 이고 Edge의 개수는 "상하좌우 4방향 = 400만" 입니다. 총 500만인..

문제 링크https://www.acmicpc.net/problem/10816아이디어이 문제는 후보군에 나온 카드를 상근이가 몇 장 가지고 있는지 출력하는 문제입니다. 처음에 알고리즘 분류를 봤을 때 이분 탐색이 있어서 이분 탐색으로 해봐야겠다고 생각하고제가 익혔던 이진 탐색 코드를 사용해서 자신 있게 mid를 찾고 return 하려고 하는데, 같은 값을 여러 개 찾아서 출력해야 했습니다.그래서 같은 값을 찾으면 양 옆으로 뻗어가며 상근이의 카드에서 일치하는게 몇 개 있는지 찾으려 했는데, 구현이 저에게는 어려워서 포기하고 다른 사람들의 풀이를 보았습니다. 저랑 같은 생각을 하신 분이 있었는데 그 분은 구현했지만 시간복잡도를 충족을 못해서 다른 풀이를 찾으셨습니다.그래서 최악의 시간복잡도를 생각해보니상근이..

문제https://www.acmicpc.net/problem/1874아이디어이 문제는 1부터 N까지 자연수를 오름차순으로 원하는대로 push, pop해서 입력의 두번째줄부터 마지막까지의 수열을 만들 수 있는지 확인하고 가능하다면 push하는 연산은 + 출력, pop하는 연산은 -를 출력하고, 가능하지 않다면 NO를 출력하는 문제입니다. 입력1부터 따라해보며 진행했습니다.입력1의 첫번째 수는 4입니다. 4번 push(1,2,3,4) 후 1번 pop(4) 합니다.두번째 수는 3입니다. 이미 스택의 맨 위에 3이 있으므로 1번 pop(3) 합니다.세번째 수는 6입니다. 2번 push(5,6) 후 1번 pop(6)합니다.네번째 수는 8입니다. 2번 push(7,8)후 pop(8)합니다.다섯번째 수는 7입니다. ..

문제https://www.acmicpc.net/problem/2164아이디어이 문제는 숫자 N이 주어지면 밑에서부터 N, N-1, N-2 처럼 피라미드 형식으로 숫자가 쌓입니다.이 문제는 두 단계로 이루어지는데 첫번째 단계, 카드 더미 맨 위에서 한장을 버리는 것.두번째 단계, 카드 더미 맨 위에서 한장을 뽑아 가장 아래에 넣는 것.입니다. 양쪽에서 데이터를 추가하고 삭제해야 하기 때문에 일반 Queue가 아닌 Double Ended Queue를 써야겠다고 생각했습니다.  그래서 큰 숫자부터 순서대로 넣은 다음에 첫번째 단계와 두번째 단계를 수행하고 덱에 요소가 하나만 있다면 출력하는 코드를 작성하였습니다.첫번째 소스코드from collections import dequeq = deque()n = int..