SY DevLog

버블 정렬(Bubble Sort) 배열의 이웃한 두 요소의 대소관계를 비교하여 교환을 반복함으로써 이루어지는 정렬 시간복잡도 : O(N²) 배열의 크기가 N개 일 때, 이중 반복문을 사용하기 때문에 N의 제곱만큼의 시간 복잡도가 생긴다. [예제] 배열 arr의 요소가 5 2 3 8 1 4 6 일 때, 배열을 버블 정렬을 통해 오름차순으로 정렬하기 배열의 첫번째 요소부터 인접한 요소와 비교하기 시작한다. 세번째 요소(5)와 네번째 요소(8)는 비교 결과, 5보다 8이 더 크므로 교환하지 않는다. 첫 번째 반복문이 종료되면 배열의 가장 마지막에 8이 위치하게 되고, 마지막 요소는 정렬된 상태가 된다. 두번째는 첫 번째 요소부터 4번째 요소까지 인접한 요소들간의 비교가 이루어진다. 반복문이 종료되면 5번째 위..

투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘 단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다. 같은 방향으로 진행되는 투 포인터 알고리즘은 다른 포스팅에서 참고하면 된다. 투 포인터 알고리즘 - 같은 방향 투 포인터 알고리즘 - 1. 같은 방향 투 포인터 알고리즘 포인터 두 개를 이용하여 문제를 해결하는 방법 전체 배열에서 연속하는 부분합(구간합)이 특정값 M와 일치하는 경우의 수를 구할 때 사용 만약에 연속하는 부분합을 구하는 lotuslee.tistory.com 다른 방향으로 진행하는 알고리즘은, 1. 하나의 배열을 사용하는 방법과 2. 두 개의 배열을 사용하는 방법이 있다. 반복문 탈출조건이 약간 다르긴 ..

투 포인터 알고리즘 포인터 두 개를 이용하여 문제를 해결하는 방법 전체 배열에서 연속하는 부분합(구간합)이 특정값 M와 일치하는 경우의 수를 구할 때 사용 만약에 연속하는 부분합을 구하는 문제에서 투 포인터 알고리즘을 사용하지 않으면, 이중 반복문이 필요하기 때문에 시간복잡도가 O(N²) 가 된다. 그러나 투 포인터 알고리즘을 사용하면 O(N) 으로 줄일 수 있음 투 포인터 알고리즘은 크게 1. 두 포인터가 같은 방향으로 진행하는 방법 2. 두 포인터가 다른 방향으로 진행하는 방법 두 가지로 나눌 수 있다. 이번에는 우선 두 포인터가 같은 방향으로 진행하는 방법에 대해 다룰 것이다. 투 포인터 알고리즘 시간복잡도 : O(N) 투 포인터 알고리즘에서 필요한 프로퍼티 : - 부분합의 시작 인덱스를 가리키는 ..

한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘 주로 간선에 가중치가 주어질 때 사용한다. 단, 다익스트라 알고리즘은 가중치가 음수인 경우에는 적합하지 않다. (이유는 나중에 설명) 우선순위 큐를 이용하지 않고 구현하는 방법과 우선순위 큐를 이용하여 구현하는 방법이 있다. 우선순위 큐를 이용할 때 시간복잡도는 더 줄어든다. 시간 복잡도 : O(N²) 다익스트라 알고리즘을 구현할 때 필요한 몇 가지가 있다. - 시작점과 각 정점들간의 최단거리를 저장하는 이차원 배열 dist[start][end] : start 정점부터 end 정점까지의 최단거리 과정을 진행하면서 계속해서 최단거리를 업데이트하기 때문에 처음에 dist 배열의 모든 요소를 Integer.MAX_VALUE 값으로 초기화해준다. 그리고 새..

LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그 수열에서 가장 긴 증가하는 부분 수열을 구하는 알고리즘 (최장 증가 수열의 요소가 꼭 연속하지 않아도 됨) 1. 최장 증가 수열을 나열하는 문제 2. 최장 증가 수열의 길이를 구하라는 문제 보통 이 두가지 문제가 기본적이다. 여기서는 최장 증가 수열의 길이를 구하는 알고리즘을 볼 것이다. 1번 케이스의 경우, 수열 자체를 구하는 것이기 때문에 수열 요소의 추적이 별도로 필요하다. 시간 복잡도 : O(NlogN) 대략적인 알고리즘은 아래와 같다. 증가하는 수열을 저장하는 리스트가 필요하다. 리스트는 증가하는 수열을 저장하고 있기 때문에 계속 오름차순 상태를 유지하면서 갱신된다. 수열의 요소를..

소수찾기 알고리즘 2부터 시작해서 배수가 되는 수를 지워나가면 다 지우고 최종적으로 남은 수들이 소수가 된다. 소수가 아닌 수를 걸러내는 것이 체로 걸러내는 모양과 비슷해서 '에라토스테네스의 체' 라고 부름 시간 복잡도 : O(N*log(logN)) 알고리즘 : 1. 2부터 N까지 소수를 구하고자 하는 범위의 모든 수를 나열 2. 2를 제외한 2의 배수를 모두 지움 3. 3을 제외한 3의 배수를 모두 지움 4. 5를 제외한 5의 배수를 모두 지움 ... ?. n을 제외한 n의 배수를 모두 지움 (여기서 n은 n*n

그래프 관련하여 문제를 풀다보면(가령 DFS, BFS 문제와 같은) 그래프에서 노드간의 연결관계를 저장해야 하는 경우가 있다. 이럴 때 그래프의 연결관계를 표현하는 방법이 대표적으로 두 가지가 있다. 인접 행렬 인접 리스트 인접 행렬 그래프에 N개의 노드가 있으면, N x N 이차원 행렬을 만들어서 노드와 노드 사이의 간선 가중치를 담는 방식이다. 그래프가 무방향 그래프이고, i노드와 j노드가 연결되어 있으며 둘 사이의 간선의 가중치가 w인 경우, graph[i][j] = graph[j][i] = w 로 나타낼 수 있다. 만약 그래프에 가중치가 주어지지 않은 경우에는 두 노드가 연결되어 있으면 1, 연결되어 있지 않으면 0 으로 나타내어 0과 1로만으로 연결관계를 표현할 수 있다. 혹은 boolean형으..