💻 OnlineJudge/Baekjoon

[백준 / BOJ] C++ 17610 양팔저울

https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 풀이 틀렸습니다와 런타임 에러로 고생한 문제... 이문제 난이도가 실버 1이라니 ..ㅜ 어떻게 해야할까 생각하다가 알고리즘 분류에 브루트포스 알고리즘을 보자말자 '완전탐색 문제구나' 했다. 우선 위의 그림과 같이 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게를 구해야한다. 이 경우의 수는 아래의 이미지와 같다. 따라서, 양팔저울에 무게추를 올리는 경우의 수는 다음과 같이 정리할 수 있다..

[백준 / BOJ] C++ 1697 숨바꼭질

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 문제에서 주어지는 조건 3가지를 만족하는 한 모든 경우의 수를 큐에 넣어버린다. 이후, 수빈이의 위치 X와 동생의 위치 K가 동일한 값이 되는 가장 처음 값을 구하면 된다. 계속 반복하며 처음 입력한 위치를 기준으로 모든 경우의 수를 큐에 다 넣고, 동생의 위치만 수빈이와 동일하면 정지시켜주자. 이후, 해당 위치값을 출력하면 끝. 직전 포스팅인 미로 문제와 크게 다..

[백준 / BOJ] C++ 2178 미로 탐색

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 연결된 점을 찾아가는 문제이다. (N,M). 이런문제는 알고리즘 분류에도 나와있지만, 너비 우선탐색으로 풀 수있다. 너비우선 탐색은 보통 큐 (queue)를 이용하여 구현한다. 큐에 관해 포스팅 되어있으니 참고하길 바란다. https://hyun-jun5.tistory.com/m/57 [Algorithm] C++ Queue (큐) 클래스 구현 큐 ( Queue ) FIFO(First In First Out) - 선입선출 이..

[백준 / BOJ] C++ 1260 DFS와 BFS

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS란? - 깊이우선탐색(Depth First Search)으로, 방문할 수 있는 정점이 있을경우, 계속해서 탐색해 나가는 방법이다. 보통 스택이나 재귀함수를 이용하여 탐색한다. BFS란? - 너비우선탐색(Breadth First Search)으로 해당 노드층의 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통 큐를 ..

[백준 / BOJ] C++ 11000 강의실 배정

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 우선순위 큐와 vector를 이용하였다. vector에 시작시간과 종료시간을 넣은 후 오름차순으로 정렬한다. 이후 우선순위 큐에 오름차순으로 정렬된 종료시간을 저장하고, 이후 종료시간과 두번째 저장된 시작시간을 비교한다. 종료 시간보다 시작시간이 작은 경우는, 다른 강의실을 사용해야하기에 우선순위 큐에 넣어주고, 예외 상황에는 동일 강의실을 쓰기에, pop 이후 다시 push를 해준다. Code #include #include #inclu..

[백준 / BOJ] C++ 2075 N번째 큰 수

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 우선순위 큐를 이용한 간단한 문제입니다. 전체 숫자를 전부 큐에 넣으면 아니나 다를까, 시간초과입니다. 정렬된 우선순위 큐에서 주어진 수 N의 크기보다 더 클 경우 해당 숫자를 pop 해주고, N개의 큰 수들만 남겨놓는 식으로 풀 수 있습니다. Code #include #include using namespace std; int main() { ios::sync_with_stdio(false); c..

[백준 / BOJ] C++ 7662 이중 우선순위 큐

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 최댓값 우선순위 큐와 최솟값 우선순위 큐를 나누어 해결하는 이중 우선순위 큐 문제이다. 이런 구조는 흔히 레드 블랙트리구조인데 , C++ 에서는 multiset이 있어 이 자체로 이중 우선순위 큐의 역할을 할 수 있다. 또한 중복데이터 삽입이 가능하며, top bottom 원소 모두 삭제가 가능하다. Code #include #include using namespace std; int m..

[백준 / BOJ] C++ 1715 카드 정렬

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 우선순위 큐를 사용하는 간단한 문제이다. 우선순위 큐에 입력된 카드 갯수를 하나씩 push 해준 이후, top 의 원소 2개를 먼저 더해주고 해당 큐가 비어있지 않다면 push 해주어 다음 원소와 더한 값들을 결과값에 넣어주면 된다. Code ( C++ ) #include #include using namespace std; int main() { ios::sync_with_s..