BOJ 2110 - 공유기 설치 문제
2023. 3. 25. 15:54
Algorithm/BinarySearch
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 접근 이분 탐색의 유형인데 주어진 집의 데이터를 가지고 이분 탐색을 진행하는 것이 아니다. 문제에선 두 공유기 사이의 최대 거리를 요구하고 있기 때문에 이분 탐색으로서 우리가 찾아야 하는 값은 바로 두 공유기 사이의 최대 거리이다. 따라서 가장 작은 범위는 각 집마다 공유기를 한 개씩 설치함으로서 얻어지는 0이 되며, 가장 큰 범위는 ..
투 포인터 활용 - 프로그래머스 보석 쇼핑
2023. 3. 19. 21:33
Algorithm/Two Pointer
문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 특정 구간에 모든 종류의 보석들이 포함되어 있는가를 묻는 문제이다. 보석들의 진열은 중복된 보석들이 존재할 수 있기 때문에 종류를 파악하기 위해 HashSet을 사용하였다. 또한 구간 내에 존재하는 각 보석의 종류와 그 갯수를 확인하기 위해 HashMap을 사용하였다. 투 포인터를 활용하는 곳은 HashMap의 size 즉 현재 구매한 보석의 종류들이 HashSet의 크기, 즉 진..
투 포인터 활용 - BOJ 2470 두 용액
2023. 3. 19. 21:15
Algorithm/Two Pointer
문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 접근 두 수의 합이 0에 가장 가까워야 한다. 하지만 데이터가 음수와 양수로 나뉘어져 있기 때문에, 두 수의 합의 절댓값을 가지고 판단해야 한다. 데이터 값이 중구난방으로 되어있어 바로 처리하기가 곤란하다. 정렬을 해서 음수 파트와 양수 파트를 나누고 양 끝에서 두 개의 포인터를 사용하여 투 포인터 전략을 사용해야 한다. 두 수의 합의 절댓값을 계산한 ..
투 포인터 - 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, 같다면 해당 스왑으로 인해 바뀐 배열을 그대로 출력하면 된다. 차이점은 힙 정렬을 보..
이분 탐색의 원리와 구현 방법
2023. 3. 16. 21:14
Algorithm/BinarySearch
이분 탐색이란? 이분 탐색(Binary Search)는 탐색 기법 중 하나로, 어떠한 데이터 리스트 L이 존재할 때 어떤 두 점을 지정하여 그 중간값을 보고 찾는 데이터와 비교하여 각 점의 위치를 옮기는 방법이다. 해방 방법을 사용하면 리스트의 길이가 N 일때, 매 번 2배씩 탐색 범위가 좁아지기 때문에 최종적으로 $O(logN)$이 된다. 일반적으로 탐색에 소요되는 시간이 $O(N)$임을 생각하면 효율적인 방법이다. 시간적으로 더 효율적인 대신에 하나의 제한 조건이 있다. 바로 데이터 리스트가 정렬되어 있어야 한다는 것이다. 이는 이진 탐색이 찾는 데이터와 현재 데이터를 비교하여 대소 유무에 따라 다음 위치를 결정하는 것이기 때문이다. 예시 문제 예시 문제로 백준의 숫자 카드가 있다. https://w..
DFS문제와 그 풀이 - (2)
2023. 3. 8. 21:34
Algorithm/BFS, DFS
해당 문제는 제로베이스 벡엔드 스쿨 11기 자료구조 문제입니다. 문제 설명 이메일 정보가 들어있는 2차원 문자열 배열인 accounts가 입력으로 들어온다. accounts[i][0]은 사람의 이름, accounts[i][1]은 이메일을 나타내는 구조로 되어있다. 한 사람이 여러 개의 이메일을 소유하기도 하며, 동명이인이 존재할 수 있다. 이때 구분하는 방법은 다음과 같다. 이름이 동일하고, 이메일이 다르다면 동명이인이다. 이름이 동일하고, 이메일 중 동일한 이메일이 존재한다면 동일인이다.(복수의 이메일을 가진 사람) 이때 이메일 정보를 취합하여 출력하는 프로그램을 작성하라 문제 접근 처음 보면 난해해 보인다. 하지만 입력 부분을 잘 보면 그래프로 모델링할 수 있다. 위의 조건 중 하나로 이름이 같고, ..
DFS 문제와 그 풀이 - (1)
2023. 3. 8. 21:05
Algorithm/BFS, DFS
해당 문제는 제로베이스 벡엔드 스쿨에서 만든 문제입니다. 문제의 설명 N x M 크기의 행렬인 board와 문자열 word가 입력으로 들어올 때 행렬 board에서 word를 찾을 수 있는지 확인하는 문제이다. 이때 word로 찾아지는 문자열은 모두 인접해 있어야 한다. 예를 들어 위와 같은 board가 주어졌다고 할 때, word로 ABCCED가 들어왔다면 위 사진의 색칠된 것과 같이 찾을 수 있게 되어 true를 반환하게 된다. 문제의 접근 word로 주어진 문자열을 찾을 때 모든 문자들이 인접해야 한다는 조건이 있다. 이는 board의 각 칸을 하나의 노드로 생각할때 상하좌우로 간선이 연결된 그래프로 모델링이 가능하다. 즉 문제는 이 그래프에서 탐색을 통해 word와 동일한 문자열을 만들어낼 수 있..