문제(link) DP로 해결하는 문제입니다. 풀이 방법 기본 조건 : 계단의 개수는 300이하의 자연수 arr = [0 for i in range(301)] dp = [0 for i in range(301)] 계단 오르기 규칙 1)1칸 or 2칸 오르기 가능 2)연속 3칸 밟기 불가능 3)마지막 칸 반드시 밟아야 함. → DP는 큰 문제를 작은 문제로 나누어 푸는 문제임. 어떤 큰 문제가 있을 때 그것의 가장 작은 문제부터 생각해야함. → 마지막 칸은 반드시 밟아야 하므로 다음과 같은 두 개의 경우의 수 존재함....
문제(link) 브루트포스 알고리즘으로 해결하는 문제입니다. 땅의 높이는 256블록을 초과할 수 없습니다. 층을 기준으로해서모든 경우의 수를 계산합니다. 층(target)과 같은 높이만큼 블록을 제거하거나 추가해서 (작업 최소 시간, 높이)를 구할 수 있습니다. 풀이 방법 [1] 0~256층까지 반복 [1-1] graph 좌표에 저장되어 있는 블록이 층 수보다 크거나 같으면 → 블록 제거, 인벤토리에 추가 [1-2] graph 좌표에 저장되어 있는 블록이 층 수보다 작으면 → 블록 추가, 인벤토리에서 제거 [1-3] 인벤토리 블록의 범위 안에서 작업했다면 [1-3-1] 최소 시간이라면 Update (작업 최소시간, 높이)...
[programmers] 순위 (문제 링크) 이 문제는 그래프로 분류되어 있습니다. 어떻게 그래프로 접근해야하는지 아이디어가 생각나지 않아서 어려웠던 문제입니다. 구글링을 해봤을 때 플로이드 와샬(Floyd-Warshall) 알고리즘을 이용해서 구현을 하신 답안이 많았지만 DFS로 구현했습니다. 플로이드 와샬의 경우 각 정점에서 다른 모든 정점까지의 최단경로를 구할 수 있는 알고리즘인데 이보다는 DFS가 효율적이라고 생각했습니다. 실제로 플로이드 와샬의 시간 복잡도는 O(n^3)입니다. 풀이 방법 n = 5 results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] results의 정보를 가지고 확실한 순위를 알 수 있는 노드의 수를 찾아내는 문제입니다....
[백준] 2667번 단지 번호 붙이기 (문제 링크) 풀이 방법 graph에서 연결 요소(connected component)의 수를 찾고 연결 요소 안의 node 수를 카운트하는 문제입니다. deque로 BFS를 구현해서 해결했습니다. [0] graph와 (x,y) 좌표의 방문 여부를 표시하는 visited (list)를 생성합니다. [1] graph 전체를 순회하면서 graph(x,y) 값이 1인 경우에 bfs 함수를 실행합니다. [1-1] (x,y)를 push한 queue를 생성합니다. [1-2] queue에서 원소를 pop 합니다. [1-3] pop한 원소를 기준값으로 해서 상하좌우를 살핍니다. 만약 값이 1이고 아직 방문하지 않았다면 push 하고, 방문 표시합니다....
[백준] 2178번 미로탐색 (문제 링크) 풀이 방법 (1,1) ~ (N,M) 까지의 최단 경로를 구하는 문제이므로 BFS를 활용해서 구현합니다. 이 문제에서 BFS를 활용하여 구현하는 이유는 다음과 같습니다. Code (python) from collections import deque def bfs(root): queue = deque([root]) #큐를 생성해서 root push while queue: x,y = queue.popleft() #pop - 기본 좌표가 나옴 #상하좌우 이동 for i in range(4): nx = x + dx[i] ny = y + dy[i] #좌표 밖을 벗어나면 넘어감 if nx < 0 or ny < 0 or nx >= N or ny >= M: continue if graph[nx][ny] == 1: #만약 이동한 좌표의 값이 1이라면 graph[nx][ny] = graph[x][y] + 1 #이동한 좌표의 값에 기본 좌표 값에 1을 더함 queue....
[백준] 1260번 DFS와 BFS (문제 링크) 기본적인 그래프 탐색 문제 입니다. DFS는 stack을 활용해서 구현하고, BFS는 queue를 활용해 구현합니다. 방문할 수 있는 정점이 여러 개인 경우 숫자가 적은 것을 먼저 방문하라는 조건을 고려해야 합니다! 풀이 방법 Graph <input> 4 5 1 1 2 1 3 1 4 2 4 3 4 위의 testcase로 만들어진 그래프의 모양은 다음과 같습니다. DFS 방식으로 그래프 탐색 stack 자료구조에서 pop을 하면 나중에 들어온 것이 먼저 나옵니다....