알고리즘

푼 날짜 : 2024.08.18푼 문제 : [1326] / 폴짝폴짝사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다.  어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.    이 부분이 중요한데 앞으로 가든 뒤로 가든 현재 위치의 징검다리의 수의 배수만큼만 이동한다는 거 !예시를 들자면 현재위치가 인덱스 4번이고 4번 징검다리에 쓰여 있는 수가 3이라면,  이렇게 1과 7로 이동할 수 있다.만약 배열이 더 길다면 인덱스 7, 10, 13, 16 .... 이렇게 갈 수 있다!   추가적인 테스트케이스를 첨부해보자면,    마지막 3번 테케는 질문게시판에 다른 분이 올려주신 부분을 손으로 그려봤다.  순서대로 N - 징검다리 수..

푼 날짜 : 2024.08.17푼 문제 : [16953] / A → B사용한 언어 : python  푼 방법 :너비 우선 탐색으로 접근하였다. 처음 풀었을 때 메모리 초과가 났다.아무래도 범위가 최대 10^9 이기 때문에 배열을 다 만든다고 하면... 그래서 생각한 방법이 dictionary다.불필요한 visited를 다 만들어 놓지 말고 필요한 값만 저장하기로 했다.사실 리스트에서 딕셔너리로 변경한 것 말고는 크게 BFS문제를 벗어날 정도의 난이도가 아니었기 때문에 코드는 전반적으로 비슷하다.   코드 :import sysfrom collections import dequeA, B = map(int, sys.stdin.readline().split())visited = {} # 딕셔너리로 만들기px =..

푼 날짜 : 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푼 문제 : [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, -..