백준알고리즘

<풀이를 위한 알고리즘>1\. X를 무조건 거쳐야 한다. 이때 S에서 출발하여 E에 도착할 때 최소 시간을 구하는 것임.\-> BFS를 사용해야 한다는 것을 알 수 있었다, 추가로 최소 비용을 어떻게 구할까 했는데 내 생각으론 한번의 BFS론 시간 초과가 날 것

백준 16954번 가장 먼저 든 생각은 DFS나 BFS를 이용하여 하는 것 같다는 생각이었고 저번엔 BFS를 써서 이번엔 DFS를 사용하였다. 두 번째로 고려한 것은 이동방향이 제자리 상하좌우 대각선인 점을 고려하여 DFS를 진행해야 한다는 점이다. 세 번째론 방

백준16946번처음에는 BFS로 바탕으로 1의 위치를 입력때 큐에 담은다음에 1의 위치를 기준으로 BFS를 하는 방식으로 구현하였다.\->테스트 케이스는 맞았는데 시간초과가 나왔다.두 번째로 생각해 본 것은 1주변에 있는 0의 집합(그룹)안의 개수를 더하고 1을 더하면

백준 2138번주어진 숫자와 정답 숫자를 비교하여 가장 먼저 차이가 나는 곳 부터 마지막으로 차이가 나는 곳을 범위로 해서 스위치를 작동하면 최소로 해서 구할 수 있지 않을 까 생각을 해봤는데 만약에 답이 나오지 않을 경우엔 별다른 기준이 없다면 시간 초과에 걸릴 것이

백준 2493번탑마다 반복문을 돌며 처음으로 자신보다 높은 것이 있는지 찾는 방법이 있는데 이러면 시간복잡도가 O(n^2)이 나올 것 이므로 다른 방법을 찾기로 함.다음으로 해본 생각은 어차피 6 2 3 9 2 5의 형태일 경우 9이후부턴 9가 제일 높으므로 다른 탑에

백준 13144번처음엔 입력을 받을 때 특정 값이 반복되며 그 값에 해당하는 인덱스를 각각 벡터에 저장해주어 나중에 범위를 구하면 된다고 생각하였다. 이 방법으로 구현하니까 포함이 되지 않는 경우가 존재하여 답이 안나왔다.(이렇게 푸는 방법이 있을 수도 있지만 나는 생

백준 3109번가장먼저 생각한 것은 bfs나 dfs를 써야할 것 같다는 것 이었다.문제의 조건에서 파이프끼리 같은 칸에 있으면 안된다는 조건이 있는데 이것이 이미 방문한 곳은 못한다는 의미라고 생각했다.만약 bfs나 dfs를 쓰려면 3가지 이동경로를 모두 탐색하며 최대

매우 비슷한 유형의 문제\->이 문제 유형과 거의 흡사하여 금방 해결할 수 있었다.백준22866번전에 푼 문제에서 이번엔 양쪽을 고려하여 접근하면 될거라고 생각했고 그러기 위해 인덱스가 1에서 시작하는 경우와 N에서 시작하는 경우에 대해서 둘다 고려하고 그 경우 볼 수

백준 1167번처음에는 플루이드-워셜 알고리즘으로 하면 가능할 거라 생각했는데 정점이 최대 100000이 되므로 이차 배열로 나타내면 메모리 초과가 발생해 다른 방법을 찾게 되었다.dfs를 이용하여 방문한 노드는 재방문을 하지 않고 cost를 합해가며 최대 값을 찾고

백준 1522번처음엔 dfs나 bfs를 이용하여 a와 b를 스왑한 경우에 대하여 횟수를 측정하는 방식으로 접근했다. b가 a와 스왑되는 위치에 대하여 브루트 포스를 진행하며 동시에 dfs를 해야하니 어디서 멈출지도 애매하고 시간 초과가 날 것이라는 생각이 들었다.그래서

분리집합이란 서로 중복되지 않는 집합이며 그 집합이 전체 집합 U를 구성하고 있는 집합을 의미한다.만약 어떤 집합이 그래프로 이루어져 있고 우리가 찾고자 하는 대상이 그 안에 속해 있는지 확인 하기위해 여러 탐색을 써서 찾을 수 있을 것이다. 그러나 매번 탐색을 하여

이미 비행기가 연결된 게이트는 더 이상 비행기가 접근할 수 없다. 만약 1번 게이트부터 시작해서 올라간다면 비행기가 있는지 없는지 보고 만약 있다면 또 옆으로 옮길 수 있는지 여부를 봐야하는데 이렇게 되면 시간이 너무 많이 들 것 같았다.그래서 최대 게이트에 대해 내림

백준 11812번백준 13116번 이와 비슷한 문제가 존재하는데 여기서는 자식이 최대 2인 경우만 다루는 문제였다.저 문제에서 아이디어를 차용하여 두 노드 중 현재 크기가 더 큰 노드에 대하여 자신의 부모를 가리키게 하는 방식으로 하나하나 올라가다가 같은 부모를 가리키

1.그래프 탐색을 이용하여 출발 도시부터 도착도시까지의 최소값을 구해야 함. 그 과정에서의 경로는 어떻게 구할 것인가를 생각해봤음.처음엔 dfs로 구현하여 만약 도착도시에 도달했을 때 그 경로가 최소일 경우 돌아오며 그 경로를 스택에 담으려 하였는데 dfs라 그런지 최

100자리 수에 대하여 나타내야 하므로 그냥 반복문을 돌리기면 무조건 시간 초과나 나올 것 이라고 생각했다. 진짜 수에 대해서 다루는게 아니라 한자리씩 다룬다고 생각하면 100자리이므로 더 쉽게 문제에 접근하였다.첫번째자리에 1-9까지의 수로 각각 시작하여 +- 1이

백준 1086번숫자가 길기 때문에 직접 연산할 수는 없고 모든 순열에 관하여 계산해야 하므로 O(N!)가 걸리기에 다 구하는 방법말고 다른 방법으로 접근해야 했다.비트마스킹을 이용하여 순열을 표시하면 좋을 것 같다는 생각이 들었다. 추가로 N개의 수로 만든 수의 나머지

counter clock wise(시계 반대 방향)세 점이 있을 때 방향이 시계방향인지, 반시계 방향인지, 직선인지 알 수 있는 알고리즘이다. 벡터의 외적을 생각하면 쉽게 이해할 수 있다.오른손 법칙을 이용하여 시계 반대방향엔 양의 법선이 시계 방향엔 법선이 음수로 나

백준 2263번주어진 inorder과 postorder를 고려해 봤을 때 postorder을 통해서 루트를 얻어올 수 있고 inorder를 통하여 미리 구한 루트를 기준으로 왼쪽 서브트리 오른쪽 서브트리를 구할 수 있다는 것을 알아냈다.이를 구현하기 위해 postord

문자열을 탐색할 때 사용하는 알고리즘이다.핵심 아이디어는 찾고자 하는 문자열의 접두사(prefix)와 접미사(suffix)에 대하여 일치하는 개수(길이)를 배열로 저장한 후에 탐색할 때 사용하는 것이다.예를 들어 찾고자 하는 문자열 p가 ababc 일 경우 i = 0,