투 포인터 - BOJ - 1806 부분합
2023. 3. 19. 20:59
Algorithm/Two Pointer
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 접근 앞서 해보았던 투 포인터 유형의 대표적인 문제인 부분합 / 구간 찾기 문제이다. 문제를 상세히 읽어보면 부분합이 S이상이 되면 되므로 $S_{cur} \geq S_{target}$ 를 만족하게 되면 left를 하나씩 올리면서 위 구간합이 만족하는지를 검사하며 구간을 줄여나가면 된다. 만약 $S_{cur} < S_{target}$ 라면 right를 움직여서 다음 요소를..
투 포인터의 원리와 예제
2023. 3. 19. 16:33
Algorithm/Two Pointer
투 포인터(Two Pointers) 투 포인터는 이름 그대로 두 개의 포인터를 사용하여 배열에서 원하는 결과를 얻는 방법이다. 다중 반복문이 사용되어야 하는 경우에서 해당 방법론을 사용할 수 있다면 좀 더 효율적으로 문제를 풀 수 있다. 포인터의 배치 위치는 일반적으로 아래와 같다. 동일한 방향에서 시작하는 경우, 첫 번째 원소에 둘 다 배치 서로 다른 방향에서 시작하는 경우, 첫 번째 원소와 마지막 원소에 배치 투 포인터의 활용 투 포인터는 배열에서 여러번의 다중 반복문이 사용되어야 할 경우에 효율적이다. 예시로는 구간합 찾기 문제가 있다. 아래와 같은 배열에서 구간합이 9인 구간을 찾아주세요 1 2 5 3 7 2 4 3 2 해당 문제를 나이브하게 다중 루프를 사용할 경우 시작 구간 i와 구간합을 계산..
힙(우선순위 큐)의 활용 - 프로그래머스 디스크 컨트롤러
2023. 3. 19. 16:00
Algorithm/DataStructure
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 우선순위 큐 유형의 문제인데 우선순위가 명확히 제시되어 있지 않고, 문제를 확인함으로서 직접 우선순위를 찾아야 하는 문제이다. 해당 우선순위 큐에서 선정해야할 우선순위는 현재 시간에 들어온 작업들 중 작업에 걸리는 시간이다. 즉 현재 시간에 들어온 요청들 중 가장 짧은 작업 시간을 가지는 데이터가 먼저 빠져나가게 된다. 대신 데이터가 요청시간 순서대로 들어오는걸 문제에서 보장하지 ..
힙(우선순위 큐)의 활용 - BOJ 24174 알고리즘 수업 - 힙 정렬 2
2023. 3. 19. 15:47
Algorithm/DataStructure
문제 https://www.acmicpc.net/problem/24174 24174번: 알고리즘 수업 - 힙 정렬 2 2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] A[3]) -> 5 4 3 2 1(heapify(A, www.acmicpc.net 문제 접근 힙 정렬을 구현 한 후, swap 함수의 호출 카운트를 세어 그보다 작다면 -1, 같다면 해당 스왑으로 인해 바뀐 배열을 그대로 출력하면 된다. 차이점은 힙 정렬을 보..
LinkedList/Queue의 활용 - 프로그래머스 프린터
2023. 3. 17. 17:48
DataStructure/List
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 초기에 저장되어 있는 위치를 기준으로 내가 원하는 문서를 잡아야 한다. 따라서 초기 상태의 인덱스와 해당 데이터의 우선순위를 하나의 클래스로 묶어 관리하면 편리하다. 이후에는 리스트를 순회하면서 맨 처음에 있는 요소보다 더 큰 우선순위를 가진 요소가 존재한다면 뒷쪽으로 보내고 그렇지 않다면 poll 한다. 이때 인덱스가 내가 원하는 인덱스인지 검사하면 끝이..
LinkedList/Queue의 활용 - BOJ 1158 요세푸스 문제
2023. 3. 17. 16:58
DataStructure/List
문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 접근 원형으로 돌아가 K만큼 떨어진 사람을 계속해서 빼내어 모든 인원이 빠질 때 까지 반복한다. 이때 빼낸 사람들을 순차적으로 출력한 것이 요세푸스 순열이다. 해당 문제는 Queue 문제이지만, LinkedList로도 풀 수 있는 문제이다. 애초에 Java에서 Queue의 구현체로 LinkedList를 사용했으니 사용하는 메서드만 다르지 동작을 동일하게 할 수 있다. 답안 코드 import java.io.BufferedReader; import java.io.IOExceptio..
이분 탐색의 원리와 구현 방법
2023. 3. 16. 21:14
Algorithm/BinarySearch
이분 탐색이란? 이분 탐색(Binary Search)는 탐색 기법 중 하나로, 어떠한 데이터 리스트 L이 존재할 때 어떤 두 점을 지정하여 그 중간값을 보고 찾는 데이터와 비교하여 각 점의 위치를 옮기는 방법이다. 해방 방법을 사용하면 리스트의 길이가 N 일때, 매 번 2배씩 탐색 범위가 좁아지기 때문에 최종적으로 $O(logN)$이 된다. 일반적으로 탐색에 소요되는 시간이 $O(N)$임을 생각하면 효율적인 방법이다. 시간적으로 더 효율적인 대신에 하나의 제한 조건이 있다. 바로 데이터 리스트가 정렬되어 있어야 한다는 것이다. 이는 이진 탐색이 찾는 데이터와 현재 데이터를 비교하여 대소 유무에 따라 다음 위치를 결정하는 것이기 때문이다. 예시 문제 예시 문제로 백준의 숫자 카드가 있다. https://w..
HashMap의 원리와 설명
2023. 3. 16. 16:48
DataStructure/Hash, map, set
기본적인 용어의 정의 Map부터 알아보자. 기본적으로 Map은 어떠한 데이터를 저장할 때 key와 value 쌍을 저장하는 자료구조로, 데이터를 Map 내부에서 탐색하거나 값을 참조하기 위해서는 key를 통해 접근해야 한다. 이를 조금 더 이해하기 쉽도록 생각하자면 배열에서 색인(index)을 통해 요소에 접근하는것 처럼, Map에서는 key를 통해 요소에 접근한다. 즉 기존 정수로만 제한되어 있던 색인을 정수 뿐만이 아닌 여러 타입으로 확장하였다고 생각하면 이해하기가 쉬울 것이다. Map의 특징으로는 key의 중복을 허용하지 않으며 대신 value의 중복은 허용된다. 또한 key를 통해 데이터의 접근, 탐색에 $O(1)$라는 강력한 성능을 가지는 것도 특징이다. Hash는 어떠한 데이터를 입력받은 후 ..
프로그래머스 - 위장
2023. 3. 16. 15:59
DataStructure/Hash, map, set
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 해시맵을 사용하는 문제이지만 기본적으론 경우의 수를 구하는 문제이다. 만약 얼굴을 동그란 안경, 검정 선글라스로 상의를 파란색 티셔츠, 하의를 청바지, 겉옷을 긴 코트로 한다면 해당 부위를 입지 않는 경우의 수까지 포함하여 곱의 경우의 수를 계산해야 한다. 그렇다면 동그란 안경 - 파란색 티셔츠 - 청바지 - 겉옷, 동그란 안경 - 파란색 티셔츠 - 없음 - 겉옷 등으로 경우의 수..
BOJ 26008 해시해킹
2023. 3. 16. 15:54
DataStructure/Hash, map, set
문제 https://www.acmicpc.net/problem/26008 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 문제 접근 해당 문제는 해싱에 대해 묻고 있다. 주목해야 할 점은 해싱하는데 사용하는 해시 함수 h(P)에 대해서이다. 문제에서 제시한 해시 함수는 아래와 같다. $$ h(P) = (P_0 \ast A^0 + P_1 \ast A^1 + \cdots + P_{N-1} \ast A^{N-1}) mod M $$ 이때 $P_0$ 을 보자 $A^0$ 이 1..