친절한 도현씨 친절한 도현씨

※ 접근법 문제에서 시작 지점이 주어지고 그 지점에서 최단 거리를 구하는 문제였기 때문에 다익스트라 알고리즘을 떠올렸고 노드의 개수가 최대 오만 개로 많았기 때문에 우선순위 큐를 이용한 다익스트라 알고리즘 문제로 풀어야겠다고 생각했다. ※ 풀이 1. 풀이법은 우선순위 큐를 이용한 다익스트라 구현과 너무 똑같기 때문에 주석으로 코드 한줄 한줄이 무엇을 의미하는지 달아놓겠습니다. (한 가지 틀린점이 있다면 문제에서 양방향이라고 말을 해줬기 때문에 입력받을 때 양방향으로 받았습니다.) import sys, heapq input = sys.stdin.readline n, m = map(int,input().split()) INF = float("inf") # 무한대 상수 선언 graph = [[] for _ i..

※ 접근법 처음에는 데이터 갯수가 너무 많아서 그리디이지 않을까 떠올렸다. 근데 그리디라고 하기에는 탐욕적인 방법이 떠오르지 않았다. 그래서 힙을 이용하여 heappop을 통해 최솟값을 계속 꺼내서 값을 구할까도 생각을 해봤지만 결국 구해나가는 방법이 그리디적으로 생각을 해야했고 발상이 떠오르지 않았다. 그래서 다른 알고리즘이 없을까 하다가 이분탐색을 떠올렸다. ※ 풀이 1. 각 캐릭터의 레벨을 입력 받으면서 최소 레벨과, 최대 레벨을 구해준다. (최종적으로 코드에서는 최대 레벨을 사용하지 않았지만 처음에는 혹시 모르니 구해놨다.) 2. 최소 레벨을 맞추기 위해 높은 레벨이 낮아질 필요는 없으니 데이터를 올림차순으로 정렬시켰다. 3. 이분탐색 로직에서는 mid값보다 커지는 구간이 나오면 반복문을 종료시켰..

※ 접근법 그래프가 주어지고 최소의 경우의 수를 구해야 하기에 bfs를 떠올렸다. n,m의 크기를 보고 그람을 사용하고 공주를 찾는 경우를 구하는 함수와 그람을 사용하지 않고 공주를 찾는 경우의 수를 동시에 구해야 시간초과가 나오지 않을 것이라 생각했다. ※ 풀이 1. 0,0부터 시작해 bfs를 시작한다. 2. 방문하지 않았고 배열 범위 안에 있는 조건을 만족하고 그 때 빈 공간이라면 큐에 추가한다. 3. 다음 좌표가 그람이 있는 곳이었다면 그람과 공주 사이의 좌표 거리를 계산한다. ※ 정답코드 from collections import deque n,m,t = map(int,input().split()) data = [list(map(int,input().split())) for _ in range(n..

※ 접근법 N,M의 크기가 크지 않아 완전 탐색을 해야겠다고 생각했고 CCTV 감시 방향이 4방향인 것을 보고 재귀를 이용해 백트래킹 해야겠다고 생각했다. ※ 풀이 1. 좌표 0,0부터 차례차례 하나씩 탐색을 해나간다. 2. 현재 탐색중인 좌표에 CCTV가 있다면 감시를 하고 감시한곳은 1을 빼준다. 3. 1번과 2번을 반복하다가 r의 크기가 N과 같아졌다면 사각지대의 개수를 구해주고 백트래킹을 한다. 4. 다음 감시 방향으로 넘어가기 전에 감시했던 방향을 +1을 해줘 감시를 풀어준다. N,M = map(int,input().split()) data = [list(map(int,input().split())) for _ in range(N)] min_num = float("inf") def one_cct..

※ 접근 처음에 N의 개수를 보고 완전탐색을 해도 되겠구나 싶었고 문제를 읽고 큐를 사용했다. 하지만 인덱스 움직이는 것에 제한이 있었고 큐를 사용하면 안된다는 것을 느껴 덱으로 생각을 전환해 접근했다. ※ 풀이 입력을 받을 때 수열로 입력받고 하나씩 꺼내어 인덱스는 +1 해서 정답 리스트에 저장하고 종이에 나온 숫자만큼 로테이트 함수를 이용해 돌려준다. import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque(enumerate(map(int,input().split()))) ans = [] while q: idx,paper = q.popleft() ans.append(idx+1) if pap..

※ 접근법 먼저 입력 제한이 n,m의 크기와 보드판의 크기가 크지 않았기 때문에 그래프 탐색을 제일 먼저 떠올렸고 주사위를 한 번 굴렸을 때 주사위 숫자 안에 있는 것들을 먼저 방문해야 하니 가까운 노드부터 먼저 탐색하는 bfs로 풀어보기로 했다. ※ 풀이 1. 사다리와 뱀에는 차이가 있지만 결국 시작지점과 끝지점이 있는 포탈이라고 생각했다. 2. visited의 크기를 108로 넉넉하게 설정해줬다. 보드판은 100까지 밖에 없지만 끝나는 조건이 100을 넘어가면이기 때문에 IndexError를 일으키지 않기 위해서다. 3. 시작지점부터 주사위를 굴리고 주사위를 굴려 이동한 곳에 사디리 또는 뱀이 있다면 거기로 이동하고 원래 있던 곳 + 1을 해준다. 4. 이동한 곳이 100보다 크거나 같았다면 바로 리..

※ 첫 접근 모든 경우의 수를 알아야하는데 문제 입력 부분을 봤을 때 n이 최대 삼십만개인 것을 보고 완전 탐색은 아니겠구나 생각했다. 이분 탐색을 떠올렸지만 정렬된 구간은 있지만 mid를 재설정 하는 과정에서 시간초과가 나서 패스했다. 다음으로 그리디 알고리즘을 떠올렸다. 그리디 알고리즘으로 반복 한 번에 풀어야만 시간초과가 나지 않을 것만 같았다. ※ 풀이 모든 유치원생이 혼자 있어야만 최소 비용일 수 있다. 1 ㅣ 3 ㅣ 5 ㅣ 6 ㅣ10 일 때 최소가 된다 n-1개의 막대기가 존재한다. 여기서 저 사이의 막대기를 치우면 한 조에 두명이상이 되고 차이만큼 비용이 증가하기 시작한다. 각 차이는 (2,2,1,4)이다. 여기서 우리는 k개의 조로 나누어야 하기에 k-1개의 막대기가 남아있어야 한다. 그렇..

※ 접근법 n의 범위가 크지 않았기 때문에 모든 경우의 수를 백트래킹을 활용하여 큰 수를 구해야겠다고 생각했다. 4가지 모양을 가지고 각 좌표에 대해서 해당 모양이 될 수 있는지 없는지를 범위와, 방문 여부로 판단했다. ※ 풀이 1. 0,0부터 visited,0을 가지고 dfs(solve함수)를 시작한다. 2. y좌표를 1씩 이동했고 y좌표가 배열의 범위를 벗어났다면 x += 1, y= 0을 해줬다. 3. 최댓값을 어느 시점에서 걸어서 백트래킹을 걸까(return을 할까) 했었는데 x가 배열의 범위를 벗어났을때는 이미 탐색을 다 한 것이니 x == n일때 해주면 됐다. n,m = map(int,input().split()) data = [list(map(int,input().split())) for _ ..