백준 algorithm
-
백준 11286 - 절댓값 힙백준 algorithm 2022. 4. 9. 23:06
입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다. 예제 입력 1 복사 18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0 예제 출력 1 복사 -1 1 0 -1 -1 1 1 -2 2 0 => 기존 최소힙, 최대힙 문제를 응용한 ..
-
백준 1927 - 최소 힙백준 algorithm 2022. 4. 6. 23:16
입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 출력 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다. 예제 입력 1 복사 9 0 12345678 1 2 0 0 0 0 32 예제 출력 1 복사 0 1 2 12345678 0 => 최대힙의 반대로 최소힙문제입니다. => queue 헤더안에 있..
-
백준 11279 최대힙 C++백준 algorithm 2022. 4. 2. 23:58
예제 입력 1 복사 13 0 1 2 0 0 3 2 1 0 0 0 0 0 예제 출력 1 복사 0 2 1 3 2 1 0 0 => 최대힙을 구현할 수 있는지에 대한 문제였습니ㅏㄷ. => C++에는 queue 헤더 안에 priority_queue 자료형을 사용 할 수 있습니다. => 해당 자료형을 이용해서 주어진 조건에 따라 출력문을 출력하면 되는 문제였습니다. => 시간초과가 걸릴 경우, cin.tie(0); ios_base::sync_with_stdio(false); 해당 구문을 입력해줄 경우 시간초과에 걸리지 않게 됩니다. #include #include #include #include #include #include #include #include #include using namespace std; i..
-
백준 2606 바이러스 C++백준 algorithm 2022. 3. 31. 01:16
입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 출력 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다. 예제 입력 1 복사 7 6 1 2 2 3 1 5 5 2 5 6 4 7 예제 출력 1 복사 4 => DFS 문제입니다. => 주어진 정점과 간선들은 배열을 통해 구현해두어야합니다. => arr[MAX][MAX] : 간선을 표현한 배열 => 각 정점이 연결되어 있을 경우 '1'로 표현..
-
백준 7576 - 토마토 C++백준 algorithm 2022. 3. 29. 23:15
입력 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다. 출력 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 ..
-
백준 2178 - 미로탐색 C++백준 algorithm 2022. 3. 28. 17:45
입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다. 예제 입력 1 복사 4 6 101111 101010 101011 111011 예제 출력 1 복사 15 예제 입력 2 복사 4 6 110110 110110 111111 111101 예제 출력 2 복사 9 예제 입력 3 복사 2 25 1011101110111011101110111 1110111011101110111011101 예제 출력 3 복사 38 예제 입력 4 복사 7 7 1011111 1110001 1000001 10000..
-
백준 2003 수들의 합 2 C++백준 algorithm 2021. 11. 2. 23:03
=> 투포인터의 기본개념을 묻는 문제입니다. => while문을 통해 시간 복잡도 O(N)의 속도를 이끌어낼 수 있는 알고리즘입니다. https://codingham.tistory.com/232 백준 1806 - 부분합 => 투 포인터 알고리즘의 개념을 알면 풀 수 있는 문제입니다. (저도 이 문제를 풀면서 처음으로 해당 알고리즘을 들었습니다.) => start 점과 end 점의 위치를 변환해가며 S의 값을 넘으면 가장 적은 codingham.tistory.com 위 문제는 투포인터를 활용한 문제입니다. 해당 문제를 푼 후에 해당 문제를 풀어보는 것도 좋은 방법입니다. => arr[0] 부문에 값을 미리 넣어 계속 틀렸었습니다. #include #include using namespace std; int..
-
백준 1806 - 부분합백준 algorithm 2021. 11. 1. 23:02
=> 투 포인터 알고리즘의 개념을 알면 풀 수 있는 문제입니다. (저도 이 문제를 풀면서 처음으로 해당 알고리즘을 들었습니다.) => start 점과 end 점의 위치를 변환해가며 S의 값을 넘으면 가장 적은 길이를 찾아내는 방법입니다. => while문에서는 end가 0 인경우에 값을 부분합에 포함하지 않으므로, 이전에 값을 더해주는 과정이 필요합니다. => while문을 통해 start 점이 end점을 앞서지 못하도록 하며, end점이 N(배열 원소의 개수)를 넘지 못하도록 합니다. (배열의 끝점 = (원소의 갯수 -1) ) => 부분합이 S를 넘지 못할 경우 end점을 뒤로 한 칸 미루며 다시 한번 계산합니다. => 부분합이 S인 경우, 최소값을 구하고 다시 한번 end점을 뒤로 미룹니다. ( 이후..