문제널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.출력입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 ..
Algorithm
투 포인터(Two Pointers) 알고리즘은 정렬된 배열에서 효율적으로 특정 조건을 만족하는 값을 찾거나, 구간을 탐색하기 위해 사용되는 알고리즘입니다. 두 개의 포인터를 배열의 양 끝에 배치하거나 특정 위치에서 시작해, 이를 이동시키며 조건을 만족하는 값을 찾습니다. 정렬된 배열에서 가장 많이 사용됩니다.두 포인터를 사용하여 한 번의 탐색으로 문제를 해결하므로 시간 복잡도는 보통 O(N)입니다.이분 탐색처럼 중간 값을 탐색하지 않고, 포인터를 이동시켜 범위를 좁혀 나가는 방식입니다.투 포인터의 동작 원리배열의 양 끝에서 시작하거나, 시작 지점을 설정합니다.각 포인터의 값에 따라 조건을 확인합니다.조건에 따라 왼쪽 포인터를 오른쪽으로 이동하거나 오른쪽 포인터를 왼쪽으로 이동합니다.두 포인터가 교차하거나..
배열의 중간 요소를 반복적으로 확인하며 탐색 범위를 절반으로 줄여나갑니다. 시간 복잡도는 아래와 같습니다.작동 원리정렬된 데이터: 이분 탐색은 반드시 정렬된 데이터에서만 동작합니다.중간 값 선택: 배열의 중간 값을 선택합니다.조건 비교:찾는 값이 중간 값보다 작으면 왼쪽 절반을 탐색합니다.찾는 값이 중간 값보다 크면 오른쪽 절반을 탐색합니다.찾는 값이 중간 값과 같으면 탐색을 종료합니다.반복: 값을 찾거나 범위가 비워질 때까지 반복합니다.fun binarySearch(array: IntArray, target: Int): Int { var low = 0 var high = array.size - 1 while (low return mid // 값을 찾은 경우 arra..
https://www.acmicpc.net/problem/21930과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친 수(pinary number)라 한다. 이친 수는 다음의 성질을 만족한다.이친 수는 0으로 시작하지 않는다. 이친 수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친 수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친 수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 케이스를 몇 번 조사해서 점화식을 통해 풀어내야하는 DP 문제입니다..
복습하는 겸, 데이터 구조의 두 가지 종류인 선형과 비선형에 대해 정리를 진행 보겠습니다. 선형 구조- 데이터가 연속적이고 순차적으로 배치되는 구조입니다.- 각 요소는 하나의 선형 순서로 정렬되어 있으며, 각 요소는 이전 요소와 다음 요소와의 관계를 가집니다.- 종류에는 배열, 연결 리스트, 스택, 큐가 존재합니다.- 연속성 : 메모리에서 연속된 위치에 데이터가 저장됩니다 (특히 배열의 경우)- 접근 방식 : 각 요소는 단 하나의 직접 앞선 요소와 단 하나의 직접 뒤따른 요소를 가집니다. - 탐색 시간 : 특정 요소에 대한 접근 시간은 구조에 따라 다릅니다. 예를 들어, 배열은 O(1)로 접근할 수 있지만, 연결 리스트는 O(n)이 걸릴 수 있습니다.- 연결 리스트의 경우에는 동적 할당을 통해 메모리 ..
