Algorithm

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 문제다. 멀티탭에 플러그를 꽂되, 플러그를 최대한 적게 빼는 횟수를 구하는 문제다. 입력된 멀티댑 사용 순서는 유지 해야 하므로 앞에서부터 접근했다. 1. 해당 플러그가 이미 꽂혀 있는지 확인 2. 플러그에 빈 자리가 있다면 꽂기 3. 빈 자리가 없다면 현재 꽂힌 플러그 중 가장 나중에 사용되는 플러그를 뽑는다. 3번을 처리하는 구현이 살짝 까다로웠지만 알고리즘 자체를 생각해내는데 어렵진 ..

https://www.acmicpc.net/problem/2879 2879번: 코딩은 예쁘게 첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수 www.acmicpc.net 그리디 문제다. 근데 구현 문제 같다. 코드의 인덴트를 맞추는 문젠데 드래그 후 탭을 누르는 횟수를 최소로 만들어야 한다. 탭을 추가해야 하는 경우와 삭제해야 하는 경우를 나눠서 생각했다. (양수와 음수) 추가해야 하는 경우 결과 값과 현재 값의 차이가 양수다. 이 때 이전 값이 음수라면 res에 현재 값을 더해준다. 이전 값이 양수라면 두 가지 경우로 나뉜다. 이전 값보다 현..

https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net DP와 누적합 문제다. 불도저가 왼쪽 위에서 오른쪽 아래까지 가는 길에 아래 부분은 사과가 많도록 윗 부분은 바나나가 많도록 지나가야 한다. 불도저는 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 움직일 수 있다. 열을 기준으로 생각을 했다. 아래로 가는 경우에는 아래 칸이 사과인지만 확인해서 빼주면 되고 오른쪽 혹은 대각선으로 움직이는 경우는 그 열에 대해 위의 바나나나 아래 사과만 확인해주면 된다..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 문제다. 스도쿠를 완성시키면 되는 문제인데 이와 유사한 문제로 2580 스도쿠 문제가 있다. 두 문제의 차이점은 입력에서 공백의 유무가 전부다. 2580 문제를 전에 푼 적이 있어서 그 코드를 넣었더니 맞았다. https://abbiddo.tistory.com/59 웃긴 점은 제한에 저렇게 쓰여져 있어 들어가봤더니 2580문제에 대한 답이 있다. 넣어보니 진짜 맞는다. 근데 내가 푼..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제다. 9 x 9로 배열이 크지 않아 백트래킹을 이용했다. 배열에서 0인 칸을 따로 저장해두고 해당 칸을 순차적으로 채워나가는 방식이다. 채울 때의 조건은 같은 행이나 열에 그 숫자가 없고 3 x 3 칸 안에 그 숫자가 없어야 한다. 스도쿠가 다 채워지면 해당 스도쿠 답을 출력한다. #include #include using namespace std; bool complete; int ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터와 누적 합 문제다. 주어진 배열에서 연속된 수들의 부분합 중에 s이상이 되는 수열 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터를 사용하여 앞에서부터 포인터를 옮겨주며 해당 포인터들 사이의 누적 합 연산을 수행했다. 합이 s 미만이면 right 포인터를 한 칸 옮겨주어 합을 늘렸다. right 포인터가 끝에 다달았다면 반복문을 종료했다. (누적 합이 더 커질 수 ..