Algorithm

문제 풀이: 이 문항은 dp문항이다. 처음에 input을 arr list를 만들어 따로 받았는데, 그럴 필요가 없었다. arr로 따로 만들게 된 이유는, 이때까지 풀었던 몇 가지 dp 문항들이 min(dp[i-1] + arr[i],dp[i]) 이런식으로 자꾸 비교하면서 들어오길래 이상하게 생각없이 arr를 무작정 만들었었다. 그런데 해결이 안되니, 근본적인 이유는, 그냥 R일 때 G일 때 B일 때를 모두.. dp로 해보면 된다는 점이었음. '모두'라 함은 작을 수 있는 가능성이 있는 경우를 뜻함. 그래서, 시작이 무엇이니에 따라서 case가 3가지가 나오고 그때마다 그냥 가장 적게 드는 값을 탐색하다보면 답이 나온다. 코드: N = int(input()) dp = [] for _ in range(N): ..

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘이다. 1)선택 정렬(Selection Sort) 가장 원시적인 방법'이다. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬이다. 2)삽입 정렬(Insertion Sort) 특정한 데이터를 적절한 위치에 '삽입'하는 정렬이다. 삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서..

미로 찾기 문항은 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다. Why? : BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. 그러므로 (1,1)지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. from collections import deque # N, M을 공백으로 구분하여 입력받기 n, m = map(int,input().split()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(map(int,input()))) # 이동할 네 방향 정의(상,하,좌,우) dx = [-..

DFS/BFS 는 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘이다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(Push): 데이터를 삽입한다. 삭제(Pop): 데이터를 삭제한다. 스택 (~=박스 쌓기) 스택은 선입후출(First In Last Out)구조 또는 후입선출(Last In ..

알고리즘 분류) 이분탐색, 매개 변수 탐색 *매개 변수 탐색(Parametric Search): 이분 탐색을 사용하여 조건을 만족하는 최대값을 구하는 방법이다. *Parametric Search의 Detail은 https://stopmin.tistory.com/31 여기 정리해 놨음. Solution) 이진탐색의 정의에 맞게 일단 비교해야 하는 값들을 sorted해서 House에 정리해줬다. start, end 포인트를 1과 가장 멀리 떨어져있는 집 사이의 거리로 설정했다. 그리고 이제 while (start count += 1로 간다. 그리고 if count 가 C보다 커질 경우에는 (start+end)값이 작기 때문이기에 start point를 mid + 1로 바꿔준다. 그리고 result = mid..

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 이 풀이의 아이디어는 '현재 상황에서 조건을 만족할 수 있는가?'를 확인한 뒤 조건의 만족 여부('Yes' or 'No)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 이 범위를 좁힐 때에 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀나간다.