SY DevLog

백준 1406번 : 에디터 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 스택을 이용하여 문제를 풀었다. [1차 시도] 처음에는 stack을 하나 만들어서 문자열의 문자들을 스택에 넣고, cursor 변수를 만들어서 명령어에 따라 커서의 위치를 갱신시켰다. 명령어 B(커서 전 문자 삭제)가 나오면, 현재 스택에 들어있는 문자의 개수 - cursor 만큼 스택에서 문자들을 pop을 한 다음에(그러면 스택의 맨 위에는 현재 커서 위치 바로 직전의 문자가 남아있게 된다.) 이 문자들을 임시 스택 tmp에 넣고, 제..

백준 18352번 : 특정 거리의 도시 찾기 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 다익스트라 알고리즘을 알면 쉽게 풀 수 있는 문제! 별로 어렵지 않게 쉽게 풀 수 있었다. 다익스트라 알고리즘 다익스트라(Dijkstra) 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘 주로 간선에 가중치가 주어질 때 사용한다. 단, 다익스트라 알고리즘은 가중치가 음수인 경우에는 적합하지 않다. (이유는 나중에 설 lotuslee.tist..

백준 2143번 : 두 배열의 합 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 먼저 배열 A의 부분합들을 리스트에 저장한다. 배열 B도 마찬가지로 부분합을 구해서 리스트에 저장한다. 그리고 두 개의 리스트를 가지고 투 포인터 알고리즘을 이용하여 문제를 풀었다. 투 포인터 알고리즘 - 다른 방향으로 해결하기 투 포인터 알고리즘 - 2. 다른 방향(배열 2개) 투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와..

투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘 단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다. 배열이 2개가 존재할 때, 배열 하나는 포인터가 왼쪽에서부터 시작하여 오른쪽으로 이동하고 다른 하나는 포인터가 오른쪽에서부터 시작하여 왼쪽으로 이동한다. 배열을 1개 사용할 때, start 포인터가 왼쪽에서 하나씩 증가하고 end 포인터가 오른쪽에서 하나씩 감소했던 것과 동일한 방식이다. 사실 배열이 한 개든, 두 개든 알고리즘 자체는 동일한데, 그냥 분리해서 이해하고자 따로 다뤘다. 투 포인터 알고리즘 - 다른 방향(배열 1개일 때) 투 포인터 알고리즘 - 2. 다른 방향(배열 1개) 투 포인터 알고리즘 - 다른 방..

퀵 정렬(Quick Sort) 알고리즘이 매우 빠르다라고 해서 붙여진 이름이다. 기준이 되는 피벗(pivot)을 설정하고, 그룹을 반복적으로 나누어서 정렬을 하는 알고리즘이다. 퀵 정렬은 피벗을 배열의 왼쪽 끝으로 설정하냐, 오른쪽 끝으로 설정하냐, 가운데로 설정하냐에 따라서 속도가 달라진다. 퀵 정렬의 알고리즘을 간단히 설명하면 이렇다. 배열의 왼쪽 끝 요소를 가리키는 커서를 pl, 오른쪽 끝 요소를 가리키는 커서를 pr 로 한다. 그리고 피벗을 가운데 값인 8로 한다고 하자. 피벗을 기준으로 왼쪽에 있는 구역을 A 구역, 오른쪽에 있는 구역을 B 구역이라고 할 때, A 구역에서는 pl을 오른쪽으로 이동시키면서 8보다 큰 값들을 찾아서 B 구역으로 넘기고, B 구역에서는 pr을 왼쪽으로 이동시키면서 8..

단순 삽입 정렬(Straight Insertion Sort) 선택한 요소를 그보다 앞쪽의 나열된 요소들 중, 알맞은 위치에 '삽입하는' 알고리즘 선택한 요소의 앞부분은 정렬이 완료된 상태이다. 삽입된 위치 이후의 요소들은 한칸씩 뒤로 밀려나게 된다. 알고리즘 : 배열의 두번째 요소부터 시작하여 하나씩 요소를 선택한다. 선택된 요소(arr[n])를 tmp 변수에 임시저장한다. * 변수 tmp에 임시저장하는 이유 : 왼쪽의 요소들을 한칸씩 오른쪽으로 미는 과정에서 선택된 요소(arr[n])가 있던 n번째 자리가 다른 값으로 채워지게 된다. 그렇게 되면 뒤에가서 arr[n]의 원래있던 값이 필요할 때 가져올 수 없으므로 tmp에 저장해둔다. 선택된 요소(tmp)보다 앞쪽에 있는 요소들(arr[0] ~ arr[..

단순 선택 정렬(Straight Selection Sort) 가장 작은 요소를 골라서 배열의 왼쪽부터 차례대로(오름차순 기준) 알맞은 위치로 옮겨서 정렬하는 방법 알고리즘 : 첫 번째 요소부터 차례대로 비교 기준(arr[n])이 된다.비교 기준의 다음번째 위치부터 마지막까지, 각각의 요소와 비교 기준이 되는 요소를 비교한다.더 작은 요소가 위치한 인덱스를 min 변수에 저장하면서 계속 min 변수를 갱신해나간다.마지막 위치의 요소까지 비교를 마치고 나면, 최종적으로 min 인덱스에 위치해 있는 요소(arr[min])와 비교 기준이 되는 요소(arr[n])를 서로 교환한다. 시간 복잡도 : O(N²) 버블 정렬, 삽입 정렬과 마찬가지로 시간복잡도가 크기 때문에 효율적인 정렬 알고리즘은 아니다. [예제] 배..

버블 정렬(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) 투 포인터 알고리즘에서 필요한 프로퍼티 : - 부분합의 시작 인덱스를 가리키는 ..