문제풀이(8)
-
백준 알고리즘 풀이 1107번 - 리모컨
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net - 브루트 포스 문제. 알고리즘 1. 목표로 하는 채널을 기준으로 두고 1씩 내려가거나 1씩 올린다. 2. 1씩 올리거나 내린 수들이 망가진 키를 포함하지 않는지 검사한다. 3. 망가진 키를 포함한다면 다시 1번으로, 망가진 키를 포함하지않는다면, 100에서 무식하게 올리는 거랑 비교해서 작은 횟수를 출력한다. 예외 조건 1. 100에서 무식하게 올리거나 내린것이 더 적은 이동..
2020.05.14 -
백준 알고리즘 풀이 2096번 - 내려가기
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - 다이내믹 프로그래밍 문제 알고리즘 현재 칸이 가장 왼쪽 위치인 경우 -> dp [1][0]=max(dp [0][0],dp[0][1])+ map[0] 현재 칸이 중간 위치인 경우 -> dp[1][1] = max(dp[0][0],dp[0][1],dp[0][2])+map[1] 현재 칸이 가장 오른쪽 위치 -> dp[1][2] = max(dp[0][1],dp[0][2])+map[2] 시간 복잡도 총 n번(n>num..
2019.12.03 -
백준 알고리즘 풀이 1890번 - 점프
https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net - 백트래킹을 이용한 dp문제. 알고리즘 1. dp배열에 마지막 칸을 1로, 나머지는 0으로 초기화한다. 2. 백트래킹을 활용한 dfs를 사용..
2019.11.19 -
백준 알고리즘 풀이 1915번 - 가장 큰 정사각형
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net - 다이나믹 프로그래밍 - 알고리즘 - 1. 전체 맵의 오른쪽 아래를 기준으로 정사각형의 왼쪽 위라고 가정한다. 2. counts[][] 배열을 만들어서 그 지점을 좌측 상단으로 하는 가장 큰 정사각형이라고 정의한다. 3. counts[a][b] = min(counts[a+1][b],counts[a][b+1],counts[a+1][b+1])+1 -시간 복잡도- 맵의 총크기 : O(n) * O(n) 각 경우당 4번씩 탐색. 따라서 총 시간 복잡도 = 4 * O(n) *..
2019.10.15 -
백준 알고리즘 풀이 13458번 - 시험 감독
https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net - 그냥 구현하는 문제. 문제 조건대로 풀면 된다. -시간 복잡도- O(n) - 예외 조건 - 1. 사람이 기준치에 미치지 못하여도 감독관이 들어가야 한다. -소스 코드- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std;..
2019.10.10 -
백준 알고리즘 풀이 5014번 - 스타트링크
- bfs 알고리즘 -시간 복잡도- O(|V|+|E|) - 알고리즘 - 1. 처음 내가 있는 위치를 queue에 넣는다. 2. U, D을 사용해서 bfs를 돌린다. 3. 원하는 위치에 들어왔다면 종료 후 그 배열 값에 저장된 값을 출력한다. - 예외 조건 - 1. bfs를 다 돌렸는데도 G를 방문하지 못했다면 계단으로 가도록 한다. 2. node에 방문하지 않는 조건을 visited [now]가 0일 때로 했으므로 처음에 들어가는 값의 visited는 1로 넣어주고 답에서 1을 빼주어야 한다. 계속 메모리 초과가 나와서 이유를 알 수 없었는데, queue에 넣는 조건을 visited [now]가 1일 때로 지정해 놓아서 메모리 오류가 나고 있었다. 새로 알게 된 사실인데 변수 이름을 g, d, u, f,..
2019.09.16 -
백준 알고리즘 풀이 1780번 - 종이의 개수
분할 정복 문제. - 알고리즘 - 1. 각 종이에 있는 모든 칸의 수가 같은지를 확인한다. 2. 모든 칸의 수가 같다면 그 칸에 있는 숫자 인덱스 값 1더한다. 3. 모든 칸의 수가 같지 않다면, 종이에 있는 칸의 갯수를 1/3로 줄이고, 첫 칸을 각 종이의 첫번째 항으로 한다. - 예외 조건 - 1. -1은 인덱스가 될 수 없으므로 값을 저장할 때 다 +1을 하고 넣어주어야 한다. 첫 칸을 각 종이의 첫번째 칸으로 하는게 좀 어려웠다. 간단히 생각해보면 for문을 두개 돌려서 넣으면 된다. -소스 코드- #include using namespace std; int map[2188][2188]; int count[4]={0,}; bool check(int num,int x,int y) { int isSa..
2019.09.05 -
백준 알고리즘 문제 풀이 10610번 - 30
그리디 알고리즘 3의 배수일 조건 : 각 자릿수의 합이 3의 배수여야 한다. 10의 배수일 조건 : 1의 자릿수가 0이어야 한다. 30의 배수일 조건 : 3의 배수이면서 10의 배수이어야 한다. -문제 풀이 1. 예외 조건을 처리한다. 2. 예외 조건에 걸리지 않는다면 맨 뒷자리에 0을 놓고 나머지를 정렬한다. -예외 조건 1. 주어진 숫자에 0이 포함되지 않을때. 2. 각자리수 합이 3의 배수가 아닐 때. -소스 코드 #include #include using namespace std; int main() { int hap=0; //3의 배수인지 아닌지 판단하기 위한 변수 int arr[1000001]; string a; cin>>a; for(int i=0;i
2019.09.05