알고리즘/BOJ(C++)
-
[백준] 1052 :: 물병알고리즘/BOJ(C++) 2020. 7. 14. 23:13
https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 마치 구현인듯 보이지만 알고보면 수학인 문제 허허,, 예시를 들며 문제를 이해해보자. N=3일경우 [1, 1, 1] => [2, 1] 로 합칠 수 있다. N=5일 경우 [1, 1, 1, 1, 1] => [2, 2, 1] => [4, 1]로 합칠 수 있다. N= 9일 경우 [1, 1, 1, 1, 1, 1, 1, 1, 1] => [2, 2, 2, 2, 1] => [4, 4, 1] => [8, 1]로 합칠 ..
-
[백준] 11725 :: 트리의 부모 찾기알고리즘/BOJ(C++) 2019. 8. 2. 16:02
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 입력되는 간선정보를 바탕으로 각 노드의 부모를 저장하면 된다. 트리는 항상 n개의 노드가 있을 때 간선이 n-1개이므로 우리는 n-1개의 간선만 입력받아도 트리를 만들 수 있다. 처음에 일차원배열로 풀었다가 틀렸다. 왜냐하면 간선 정보가 depth가 깊어지는 순서대로 입력된다는 보장이 없기 때문이다. 따라서 그래프 입력받듯이 모든 간선 정보를 vector에 저장한 후 한번에 트리를 만들어야 한다. 소스코드 ...더보기 1 2 3 4 5 6 7 8 9 10 11..
-
[백준] 2250 :: 트리의 높이와 넓이알고리즘/BOJ(C++) 2019. 8. 2. 15:59
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다. www.acmicpc.net 문제 그대로 트리의 넓이를 구하는 문제이다. 가장 중요한 포인트는 트리의 각 노드가 몇번째 열에 위치하는지를 알아내는 것인데, 조금만 고민해보면 이것은 preorder 트래버설로 알아낼 수 있다. 프리오더 트래버설은 왼쪽 -> 루트 -> 오른쪽 이렇게 탐색하는 방식이고 이 순서대로 탐색..
-
[백준] 3055 :: 탈출알고리즘/BOJ(C++) 2019. 8. 1. 19:28
https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 해결방법 1. 비버의굴과 바위는 못가는 곳으로 표현한다 2. 물이 위치하는 곳에서 부터 bfs를 탐색해, 어떤 지점에 몇초만에 그 물이 도달..
-
[BOJ] 1202 :: 보석 도둑알고리즘/BOJ(C++) 2018. 7. 24. 12:09
https://www.acmicpc.net/problem/1202 으엉 ㅠㅠ어려웠고 엄청 많이 틀렸던 문제라서 문제풀면서 느낀거 정리하려고 씀 1. 그리디한 문제. 가장 큰 가격 부터 가방에 담으려고 시도 -> 가방에 담을 때 자신보다 크거나 같은 가방 중 가장 작은 가방을 찾아야함2. 정말 naive하게 풀면 nk가 나오는데 물론! 시간초과3. 지금 담으려는 무게보다 크거나 같은 것 중 가장 작은 가방을 찾는 과정에서 시간을 줄이기 위해 lower_bound를 생각함(logN)4. lower_bound로 담을 수 있는 가방을 찾고 그 가방을 사용했다는 표시?를 하기위해 erase연산을 사용헀으나, vector에서 erase연산은 n의 시간복잡도를 가지므로 약 n^2logn이 나와 시간초과5. 우선, p..
-
[BOJ] 14226 :: 이모티콘알고리즘/BOJ(C++) 2018. 7. 3. 15:22
https://www.acmicpc.net/problem/14226 pair를 한 정접으로 하는 그래프를 생각하고, bfs탐색을 진행합니다. pair의 first원소는 현재 화면에 있는 이모티콘의 개수이고 second원소는 클립보드에 있는 이모티콘의 개수입니다. index관련 예외처리만 잘해주면 됩니다! 요즘 런탐에러 너무많이나네요ㅠ 실수안해야지.. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include using namespace std; int s; bool check[1003][2003];int dist[1003][2003]; int main(){ cin..
-
[BOJ] 9019 :: DSLR알고리즘/BOJ(C++) 2018. 7. 2. 22:58
https://www.acmicpc.net/problem/9019 얘도 BFS문제입니다! 앞으로 한동안은 미뤄놨던? 어려운 BFS문제들을 다 풀어서 끝내려고합니당... 이번주 scpc 2차라서 좀 다양한 못접해본 문제들 풀어야 하긴 하는데 ㅠ 몬가 이제와서 새로운 개념 공부해서 풀기 좀 늦은것 같기도하고... 암튼 잡소리 치우고 이문제도 너무 전형적인 bfs문제인데 여기서는 이제 다른 bfs문제랑 다른게 현재 탐색중인 지점이 어디서왔는지를 나타내는것(from배열 이용) 뿐만 아니라 그 지점으로 올때 사용된 방법(how)도 기록을 해주어야 한다는 점 입니다! L과 R구하는데 실수만 안하면 하핳...금방 풀수있는 문제입니다123456789101112131415161718192021222324252627282..
-
[BOJ] 1377 :: 버블 소트알고리즘/BOJ(C++) 2018. 7. 1. 15:49
https://www.acmicpc.net/problem/1377 백준 풀고 점점 풀이올리기가 귀찮아지는데...풀이올리면 나도 한번 다시 푸는 방법 복습하는 거니까 다시 열심히 올리려고한다! 우선 이 문제는 우리가 아는 평번한? 버블 소트 문제인데, 전체 크기인 N의 크기가 너무 커서 실제 버블 소트를 돌리면 TL이 뜬다. 그래서! 우리는 처음 들어왔을 때 수의 위치와 정렬 후 수의 위치를 비교해 가장 앞으로 많이 옮겨간 수가 몇칸 옮겨갔는지를 찾아주면 되는 문제이다!이때 정렬할때 algorith 헤더파일에 들어있는 sort함수를 쓰면 nlogn에 정렬이 가능하다. vector pair로 입력을 받아 first에는 수의 값 second에는 위치를 입력받으면 된다.후에 first를 기준으로 sort하고 s..