목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]1927번 최소 힙 풀이: Heap

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 최소 힙은 루트 노드에 항상 가장 작은 원소가 위치하도록 하는 자료구조 입니다. 때문에 부모 노드는 자식 노드보다 항상 작은 값을 갖게 됩니다. 우선순위큐를 사용하여 쉽게 구현할 수 있습니다. 처음엔 scanf와 printf 대신 cin과 cout 을 사용했더니 시간 초과로 실패 했습니다. 구글링을 통해 일반적으로 scanf/printf 보다 cin/cout이 더 느리다는 점을..
알고리즘 문제 풀이/BOJ 2022. 3. 23. 17:14
[백준 BOJ][C++]14500번 테트로미노 풀이: 브루트포스 & DFS

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이 문제는 모든 도형이 회전, 대칭한 모든 모양에 대해 그 합을 구해도 되지만, 위 그림 처럼 ㅗ 모양을 제외한 나머지 모양은 depth가 4인 영역을 탐색하여 그 합을 구할 수 있습니다. 각 종이의 칸마다 DFS를 호출하여 depth가 4만큼 탐색하여 최대 합을 구하여 ㅗ 모양의 합과 비교하면 됩니다. ㅗ 모양은 회전하면 총 ㅗ, ㅜ, ㅓ, ㅏ 네가지 모양이 나오므로 4개의 함수를 작성하여 모양..
알고리즘 문제 풀이/BOJ 2022. 3. 21. 15:05
[백준 BOJ][C++]1107번 리모컨 풀이: 브루트 포스

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이 문제는 브루트 포스 알고리즘을 사용하여 해결하는 문제입니다. 우선, 현재 100번 채널에서 N 번 채널까지 이동하기 위해 버튼을 눌러야 하는 최대 횟수는 + 혹은 - 버튼만을 눌러야 하는 경우 입니다. 따라서 100-N의 절댓값이 최댓값이 됩니다. 브루트 포스 알고리즘을 사용하므로 0번부터 1씩 증가하며 차례대로 모든 경우를 탐색해야겠죠? [풀이 과정] 1. 숫자 num이 고장..
알고리즘 문제 풀이/BOJ 2022. 3. 20. 17:39
[백준 BOJ][C++]3085번 사탕 게임 풀이: 브루트 포스

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 이 문제는 브루트 포스 알고리즘을 사용하여 해결하는 문제입니다. 브루트 포스 알고리즘은 가능한 모든 경우를 확인하여 결과를 도출해내는 알고리즘입니다. 보드에서 교환할 수 있는 사탕은 위, 아래, 왼쪽, 오른쪽입니다. 우리는 보드에서 어느 한 사탕의 위치 (x, y)에서 교환하기 전의 가장 긴 부분과 교환한 후의 가장 긴 부분을 비교하여 더 긴 길이를 얻으면 됩니다! 이 과정을 모든 위치에 대해 반복하면 문제를 해결할 수 있습니다. [풀이 과정] 1. 보드의 위치 (x, y)에서 x열과 y행에 대해 가장 긴 길이를 ..
알고리즘 문제 풀이/BOJ 2022. 3. 20. 15:58
[백준 BOJ][C++]13398번 연속합 2 풀이: DP

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp[0][i] = i 번째 숫자까지의 연속 합의 최댓값 dp[1][i] = 숫자 하나를 제거한 i 번째 숫자까지의 연속 합의 최댓값 연속 합의 풀이는 다음 링크를 참고해주세요:) https://iridescent-zeal.tistory.com/47?category=1261302 문제 예제로 풀이 과정을 보겠습니다...
알고리즘 문제 풀이/BOJ 2022. 3. 16. 20:03
[백준 BOJ][C++]9465번 스티커 풀이: DP

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. DP는 2차원 배열 dp[2][100001] 크기로 선언하였습니다. 2차원 배열 arr은 2n개의 스티커 점수를 나타내는 배열입니다. dp[0][n] = 1열부터 n-1열의 총 스티커 점수에 n열 0행을 더했을 때의 최대 점수이고 dp[1][n] = 1열부터 n-1열의 총 스티커 점수에 n열 1행을 더..
알고리즘 문제 풀이/BOJ 2022. 3. 15. 12:45
이전 Prev 1 ··· 4 5 6 7 8 9 10 ··· 13 Next 다음