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

※ 접근법 그래프가 주어지고 최소의 경우의 수를 구해야 하기에 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..

※ 접근법 1. 그래프가 주어지고 최소의 경우의 수를 구해야 하니 탐색을 떠올렸다. 2. 보드의 크기가 최대 100, 100 총 만 칸이니 dfs로 탐색할 시 RecursionError가 발생할 것 같아 bfs로 풀기로 했다. ※ 풀이 1. 미로에서 상하좌우로 이동하는데 빙판길이라고 생각했다. 2. 장애물("D"), 벽("그래프 범위를 벗어나기 전 가장자리")을 만나기전 까지 계속 미끄러진다. 3. 목표지점을 만났다면 바로 리턴해서 함수를 종료해준다. (바로 리턴해줄 수 있는 이유는 밑에 나온다.) 4. 벽이나 장애물을 만났는데 count > 0이면서 전에 방문했을 때보다 더 작은 횟수로 방문했을 시 큐에 추가해주고 visited값을 갱신해준다. (이렇게 최소 횟수의 방법만 큐에 들어오니 목표지점 도착했..

※ 접근법 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 _ ..

★ 접근 N의 최대 크기를 이십만으로 제한했기 때문에 모든 경우를 다 탐색할 경우 시간초과가 나올 것이라 생각했다. 그래서 그리디로 접근해보자고 생각을 했다. ★ 풀이 처음에는 모든 집에 대해서 안테나 거리들의 합이 최소일라면 가운데에 있으면 되는 것이 아닌가 했다. 너무 간단하다고 생각을 했고 코드도 너무 짧을 것 같아 확신이 없었다. 결국 다른 방법으로 해봤는데 틀렸다. 설마하고 첫 생각대로 해봤는데 통과돼서 허무했다. import sys input = sys.stdin.readline N = int(input()) house = list(map(int,input().split())) house.sort() print(house[(N-1) // 2])