본문 바로가기

알고리즘22

투 포인터 (+ 백준 2003) 오늘은 투 포인터라는 개념을 알아보겠습니다! 투 포인터는 알고리즘.. 이라기보다는 개념이라고 하는게 더 맞는 표현인 것 같아요. 1차원 배열을 두고 start, end 라는 두 개의 인덱스를 사용해서 답을 구하기 때문에 Two Pointer (투 포인터) 라는 이름이 붙었습니다. 사실상 두 개의 인덱스 (포인터) 를 사용한다는 것 외에 특별히 설명할 수 있는게 없어서 오늘은 백준 2003번: 수들의 합 2 를 예시로 투 포인터를 설명해보려 합니다. 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤.. 2021. 2. 25.
Linked List (링크드리스트) 링크드 리스트는 이름과 같이 하나하나의 요소가 연결되어 리스트를 이루는 구조입니다. 그리고 보통 싱글 링크드 리스트 (Single Linked List)와 더블 링크드 리스트 (Double Linked List)로 나뉩니다. 링크드 리스트를 사용하게 되면, 새로운 요소를 넣을 때 그 요소와 원래의 요소들을 연결하기 때문에 미리 데이터 공간을 할당할 필요가 없어집니다. 하지만 연결을 위한 별도 데이터 공간이 필요하기 때문에 저장공간 효율이 높지는 않습니다. 중간 데이터를 삭제할 때도 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하죠. 하지만 만약 데이터를 얼마나 집어넣을지 모르는 상태라면 링크드리스트를 사용해보는 게 좋습니다. 애초에 많은 데이터 공간을 할당하고 시작하는 것보다 리스트에 추가해.. 2021. 2. 24.
PriorityQueue (우선순위 큐) Priority Queue (우선순위 큐)는 말 그대로 사용자가 지정한 조건에 따라 우선순위가 정해집니다. 일반적인 Queue는 단지 데이터가 들어오는 순서에 따라 FIFO(First In First Out) 구조를 따르게 되는데, Priority Queue는 우선순위가 높은 데이터부터 pop됩니다. PriorityQueue는 우선순위에 따라 Heap(힙) 자료구조로 데이터를 저장하게 되기 때문에 삽입과 삭제의 시간복잡도는 O(log n)으로 매우 빠른 시간을 자랑합니다. 제가 이 Priority Queue (우선순위 큐)를 Swift로 직접 구현하기 위해 이전 게시물에서 Heap(힙) 자료구조를 공부했었습니다!! Queue도.. Stack도.. PriorityQueue도 없는 Swift는... 사용하려.. 2021. 2. 19.
Heap 힙 자료구조 ㅎ..제가 말이죠.. 요즘 Swift로 알고리즘을 풀어보려고 연습중인데, 거의 없는게 없는 Java로 알고리즘 문제를 풀다가 Swift로 풀려고 하니 없는게 너어무 많더라구요??? Stack도 Queue도 PriorityQueue도?!? 구글링 해보니 직접구현해야하는 거 같더라구요??ㅋㅋㅋㅋㅋ 예. 근데 이것도 사실 이 게시물 작성했을 당시에 iOS / Swift 공부를 한지 겨우 2개월밖에 안됐을 때라 그랬나봐용.. stack 은 그냥 배열에서 removeLast( ) 사용해서 stack처럼 사용하면 되구.. queue는 그냥 배열에서 removeFirst( ), removeLast( ) 사용해서 queue처럼 사용하면 되구.. PriorityQueue도 .sorted(by: { Bool }) 이런식으.. 2021. 2. 17.
Insertion Sort (삽입 정렬) Insertion Sort (삽입 정렬)은 이름 그대로 적절한 위치에 삽입을 하여 정렬을 하는 알고리즘입니다. 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 하나씩 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성합니다. 요소를 하나씩 비교해나가기 때문에 시간 복잡도는 O(n^2)를 가집니다. 알고리즘 구현 순서는 다음과 같습니다. 비교는 배열의 두 번째 인덱스부터 시작하여 자신의 앞쪽에 있는 요소들과 비교합니다. 비교했을 때, 앞의 요소가 자신보다 크다면 swap 합니다. 비교했을 때, 앞의 요소가 자신보다 작다면 비교를 멈춥니다. 다음 인덱스의 요소부터 다시 2~4를 반복합니다. 아래는 Swift로 구현한 Insertion Sort 입니다. var arr: [Int] = [5,2,4,1.. 2021. 2. 15.
Quick Sort (퀵 소트) Quick Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 이름만큼 평균적으로 매우 빠른 수행 속도를 자랑하며 시간복잡도 O(n log n)을 가지고, 추가 메모리 공간을 필요로 하지 않기 때문에 O(log n)만큼의 메모리를 필요로 합니다. Merge Sort와 달리 Quick Sort는 비균등 분할을 합니다. 리스트 안에 있는 한 요소를 선택하는데, 이때 이 원소를 pivot이라 합니다. 입력 배열을 pivot을 기준으로 비균등하게 2개의 부분 배열로 분할합니다. 이 때, pivot의 왼쪽은 pivot보다 작은 요소들로, pivot의 오른쪽은 pivot보다 큰 요소로 이루어지게 됩니다. (divide) 이렇게 분할한 부분 배열을 정렬합니다. 부분 배열의 크기가.. 2021. 2. 12.
Merge Sort (병합 정렬) Merge Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 시간복잡도 O(n^2)을 가지는 일반적인 정렬과 달리 Merge Sort의 시간 복잡도는 O(nlog_2 n) 이 됩니다. 이등분씩 나누는 것을 반복해서 최소 단위까지 분할합니다. (divide) 분할한 부분 리스트를 정렬합니다. (conquer) 정렬된 부분 리스트들을 하나의 리스트에 병합합니다. (combine) 다음은 swift 언어로 구현한 divide, merge 메서드 입니다. func divide(_ start: Int,_ end: Int) { if start >= end { return } let mid = (start + end) / 2 divide(start, mid) divide(mid.. 2021. 2. 11.
[플로이드와샬] 백준 11404번 플로이드 (Java) 백준 11404 : https://www.acmicpc.net/problem/11404 정말 기본 플로이드 와샬 알고리즘 그대로 사용하는 문제이다. 그래서 플로이드 와샬 알고리즘을 공부하면서 풀어보았다. 플로이드 와샬은 다대다 최단거리를 계산할 때 사용한다. 그만큼 속도가 느리지만, 모든 노드 사이의 최단 거리를 알아야 하는 문제에 사용한다. 그럼 어떻게 푸는지 한 번 살펴보자. 기본 세팅 N : 노드 개수 dp[N][N] : 모든 노드 사이의 최단 거리를 저장하는 배열 INF = 최대 거리(나는 N*maxlength로 두었다.) dp 초기화 자기 자신으로 가는 거리는 0 그대로 두고, 나머지는 INF로 설정한다. 예시) 간선 입력 간선을 입력받을 때, 기존 dp값과의 min값으로 저장합니다. 플로이드 .. 2020. 8. 28.
프로그래머스 - 불량 사용자 (Java 풀이) 출처 : 프로그래머스 - 2019 카카오 개발자 겨울 인턴십 코딩테스트 문제 [ 문제 설명 ] 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다. 무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다. 예를 들어, .. 2020. 5. 21.
프로그래머스 - 튜플 (Java풀이) 출처 : 프로그래머스 - 2019 카카오 개발자 겨울 인턴십 코딩테스트 문제 [ 문제 설명 ] 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, .. 2020. 5. 4.

티스토리툴바