![]()
푼 날짜 : 2024.08.17푼 문제 : [1697] / 숨바꼭질사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근하였다. 이동 가능한 범위는 현재위치에 +1, -1, *2 였기 때문에 이를 배열로 만들어 반복문을 돌며 확인하도록 했다.나머지 방식은 일반적인 BFS와 동일하다. 코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split())px = ['-', '+', '*']def BFS(visited, v): queue = deque([v]) visited[v] = 0 while queue: now = queue.popleft() nx = now ..
![]()
푼 날짜 : 2024.08.16푼 문제 : [14248] / 점프 점프사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근하였다. 한 칸씩 이동하는 다른 문제와 달리 이번 문제는 돌다리의 숫자만큼 좌우로 움직일 수 있으므로 그 숫자를 저장하고 현재 위치에서 빼거나 더하는 방식으로 접근하였다. 코드 :import sysfrom collections import dequeN = int(sys.stdin.readline())graph_ = list(map(int, sys.stdin.readline().split()))graph_.insert(0, 0) # 문제를 편하게 풀기 위해 index 0 추가visited = [0 for _ in range(N+1)]start = int(sys.stdin..
![]()
푼 날짜 : 2024.08.03푼 문제 : [1932] / 정수 삼각형사용한 언어 : python알고리즘 : DP 점화식:dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+lst[i][j] *주의)첫 번째 요소에는 dp[i-1][0]만 더할 수 있다.마지막 요소에는 dp[i-1][j]를 더할 수 없다.=> 둘 다 index error 가 발생하므로 두 부분은 따로 작성해주었다. 일단 이렇게 그림을 그려 이해했다.머리로 생각하는 삼각형 구조와 입력값으로 주어지는 배열의 인덱스를 이해하기 위해 둘 다 그림으로 그렸다. 코드로 출력했을 땐, 첨부 이미지처럼 나온다. 코드:import sysN = int(sys.stdin.readline())lst = []for _ in..
![]()
푼 날짜 : 2024.07.25푼 문제 : [2579] / 계단오르기사용한 언어 : python 점화식:dp[i] = max(dp[i-2], dp[i-3]+score[i-1])+score[i] dp - 이전 계산 값을 담는 dp 배열score - 계단점수를 담은 배열 푼 방법 : DP처음에 초기값을 잘못 설정해서 한참을 헤맸다 이해하기 위해 쉽게 그림을 그려보면, i는 현재 값계단을 3연속 밟지 않으면서, 현재 값을 만들기 위해서는 3전칸+1전칸에 더하거나, 2전칸에 더하는 경우가 만들어진다. dp는 초기값을 잘 설정하는게 중요한데, 초기값 설정은 아래 코드에서 확인할 수 있다. 코드 :import sysN = int(sys.stdin.readline())score = []for _ in ra..
![]()
푼 날짜 : 2024.07.25푼 문제 : [21736] / 헌내기는 친구가 필요해사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근어휴 이제는 척하면 척! 쉽다 쉬워(정말?) 'X' 인 경우는 벽이기 때문에 이동을 막고, 'O' 와 'P' 의 경우에는 이동을 허용한다.이때 'P'인 경우 정답 += 1 해준다.( ans 가 0일 경우 친구를 못만나서 슬프니까 'TT' 출력하기 ! ) 코드 :import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph_ = []dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]def BFS(graph_, visited, v): queue ..
![]()
푼 날짜 : 2024.07.25푼 문제 : [17219] / 쉬운 최단거리사용한 언어 : python 푼 방법 :파이썬 딕셔너리를 사용하여 key: value 형식으로 매핑하여 저장하였다. 코드 :import sysN, M = map(int, sys.stdin.readline().split())myDict = {}for _ in range(N): url, pw = sys.stdin.readline().split() myDict[url] = pwfor _ in range(M): url = sys.stdin.readline().rstrip() print(myDict[url]) 쉽다!
![]()
푼 날짜 : 2024.07.25푼 문제 : [14940] / 쉬운 최단거리사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근하였다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력 처음에는 리스트 형식( [1, 2, 3, ~] )으로 출력을 잘못해서 틀렸고, 두 번째에는 위의 예외처리를 안해줘서 틀렸다. 항상 문제를 꼼꼼하게 읽자! 코드 :import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph_ = []visited = [[0 for _ in range(M)] for _ in range(N)]dx = [1, -..
![]()
푼 날짜 : 2024.07.24푼 문제 : [11727] / 2×n 타일링 2사용한 언어 : python 점화식: dp[i] = dp[i−2]∗2+dp[i−1] (i≥2) 어떻게 구했냐면... 모를 땐 직접 그려보자 점화식 찾기.. (i-1) 에는 너비를 맞추기 위해 블록 하나(=> 2*1타일)씩을 붙일 수 있지만 (i-2) 에는 두 칸을 붙일 수 있으므로 x2를 해준다는 식으로 이해했다. (=> 2는 2*1타일과 2*2타일 두 개를 의미) 예를 들어 현재 주어진 수가 5라면 가로로 5칸을 차지한다.이럴 경우 이전(i-1) 값인 4에는 1을 붙여야 5칸을 만들 수 있다.그 이전(i-2) 값인 3에는 2를 붙여야 5칸을 만들 수 있다. 코드 :import sysN = int(sys.stdin...
