흙금이네 블로그

아이디어 BFS로 나이트가 체스판의 각 칸에 방문하기 위한 최소 이동 횟수를 구한다. 풀이 #1 (Python) 나이트가 이동할 수 있는 위치의 변화 값을 튜플로 리스트 delta에 저장한다. 체스판 내 각 칸의 최소 이동 횟수를 저장하기 위해 (N+1)×(N+1) 크기의 0으로 채워진 2차원 리스트 visited를 생성한다. visited에서 나이트의 초기 위치를 1로 저장하고, 큐 queue에 나이트의 초기 위치를 저장한다. while문에서 BFS로 나이트가 이동할 수 있는 칸으로 이동하며 visted에 최소 이동 횟수를 저장해 나간다. 체스판의 모든 칸에 대해 최소 이동 횟수를 저장한 후, for문에서 상대편 말을 잡기 위한 최소 이동 횟수들을 출력한다. import sys input = sys.s..

아이디어 BFS로 칸을 이동하며 게임을 클리어할 수 있는지 확인한다. 풀이 #1 (Python) 지도 정보를 lines에 입력 받고, 큐 queue에 칸 인덱스, 줄 인덱스, 시간이 모두 0인 튜플을 초기값으로 저장한다. while문에서 queue에 저장된 튜플을 차례로 꺼내 i, j, t에 저장한다. 반대편 줄의 i+k번 칸으로 이동해 게임을 클리어할 수 있다면 결과값 res에 1을 저장하고 break로 while문을 종료한다. 게임을 클리어할 수 없다면 i+k번 이하의 칸(k는 1 이상이므로 최소 i+1번 칸)은 유효하다. 따라서 반대편 줄의 i+k번 칸, i+1번 칸이 안전하면 queue에 추가하고, i-1번 칸은 안전한 칸이면서 이번 차례에 사라지지 않으면 queue에 추가한다. queue에 추가..

지난 2월 24, 25일 부산에서 열린 패스핵에 다녀 왔습니다. 기획자, 디자이너, 개발자, 메이커로 총 4개의 포지션이 있는데 저는 개발자로 참여했습니다. 입장해서 참가자 등록을 하면 이름표, 패스핵 후드티와 여러 굿즈를 받을 수 있었습니다. 강당에 모여 오프닝 행사를 하고, 간단한 자기소개 이후에 팀 빌딩 시간이 주어집니다. 저는 싸피 동기의 권유로 동기 지인분들과 함께 팀 빌딩을 마친 상태로 참가했습니다. 저희 팀은 개발자 4명, 기획자 1명으로 구성된 팀으로 저는 디자이너 겸 프론트엔드를 담당했고, 다른 팀원분들은 각각 기획자 겸 메이커, AI 담당, 백엔드 담당, 아두이노 담당으로 역할을 맡아 주셨습니다. 이번 패스핵은 메이커톤이어서 하드웨어를 활용해야 했습니다. 스폰서측에서 재료들을 일부 지원..

아이디어 만들 수 있는 2진 수열 개수의 규칙을 찾는다. 풀이 #1 만들 수 있는 2진 수열은 타일 개수에 따라 피보나치 수열을 이루고 있다. res와 prev에 각각 현재와 이전 피보나치 수 저장하여 계산하고, res를 15,746으로 나눈 나머지를 출력한다. def solution(): N = int(input()) prev = res = 1 for i in range(2, N+1): res, prev = (res+prev)%15746, res print(res) solution() 풀이 #2 행렬 곱을 이용하여 피보나치 수열을 빠르게 구할 수 있다. 2차원 행렬을 1차원 튜플로 표현하고, N을 이루는 2의 제곱수마다 해당하는 거듭제곱 행렬을 곱한다. def fibo(a, b): return ((a[..

아이디어 돌 개수에 따른 결과의 규칙을 찾는다. 풀이 돌 개수가 홀수면 상근이가, 짝수면 창영이가 게임을 이기게 된다. print('SK' if int(input())%2 else 'CY')

아이디어 규칙을 찾고 동적 계획법으로 가짓수를 계산한다. 풀이 고정석으로 구분된 연속된 좌석에 대해 그 가짓수가 좌석 개수에 따라 피보나치 수열을 이루고 있다. 리스트 vip에는 0과 좌석 끝 번호를 추가하여 고정석 번호를 저장하고, 리스트 dp에는 피보나치 수열을 저장한다. 전체 가짓수는 연속된 일반 좌석들의 곱이므로 결과값 res에 일반 좌석 개수에 따른 피보나치 수열의 수를 곱한다. import sys input = sys.stdin.readline def solution(): N = int(input()) M = int(input()) vip = [0]+[int(input()) for _ in range(M)]+[N+1] dp = [1]*(N+1) for i in range(2, N+1): dp[..

아이디어 동적 계획법으로 각 블록을 사용하여 탑을 만드는 경우의 수를 구해 나간다. 풀이 #1 (Python) 2624번 동전 바꿔주기 문제 풀이와 유사하다. 0으로 채워진 H+1 크기의 리스트 dp를 생성하는데, dp[i]에는 높이 i의 탑을 만드는 경우의 수를 저장한다. for문에서 리스트 blocks에 블록들의 높이를 입력 받고, temp에 리스트 dp를 복사하여 저장한다. blocks의 블록 하나로 해당 블록의 높이만큼 탑을 쌓는 경우의 수 dp[b]를 1 증가시키고, 해당 블록을 기존 블록들을 함께 사용해 탑을 쌓아 높이 i의 탑을 경우의 수를 temp[i-b]만큼 증가시킨다. 높이 H의 탑을 쌓는 경우의 수를 10,007로 나눈 나머지를 출력한다. import sys input = sys.st..

아이디어 동적 계획법으로 각 동전을 사용한 교환 방법의 가짓수를 저장해 나간다. 풀이 #1 (Python) 0으로 채워진 T+1 크기의 리스트 dp를 생성하는데, dp[i]에는 i원의 교환 방법 가짓수를 저장한다. for문에서 동전의 금액 p와 동전 개수 n을 입력 받고, temp에 리스트 dp를 복사하여 저장한다. p원 동전으로만 교환하는 방법의 가짓수는 1이므로 n 이하의 자연수 i에 대해 dp[p*i]를 1씩 증가시킨다. p원 동전을 사용하여 교환하는 방법의 수는 그 금액보다 p원만큼 작은 금액을 기존 동전들로 교환하는 방법의 수와 같다. 따라서 기존 동전들과 함께 사용하여 교환하는 방법의 수 dp[j]에 기존 동전들로만 교환하는 방법의 수 dp[j-p*i]를 더한다. 지폐의 금액 T를 넘는 동전의..

아이디어 동적 계획법으로 감소하는 수열 합의 최댓값을 구한다. 풀이 #1 (Python) 리스트 dp에 수열 A와 같은 값들을 저장한다. 이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다. max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다. def solution(): N = int(input()) A = tuple(map(int, input().split())) dp = list(A) for i in range(N): for j in range(i+1, N): if A[j] dp[j]: dp[j] = dp[i]+A[j] print(max(dp)) solution() 풀이 #2 (Jav..

아이디어 덱을 이용하여 풍선 안 종이에 적힌 수에 따라 풍선을 회전한다. 풀이 덱을 사용하기 위해 collections 모듈의 deque를 불러온다. enumerate 함수를 이용하여 풍선의 번호와 풍선 안 종이에 적힌 수를 튜플 형태로 덱 balloon에 저장한다. for문에서 popleft로 balloon의 맨 앞 풍선을 꺼내 풍선의 번호와 종이에 적힌 수를 각각 r과 d에 할당한다. 결과값 리스트 res에 풍선의 번호를 추가하고, d에 따라 풍선을 이동한다. d가 양수이면 풍선들을 왼쪽으로 회전(-)시키는데 popleft로 풍선이 하나 줄었으므로 rotate에 -(d-1)을 인자로 넘긴다. d가 양수가 아니면(음수인 경우) 풍선들을 오른쪽으로 회전(+)시키기 위해 rotate에 -d를 인자로 넘긴다..