Dalin's Archive

문제 보러 가기! 평범한 BFS 문제에서 조금 더 생각해야 했다.. dq에는 위치, 얼마나 걸렸는지를 가지고 있는다. 앞으로 걷고, 뒤로 걷고, 순간이동하는 경우를 범위, 방문 체크한 후에 dq에 넣는다. 일단 N이 0일 때는 곱하기 2해도 0이고, -1은 해도 점점 멀어지는 거니까 괜히 시간만 든다. N이 0일 때는 일단 무조건 한 칸 앞으로 가야 하니까, dq에 (N+1, 1)을 넣고 시작한다. 틀리다가 질문 게시판의 반례!!를 보고 문제를 알았다. dq에 넣을 때 방문 체크를 하면 안되고, 뺄 때 방문 체크를 해야 한다! 1 10의 경우에 1->2->4->5->10으로 가는 게 젤 빨리 가는 것인데, 1에서 2로 갈 때 걸어서 갈 수도, 순간 이동해서 갈 수도 있다. dq에 넣을 때 방문 체크를 하..

문제 보러 가기! 오.. 문제가 생각보다 쉽게? 직관적으로? 풀려서 신기하다... 문자열이 주어졌을 때, 회문이 아닌 가장 긴 부분 문자열의 길이를 구하는 문제이다! 그런 부분 문자열이 없으면 -1을 출력하라고 했다. 일단 -1을 출력해야 하는 경우를 생각해봤다. 단어가 한 글자인 경우(어떻게 봐도 회문이 되니까!), 맨 처음에 쭉~ 봐서 모두 같은 알파벳으로 이뤄진 경우에는 -1를 출력하고 끝냈다. 그게 아닌 경우는 bfs처럼 봤다. 일단 전체 문자열을 넣어주고 시작한다. popleft한 것이 회문인지 본다. 회문이 아니면, 그 문자열 길이를 리턴한다. 그게 젤 긴 문자열일테니까 정답! 회문이라면 그 문자열에서 맨 앞 한글자를 뺀 단어, 맨 뒤 한글자를 뺀 단어를 큐에 넣는다. -이걸 한 글자가 될 때..

문제 보러 가기! import sys input = sys.stdin.readline MIISS = lambda: map(int, input().strip().split()) dp = [[0] * 100_001 for _ in range(4)] dp[1][1] = 1 dp[2][2] = 1 dp[1][3], dp[2][3], dp[3][3] = 1, 1, 1 for i in range(4, 100_001): dp[1][i] = (dp[2][i - 1] + dp[3][i - 1]) % 1_000_000_009 dp[2][i] = (dp[1][i - 2] + dp[3][i - 2]) % 1_000_000_009 dp[3][i] = (dp[1][i - 3] + dp[2][i - 3]) % 1_000_000_0..

문제 보러 가기! 하늘색 숫자는 원래 그 자리의 숫자이다.(arr에 저장했다.) dp는 n X n 2차원 리스트로 만들었다. 세로는 위에서부터 몇 층 내려왔는지, 가로는 지금의 가로 위치를 뜻한다. 그 위치로 올 수 있는 숫자 중 큰 수(각 층에서 0번째 자리는 바로 위에서만 내려올 수만 있고, 가장 오른쪽 수는 대각선 왼쪽에서만 내려올 수 있다. 다른 수들은 바로 위 or 대각선 왼쪽 수 중 큰 수!! )에다가 원래 그 자리의 숫자를 더해서 저장했다. 아! 문제에 '아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.'라고 쓰여 있는데, 인덱스로 따지면..! 아래 그림처럼 된다. 노란 동그라미 친 숫자 기준으로 보면, 왼쪽 대각..

문제 보러 가기! 처음에 아이디어가 딱 떠올랐다 ! 그 후에 문제를 잘 이해하지 못해서, 조건 생각 못해서 틀리다가 맞았다 !! 정답률이 낮은 이유를 알 것 같다.. 꼼꼼하게 문제를 읽어야 겠다..!! 사전에 있는 단어가 들어온다. 그 후에 문장이 들어온다. 그 문장을 해석하는 경우의 수를 출력하는 문제이다! 그 문장의 단어들이 사전에 있는 단어와 첫 글자와 끝 글자가 일치하고, 가운데 글자들이 있으면 해석될 수 있다. 예를 들어서 사전에 abc, cba가 있는데, 'acb'가 들어오면 두 가지 방식으로 해석될 수 있는 것이다. 그래서 2차원 리스트, defaultdict을 이용해서, 어떤 단어가 들어왔을 때 몇 가지 방식으로 해석될 수 있는지 개수를 저장했다. 2차원 리스트를 53X 53로 만들었다. ..

문제 보러 가기! 문제와 함께 하는 즐거운 크리스마스 이브 ~ 구해야 하는 것은 두 기어가 주어졌을 때 맞물리게 하는 가장 짧은 가로 너비이다. 즉 맞물리는 최대 길이를 찾으면 된다. (두 기어의 길이 합에서 맞물리는 최대 길이를 빼면 정답이 된다.) part1, part2에 오는 문자들의 개수가 적어서, 일일이 다 봐주었다! 두 기어가 맞물리는지, 아닌지 봐줄 때 아래 세 가지 경우를 봐줄 수 있다. 1번, 2번 경우이다. 노란색 왼쪽이 1번, 오른쪽이 2번 경우이다. 1번) 짧은 기어를 기준으로, 짧은 기어가 긴 기어 왼쪽에서 하나씩 더 겹쳐지면서, 그럴 때 맞물리는지 볼 수 있다. 2번) 짧은 기어가 긴 기어 오른쪽에서 하나씩 더 겹치지면서, 그럴 때 맞물리는지 볼 수 있다. -> 맞물리면 그때까지..

문제로 가기! 몇 초에 몇 번 이동했을 때, 그때까지 먹은 자두 수를 dp 테이블에 저장했다.(2차원 리스트로 dp) 이 부분에 점화식 설명을 적을 것이다.. 그림으로 그려서 설명하려고 하는데, 지금 태블릿을 누구한테 빌려줘서... 내일 할게용 초가 지나갈 수록 자두가 몇번 나무에서 떨어지는지 쭉~ 보면서, 몇 번 나무에서 떨어졌는지에 따라서 다르게 했다. 1번 나무에서 자두 떨어졌을 때) 한 번도 이동 안했을 때 1번 나무에서 시작하니까, dp[0][j]가 전에 비해서 1 증가. 그 것보다 많이 이동했을 때는, 짝수번 이동했는지 홀수번 이동했는지에 따라서 몇 번 나무에 있는지 알 수 있다. 짝수번째로 이동했으면 1번 나무에 있는 것이다. 최대 이동 횟수일 때는 따로 처리한다. 2번 나무에서 자두 떨어졌..

문제 풀러 가기! 정성스럽게 구현했다 ^^ 엄청난 알고리즘!!보다는, 조건을 잘 따지고 실수하지 않으면 되는 것 같다.. 잘못을 찾을 때, 디버깅 연습도 해서 좋았다. ^^ 내가 실수했던 부분들!✅ 가을) 나무 개수가 5의 배수이면 인접한 8개 칸에 나이가 1인 나무가 생긴다. 그런데 나는 ni, nj = i+ki, j+kj 부분을 처음에 안 썼다.. 그리고 ni, nj가 아니라 ki, kj를 범위 체크하고, ki, kj부분에 나무를 더해줘서 문제였다... K년 후에 남은 나무 개수를 셀 때! 처음에는 쭉 보면서 그 지점에 나무가 있으면 1을 더했다. 그런데 그 지점에 나무가 여러 그루 있을 수도 있으니까, ground_tree[i][j]의 len을 세줘야 했다. 코드 👩‍💻 import sys inpu..

문제 보러 가기! 문제를 읽어보니 토끼가 정보섬에 올라간 이유는! 당근을 많이 주워 가기 위해서였다 ! 🥕🥕 토끼는 →, ↘, ↗ 방향으로만 이동할 수 있다. 정문으로 들어와서 쪽문으로 나가는데, 쪽문은 여러 개이고 a 쪽문을 지나서 b 쪽문으로 나가도 상관없다. 토끼가 섬에 있을 동안 얻을 수 있는 당근의 최대 개수를 구하는 문제였다! (쪽문으로 빠져나갈 수 없는 경우에는 -1을 출력한다) ㅠㅠㅠ 많이 틀리다가 맞았따.. ㅠㅠㅠㅠ 일단은 토끼가 정문으로 들어오는 것은 'R'로 표시되기 때문에, 그 위치를 찾았다. 그 후에는 그쪽보다 오른쪽인 지점들을 다 쭉~ 봐주었다. 그러면서 해당 지점일 때까지 얻을 수 있는 당근의 최대 개수로 업데이트했다. (그 지점으로 올 수 있는 방법은 →, ↘,..

문제 보러 가기! ㅎㅎ제목부터 재밌다. (TMI: 나도 젤다의 전설 바람의 숨결! 게임을 종종 한다 ㅎㅎ ) 전에 나는 평범한 다익스트라 문제만 풀어봤는데, 조금 응용한 문제를 풀어봐서 재밌었다. 시작하는 점이 정해져 있고(제일 왼쪽 위), 음의 간선이 없으니까 다익스트라가 가능하다. 다익스트라는 특정 노드에서 시작해서, 다른 노드로 가는 최단 경로를 각각 구해준다. 이 문제는 잃은 도둑 루피가 최소로 되도록! 0,0 점에서 N-1,N-1까지 이동해야 한다. 조금 주의할 것이 있다고 하면~ 1차원 리스트로 최단 경로 테이블을 만들기 위해서, i좌표와 j 좌표를 곱해서 만든 하나의 숫자로 인덱스 위치를 표현했다. 상하좌우로 갈 때도 그 하나의 숫자를 바꿔줘야 한다. (위: -N, 아래: N, 왼쪽: -1,..