Algorithm

[백준 12100번] 2048 (easy) (C/C++)

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 문제는 백트래킹을 이용하여 이동의 모든 경우의 수를 구하고, 큐를 이용하여 각 경우의 수에 대해 가장 큰 블록을 계산하였습니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second int board[20][20]; vector p; vector selected(5); int ..

[백준 18808번] 스티커 붙이기 (C/C++)

https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 전체 알고리즘의 기본 틀은 아래와 같습니다. 스티커의 각 좌표를 구한다. 노트북에 붙여본다. 실패한다면 각 좌표를 90° 시킨다. 2번 부터 다시 진행한다. (단, 360° 회전시킨 경우, 더이상 노트북에 붙여보지 않는다.) 아래는 각 좌표를 90° 회전시키는 함수입니다. ⚠️ 주의할 점은 이후에 또 다시 각 좌표를 90° 회전시킬 수 있기 때문에 n과 m을 교환해주어야 한다는 것입니다. void ..

[백준 14888번] 연산자 끼워넣기 (C/C++)

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 연산자 끼워넣기 문제는 백트래킹을 이용하였습니다. next_permutation()를 이용하여 연산자 수열의 모든 경우의 수를 뽑아내고, 각 수열에 대해 연산식을 계산하면 됩니다. 주의할 점은 next_permutation()을 호출하기 전에 대상 배열이 정렬되어 있어야 합니다. 또한 100 이하의 정수가 최대 11개 주어지며, 곱셈 연산이 ..

[백준 13335번] 트럭 (C/C++)

https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 트럭 문제는 큐와 덱을 이용해서 해결할 수 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 기다리는 트럭을 모두 Queue1에 넣는다. 다리 위에 있는 트럭들을 모두 앞으로 1씩 이동시킨다. 다리를 건넌 트럭은, 다리 위의 트럭을 저장하는 Queue2에서 pop() 한다. Queue1에서 가장 앞에 있는 트럭을 pop()하여 Queue2에 push..

[백준 1107번] 리모컨 (C/C++)

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이동 가능한 채널 번호를 계산하기 위해 백트래킹을, 최단 거리를 계산하기 위해 BFS를 사용했습니다. 아래는 main 함수입니다. 먼저 이동하려는 채널 번호, 고장난 버튼의 개수, 고장난 버튼을 입력 받은 후 모든 채널 번호를 계산합니다. 그 후 계산된 채널 번호를 가지고 이동하려는 채널 번호까지의 최단 거리를 계산합니다. int main(){ ios::sync_with_stdio..

[백준 1654번] 랜선 자르기 (C/C++)

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 랜선 자르기 문제는 K가 10,000이하이고, N이 1,000,000 이하이므로, 전체를 탐색하면 시간이 초과되기 때문에 이분탐색을 이용해야합니다. 또한 랜선의 길이는 int형의 최대값이 될 수 있으므로, 아래 케이스의 경우 만들 수 있는 랜선의 개수는 int형의 범위를 벗어날 수 있습니다. 따라서 자료형으로 long long형을 사용해야합니다. 2 1000 21474..

[백준 2805번] 나무 자르기 (C/C++)

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 나무의 높이가 최대 10억이기 때문에 모든 높이에 대해 잘린 나무의 길이를 계산하면 시간초과가 발생합니다. 따라서 나무 자르기 문제는 이분탐색을 이용해야합니다. 중요한 점은 나무의 개수가 최대 백만개이고, 높이는 최대 10억이기 때문에, 잘린 나무의 높이를 계산할 때, 결과 값을 저장하는 변수의 자료형이 long long이 되어야 한다는 것입니다. 또한 적어..

[백준 18111번] 마인크래프트 (C/C++)

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 블럭을 제거하는 경우 2초, 블럭을 쌓는 경우 1초입니다. 땅을 고르는데 걸리는 시간이 최소로 걸리기 위해서, 가능한 땅 높이의 범위는 가장 낮은 땅 ~ 가장 높은 땅입니다. 아래는 전체 코드입니다. #include using namespace std; #define v first #define h second int n, m, b; int board[500][500]; int main(){ i..