코딩 테스트 수련의방98 정렬 알고리즘 시간 복잡도 버블정렬 위 그림처럼 하나씩 인덱스를 옮기면서 정렬 라운드를 진행하고 정렬이 완료될 때 까지 라운드를 계속 반복한다. 시간 복잡도 N^2 선택 정렬 위 그림처럼 가장 우선순위가 높은 요소를 하나씩 선택하여 가져와서 정렬이 완료된 영역을 하나씩 넓힌다. 시간 복잡도 N^2 삽입 정렬 일단 값을 순서대로 가져와서 위치를 찾아서 삽입한다. 선택 정렬과 비슷하다. 시간 복잡도: N^2 힙 정렬 힙 정렬은 이진 트리 형태로 최대힙 또는 최소힙을 만들어서 값을 정렬하는 방법이다. 정렬을 하는데 log n 의 시간이 걸리고 총 n개를 삽입하므로 -> 시간 복잡도: N log N 병합 정렬 위 그림처럼 모두 분해해서 병합을 하면서 정렬을 하는 방법이다. 병합은 log N 번 진행하고 정렬은 각 병합 단계마다 N번 진행.. 2023. 12. 10. 순열 오늘 LG CNS 코딩테스트를 쳤다. 3문제 중에 2문제는 테스트 케이스를 통과했고 1문제는 풀지 못했다. 아마도 문제가 전부 쉬워서 떨어질 것 같긴하다. 2번째 문제를 푸는데 dfs로 잘 안풀려서 고민하다가 마지막 20분 전에 순열로 풀 수 있는 방법이 떠올라서 열심히 했는데 시간 내에 완성하지 못하고 그냥 제출했다. 순열은 그냥 dfs나 브루트포스처럼 전부 계산하면 되긴 하지만 시간 제한 때문에 조금 알고리즘을 알아두면 좋을 것 같다. 밑에 다음 순열을 구하는 알고리즘은 오늘 시험과는 무관하지만 그냥 순열을 공부하다보니 자주 등장하길래 한번 정리해봤다. 백준 - 다음 순열 int i = 배열 마지막 인덱스, int j = 배열 마지막 인덱스 일때 1. i > 0 이면서 A[i] > A[i-1]를 만족.. 2023. 10. 7. LIS 알고리즘 DP로 풀면 간단하지만 시간 복잡도가 N^2이 되어서 N이 10000이 넘는 순간 복잡도가 100만이 넘어가면서 문제 제한 시간을 통과하지 못한다. DP로 문제를 해결하는 경우 아래와 같이 이중 for문으로 현재 위치보다 낮은 인덱스 중 가장 큰 dp에 1을 더해서 현재 dp와 비교 후 적용하는 방식으로 진행하면 된다. 백준 11053 if __name__ == '__main__': N = int(input()) lst = list(map(int, input().split())) dp = [1 for i in range(N)] for i in range(N): for j in range(i): if lst[i] > lst[j]: dp[i] = max(dp[i],dp[j]+1) print(max(dp)) .. 2023. 8. 9. 크루스칼 알고리즘 크루스칼(Kruskal) 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. 최소 신장 트리는 가중치가 있는 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소인 트리를 말합니다. 크루스칼 알고리즘의 동작은 다음과 같습니다: 그래프의 모든 간선을 가중치 순으로 오름차순으로 정렬합니다. 빈 신장 트리를 생성합니다. 가장 작은 가중치를 가진 간선부터 시작하여, 해당 간선의 양 끝점이 서로 다른 집합에 속해 있다면, 간선을 신장 트리에 추가합니다. 이를 위해 Union-Find 자료구조를 사용하여 각 정점이 어떤 집합에 속해 있는지 확인합니다. 모든 간선을 처리할 때까지 3단계를 반복합니다. 크루스칼 알고리즘은 간선의 가중치를 기준으로 처리하기 때문에 .. 2023. 6. 18. 다익스트라 알고리즘 다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다익스트라 알고리즘은 음의 가중치를 갖는 간선이 없는 경우에 최적의 결과를 보장합니다. 다익스트라 알고리즘의 개념과 시간 복잡도에 대해 자세히 설명드리겠습니다. 개념: 출발 정점으로부터 각 정점까지의 최단 거리를 저장하는 배열을 초기화합니다. 출발 정점의 최단 거리는 0이고, 다른 정점들의 최단 거리는 무한대로 설정합니다. 우선순위 큐를 사용하여 최단 거리가 가장 작은 정점을 선택하고, 해당 정점과 연결된 정점들의 최단 거리를 업데이트합니다. 업데이트된 거리가 더 작은 경우에만 갱신합니다. 모든 정점을 방문할 때까지 위의 과정을 반복하여 최단 거리를 찾습니다. 시간 복잡도: 다익스트라.. 2023. 6. 18. 투 포인터 알고리즘 투 포인터 알고리즘은 배열 또는 리스트에서 두 개의 포인터를 사용하여 원하는 결과를 찾는 알고리즘 기법입니다. 이 알고리즘은 주로 선형 시간(O(N))에 문제를 해결하는 효율적인 방법으로 사용됩니다. 특히, 정렬된 배열이나 리스트에서 특정한 조건을 만족하는 요소를 찾거나, 부분 배열 또는 부분 리스트를 찾는 데 유용합니다. 투 포인터 알고리즘은 일반적으로 다음과 같은 두 가지 포인터를 사용합니다: 시작 포인터(Left Pointer): 배열이나 리스트의 시작 위치를 가리킵니다. 끝 포인터(Right Pointer): 배열이나 리스트의 끝 위치를 가리킵니다. 이 두 포인터는 주로 다음과 같은 방식으로 조작됩니다: 시작 포인터와 끝 포인터가 서로 다른 요소를 가리키며, 이들을 이용하여 특정한 조건을 만족하는.. 2023. 6. 17. DP 알고리즘 DP(Dynamic Programming) 알고리즘은 큰 문제를 작은 부분 문제로 나누어 푸는 기법입니다. 작은 부분 문제들의 결과를 저장하고 활용하여 중복 계산을 피하면서 효율적으로 문제를 해결합니다. DP는 최적화 문제나 조합 문제를 해결하는 데에 주로 사용되며, 다음과 같은 특징을 가지고 있습니다. 장점: 1. 중복 계산을 피할 수 있습니다: 작은 부분 문제의 결과를 저장해두고 재사용함으로써 중복 계산을 피할 수 있습니다. 이로써 계산 시간을 줄이고 효율적인 알고리즘을 구현할 수 있습니다. 2. 문제를 작은 부분으로 나누어 해결할 수 있습니다: 큰 문제를 작은 부분 문제로 분할하여 해결하는 방식으로 문제를 더 이해하기 쉽게 만들 수 있습니다. 이로써 복잡한 문제를 단순화하고 해결할 수 있습니다. 3.. 2023. 6. 12. DFS 알고리즘 DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이 방향으로 그래프를 탐색하는 방법입니다. DFS는 스택(Stack) 또는 재귀 함수를 통해 구현할 수 있습니다. DFS의 동작 방식은 다음과 같습니다: 시작 노드를 방문하고, 해당 노드를 방문한 것으로 표시합니다. 현재 노드와 연결된 이웃 노드들 중에서 아직 방문하지 않은 노드를 선택합니다. 선택한 이웃 노드로 이동하여 재귀적으로 탐색합니다. 선택한 이웃 노드가 없을 때까지 이 과정을 반복합니다. 모든 이웃 노드를 방문한 후에는 이전 단계로 돌아가서 다음 이웃 노드를 선택하고 탐색을 진행합니다. 스택이 비어있을 때까지 위 과정을 반복합니다. DFS는 깊이를 우선으로 탐색하기 때문에, 그래프의 한 가지 경로를 가능한 멀리까지.. 2023. 6. 9. BFS 알고리즘 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색이란? 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. - Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우 - 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다. - 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색 너비 우선 .. 2023. 6. 2. 이전 1 2 3 4 ··· 11 다음
