devlog

[백준] 전구와 스위치 2138번 (c++) 그리디

출처 : https://www.acmicpc.net/problem/2138 풀이 방법이 문제는 전구를 켜는 순서가 중요하지 않으며, 또한, 전구를 여러 번 켜고 끄더라도 같은 상태로 반복하므로, 각 전구는 0번 또는 1번만 변경하면 된다는 점을 파악하는 것이 중요하다. (2번 스위치 하는 것은 0번 스위치 하는 것과 동일) 문제 해결을 위해 첫 번째 전구부터 시작하여 전구를 바꾸는 경우와 그대로 두는 경우를 고려하며 탐색한다. 이 과정에서 현재 인덱스 이전의 전구가 원하는 정답 상태와 다르다면, 반드시 현재 전구를 바꿔야 한다는 규칙을 도출할 수 있다. 이러한 방식으로 인덱스를 늘려가며 조건을 적용해 나가면 최소 횟수로 전구를 원하는 상태로 만들 수 있다. #include #include #include..

출처 : https://www.acmicpc.net/problem/14466 풀이 방법먼저 문제를 이해하는 것이 중요하다.농장에서 다리가 없는 곳은 자유롭게 이동이 가능하지만, 다리가 연결된 곳은 다리를 건너야 이동이 가능하다.주어진 예시를 통해 이해해 보자위 이미지에서 체크가 소의 위치 사각형의 변에 동그라미가 다리의 위치이면, (3,3)의 위치로 이동하기 위해선 무조건 다리를 건너야 한다.하지만, (2, 2)와 (2, 3)은 다리를 이용하지 않고 돌아서 (2, 2), (1, 2), (1, 3), (2, 3)와 같이 다리를 이용하지 않고 이동이 가능하다. 이 문제를 쉽게 구현하기 위해, 다리를 저장하는 자료구조가 중요했다.다리라는 3차원 배열을 선언한 뒤 bridge [y][x][dir] 해당 배열을 ..

출처 : https://www.acmicpc.net/problem/23289 풀이 방법시뮬레이션 문제이므로 조건 정리를 꼼꼼하게 하고 풀이하면 된다. 해당 문제에서 가장 까다로운 부분은 벽을 처리하는 것이다.입력으로 주어지는 벽은 현재 칸에서 위 쪽에 있거나, 오른쪽에 있는데 이렇게 된다면 벽을 처리하기 위해 항상 해당 벽의 왼쪽 좌표나 아래쪽 좌표를 확인해야 한다는 불편함이 있다. 이를 해결하기 위해 입력을 받을 때 해당 벽의 양쪽 좌표에 벽을 표시해 주었다. 가령 a, b의 위쪽에 벽이 있다면, wall[a][b][2] = 1, wall [a-1][b][3] = 1로 y, x의 좌표에 dir (오른쪽, 왼쪽, 위쪽, 아래쪽)으로 설정해서 문제를 풀이하였다. 운풍기를 돌리기 위해 Fan 구조체를 정의하..

출처 : https://www.acmicpc.net/problem/20188 풀이 방법완전 탐색으로 노드를 기준으로 하면 시간 복잡도가 N^2 이므로 시간 초과된다.시간 복잡도를 줄이기 위해 DP를 사용할까 했지만, 노드를 기준으로 문제를 완벽하게 분리하는 것이 쉽지 않았다.이럴 때 필요한 것이 역발상 즉 간선을 기준으로 생각해 보면 정답을 구할 수 있다. 위 그림에서 5-6을 잇는 간선을 지나가는 경우는 5를 루트로 하는 서브트리의 노드 중 2개를 선택하거나, 5의 서브트리 노드 중 하나를 선택하고, 1, 4, 3중에 하나를 선택하는 경우라고 알 수 있다.그러므로, 각 노드를 루트로 가지는 서브트리에서 노드의 수를 계산해 주면 된다. 이는 dfs로 계산하고, 나온 값이 ret라고 하면, ret * (r..

출처 : https://www.acmicpc.net/problem/22954 풀이 방법처음에는 유니온 파인드 문제인 줄 알았지만 굳이 구현할 필요는 없었다.1. bfs 함수를 통해 트리를 만든다.-> 1번에서 만든 트리의 노드가 n개 라면 -> 문제의 조건에서 1개 이상이기만 하면 되므로 마지막에 방문한 노드만 분리하고 답을 도출한다.2. 만약 1번에서 구한 노드의 개수가 n보다 작으면 다음 방문을 안 한 노드를 기준으로 bfs를 진행한다.-> 2번에서 진행한 bfs를 통해 구한 노드의 수의 합과 1번에서 구한 노드의 수의 합 n이 아니라면 2개 이상으로 분할이 되므로 -1을 출력-> 만약 1, 2번에서 구한 노드의 수가 같으면 문제의 조건인 다른 개수의 노드를 가진 트리에 위반하므로 -1를 출력 주의 ..

출처 : https://www.acmicpc.net/problem/3687풀이 방법각 수를 만드는데 필요한 성냥개비의 수를 알아보자1 = 2개2 = 5개3 = 5개4 = 4개5 = 5개6 = 6개7 = 3개8 = 7개9 = 6개0 = 6개 가장 큰 수를 만드는 것은 가장 자릿수가 많아야 한다.가장 자리수가 많기 위해선 가장 작게 성냥개비를 사용할 수 있는 수를 최대한 많이 추가해야 하는데필요한 성냥의 수를 보면 너무 좋게 2개를 사용해서 1, 3개를 사용해서 7을 만들 수 있어 그리디 하게 풀방법을 생각해 낼 수 있었다.만약 주어진 성냥개비수가 홀수이면 맨 앞을 7로 나머지 뒤는 모두 1로, 반대로 짝수이면 모든 수를 1로 채워 넣으면 가장 큰 자릿수를 만들 수 있고 이것이 가장 큰 수가 된다. 가장 작..

출처 : https://www.acmicpc.net/problem/24042 풀이 방법주기마다 횡단보도의 신호가 들어온다는 것이 신기했던 문제이다. 현재 위치에서 이동할 수 있는 지역을 계산해 주기 위해 현재 위치에 해당하는 신호가 언제 들어오는지 시간을 체크해 주어야 한다.이를 시간적으로 빠르게 해 주기 위해 그래프의 인접 리스트에 저장할 때 불이 들어오는 시간도 저장해 주었다. (아니면 M시간을 계속 순회해야 함) 그리고 최단 시간 안에 이동해야 하므로 bfs와 우선순위 큐를 사용해서 가장 시간이 적은 것부터 방문해서 처리해 주었다. 다음 노드로 가기 위해 시간계산은 만약 (현재 시간 % m ) 보다 이동할 신호의 시간이 크다면 다음 시간을 cur.time + (next.time - (cur.time..

출처 : https://www.acmicpc.net/problem/2169 풀이 방법해당 문제에서 다른 dp문제와 다르게 고려해야 할 점은 음수 값을 가지는 칸이 있다는 것과 최단 거리가 아니라 가치의 합이 최대이기 때문에 빙 둘러서 오는 것이 답이 될 수 있다는 점이다. 우선 빙 둘러서 오는 것이 답이 될 수 도 있는데 여기서 고려해야 할 점은 한 번 방문한 점은 다시 방문하면 안 된다는 것이다.그렇기 때문에 backtracking을 사용해야함을 알 수 있다. 또한 같은 위치라도 어느 방향에서 오느냐에 따라 해당 위치에서의 최대 값이 달라지므로 3차원 dp를 사용해서 [y][x][dir] 즉 y, x를 dir 방향으로 방문했을 때 최대 값으로 메모리제이션을 했다. 여기서 음수 값이 존재하기 때문에 dp..

출처 : https://www.acmicpc.net/problem/1941 풀이 방법해당 문제를 보고 완전 탐색 문제인 것을 확인했다. 처음엔 단순히 dfs, bfs를 통해 임도연 파가 3명이 넘어가면 중단하며 인접한 7명의 사람을 선택하는 방법으로 풀이할까 했지만, 이렇게 한다면 아래 이미지와 같은 케이스는 탐색하지 못한다. 그렇기 때문에 각 위치의 인덱스를 이용해서 7명을 뽑고, 7명 중 임도연파 수를 세고, 인접한 지 검사하는 방법으로 완전탐색을 수행해야 한다.인덱스는 0부터 24까지 두었고 y좌표를 인덱스 / 5, x좌표를 인덱스 % 5로 설정해서 y, x좌표를 구했다.여기서 visited배열은 선택된 사람 adjVisited는 인접 검사를 진행하기 위한 bfs 수행 시 방문 여부이다. 7명 구하..

출처 : https://www.acmicpc.net/problem/1943 풀이 방법 이 문제는 냅색 문제 유형에 속한다. 주어진 동전의 종류와 각 동전의 개수를 사용해 두 사람이 같은 금액을 만들 수 있는지 확인해야 한다. 이를 해결하기 위해 DP(동적 계획법)을 사용한다.  1. 총금액 확인 • 먼저 주어진 모든 동전의 금액을 계산하여 총합 sum을 구한다. • 만약 총금액이 홀수라면 두 사람이 같은 금액을 가질 수 없으므로, 바로 0을 출력한다. 이는 두 사람이 나눠가질 금액이 정확히 sum / 2가 되어야 하기 때문이다. 한 사람이 sum/2 금액을 만들 수 있으면 나머지 사람은 남은 돈을 다 가져가면 sum/2가 되므로 자연스럽게 문제가 해결된다. 그러므로 sum/2를 구하는 경우만 생각하면 된..