반응형

전체 글 88

BOJ 18111 마인크래프트

이 문제는 땅의 높이를 0~256중 하나로 하여 땅을 고르게 만들때 걸리는 시간과 땅의 높이를 출력하는 프로그램이다. 처음 생각한 방법은 같은 높이의 블록 갯수를 파악하여 {높이,갯수} 형태로 배열에 저장하고 이들중 하나의 높이로 통일 시킬 때 걸리는 시간과 높이를 구하여고 하였다. 하지만 위와 같은 방법의 문제점은 문제에서 주어진 높이로만 땅을 고르게 할때 다음과 같은 반례가 나올 수 있다. 1 3 1 1 4 1 다음과 같은 경우 정답은 6 2 가 되지만 처음 생각한 방법으로 구현 하였을 경우 배열에 {1,2},{4,1}이 들어가고 결과는 6 1 이 나오게 된다. 이는 문제에서 시간이 같다면 높이가 높은것을 구하라고 하는것을 빼먹은 것이다. 이를 해결하기 위해 모든 높이에 대해 걸리는 시간을 모두 구하..

알고리즘/boj 2023.02.13

BOJ 10816 숫자 카드 2

이 문제는 상근이가 가지고 있는 숫자 카드 N개 중 주어진 M(정수)를 몇개씩 가지고 있는지 구한는 문제이다. N은 -10,000,000 ~ 100,000,000 사이의 숫자로 중복된 값이 들어올 수 있다. 이를 해결하기 위해 N개의 카드 중 특정 숫자가 몇개 존재하는지 체크를 해야한다. 가장 간단한 방법은 카드에 적혀 있는 숫자를 배열의 인덱스로 하여 카운팅 해주는게 편리한데 그렇게 할 경우 인덱스 범위가 0~ 200,000,000이 되어 해당 크기의 배열을 정의할 수 없다. 따라서 다른 방법을 생각해야한다. 생각해낸 방법은 백터를 이용하여 N을 정렬한 후 순차 탐색하면서 이전의 값이랑 중복되는지 안되는지 확인하여 새로운 해싱 백터를 만드는 것이다. 자세한 방법은 아래 코드에서 확인할 수 있다. 위의 ..

알고리즘/boj 2023.02.10

BOJ 7662 이중 우선순위 큐

기본적으로 우선순위 큐는 삽입,삭제에 대해 O(logN)의 시간복잡도를 가진다. 또한 트리구조를 취하는 MaxHeap( 또는 MinHeap)으로 구현된다. 문제에서 Q의 종류중 D 1 은 가장 큰 값 삭제, D -1은 가장 작은 값 삭제를 수행하야 하지만 우선순위 큐 한개로는 불가능 하다. 따라서 MaxHeap, MinHeap으로 구현된 우선순위 큐 2개를 사용해야 한다. 여기 까지가 처음 생각한 방법이다. 하지만 문제는 두 큐가 동기화가 되지 않는다는 점이다. 한참을 고민하던도중 multiset이라는 자료구조를 이용하면 해결 가능하다는 것을 발견하였다. multiset이란 기본적인 set은 중복을 포함하지 않고 정렬되어있지만 multiset은 중복을 허용한 정렬된 자료구조이다. 또한 특정 값을 eras..

알고리즘/boj 2023.02.05

BOJ 18870 좌표 압축

문제를 분석해보면 새로 생성된 좌표 X`은 Xi > Xj를 만족하는 좌표의 갯수를 의미하는 것을 알 수 있다. 이는 i번째 좌표보다 작은 좌표의 갯수가 압축된 좌표임을 나타내는데, 핵심은 어떻게 특정 좌표보다 작은 좌표의 갯수를 구하는것이다. 가장 단순하게 이중 for문을 사용하며 부르트포스 방식으로 탐색한다면 O(n^2) 으로 시간초과가 발생한다. 따라서 다른 방법을 떠올려야한다. 입력을 보았을때 가장 작은 숫자는 항상 0으로 압축이된다. 이를 바탕으로 좌표를 오름차순으로 정렬하고 i=1, i번째 좌표가 i-1번째 좌표보다 클 경우 이전 좌표값에서 1을 증가시켜주는 방법으로 갯수를 파악할 수 있다. 이 방법을 사용하면 O(n) 만에 특정 값보다 작은 값의 갯수를 구할 수 있다. #include #inc..

알고리즘/boj 2023.02.05

BOJ 2805 나무 자르기

이 문제는 얼마전 포스팅했던 BOJ 1654 랜선 자르기 문제와 100%일치하는 문제이다. 핵심은 적절한 나무 길이를 구하기 위해 이진 탐색을 이용해야하는 것이다. https://devconf.tistory.com/65 BOJ 1654 랜선 자르기 이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개( devconf.tistory.com #include #include #include #include using namespace std; typedef long long ll; int n, m; vector len; ll result; bool cmp(ll a, ll ..

알고리즘/boj 2023.02.03

BOJ 1826 연료 채우기

이 문제의 접근 방법은 현재 가진 연료로 갈수 있는 주유소 중 멈췄을때 가장 많은 연료를 획득할 수 있는 주유소에서 멈추면 된다. 주유소의 위치가 순서대로 들어오지 않기 때문에 주유소 위치를 정렬 시켜주어야 한다. 이후 현재 가진 연료로 멈출 수 있는 모든 주유소에서 얻을 수 있는 연료의 양을 우선순위 큐에 넣고 빼면서 전체 획득한 연료 양을 누적시킨다. #include #include #include #include using namespace std; priority_queue pq; vector v; int n; int l, p; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 0; i < n; i..

알고리즘/boj 2023.02.03

BOJ 1654 랜선 자르기

이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개(이상)의 랜선을 만들수 있는지 없는지에 초점을 두었다. 여기서 핵심은 적절한 랜선의 길이를 어떻게 잡는가 이다. 여기서 선택지는 두가지로 다음과 같다. 1. 가장 큰 길이를 기준으로 적절한 랜선 길이를 찾아내기 2. 가장 작은 길이를 기준으로 적절한 랜선 길이를 찾아내기 가장 작은 길이로 적절한 랜선 길이를 찾아낼 경우 최대 랜선의 길이를 구할 수 없다. 예를들어 입력이 2 10 100 4 일때 최대 랜선의 길이는 10 이 되지만 가장 작은 길이를 기준으로 하였을 경우 결과는 4가 된다. 가장 큰 길이의 랜선을 기..

알고리즘/boj 2023.02.01

BOJ 10816 숫자 카드 2

이 문제는 N개의 카드중에서 M개의 카드 숫자가 몇개 있는지 찾는 문제이다. 단순한게 브루트포스 방법 O(n^2)으로 문제를 해결하려고 시도한다면 N = 500000, M = 500000 이므로 시간초과가 발생한다. 따라서 특정 숫자가 어디에 있는지 빠르게 탐색하기 위해 이진탐색으로 접근해야 한다. 이진탐색을 하기 위해서는 우선 상근이의 숫자 카드 N이 오름 차순으로 정렬이 되어있어야 한다. 이때 핵심은 중복된 숫자 카드를 어떻게 표현할 것인가 이다. 오름 차순 정렬 후 앞쪽부터 순회하면서 중복된 숫자를 pair 로 변환 시켜준다. 예를들어 N이 -10, -10, 1, 3, 5, 10, 10, 10 일경우 {-10,2}, {1,1}, {3,1}, {5,1}, {10,3} 과 같은 형태로 변환을 시켜준다...

알고리즘/boj 2023.02.01
반응형