구름 개발일기장

https://www.acmicpc.net/problem/8972 🐢 설명 내가 조종하는 아두이노 기기 [I]와 미친 아두이노 [R] 들이 만나지 않고 주어진 명령을 수행하는지 확인하는 문제이다. 또한, 주어진 8방향은 순서가 정해져있으므로 그에 맞춰서 dir 배열을 만들어야 한다. 나의 아두이노가 실패하는 경우 내가 이동할 때 미친 아두이노를 만난 경우 미친 아두이노가 나에게 가깝게 이동하는데 만난 경우 내가 성공하는 경우 주어진 명령 방향을 온전히 수행하는 경우 주어진 명령이 맵을 벗어나는 경우가 없어서 맘편히 돌리면 되어서 좀 편했다. 일단 모든 미친 아두이노를 리스트에 담고 지도에 -1로 표시해주었다. 이 후 나의 아두이노가 주어진 명령 하나를 수행하고, 모든 미친 아두이노들에 대해서 8방향 중 ..

https://www.acmicpc.net/problem/18119 🐢 설명 비트마스킹 문제이다. 기억하는 단어, 잊는 단어가 입력으로 주어지는데 이를 기반으로 bit를 on/off 한 후에 기억하는 알파벳과 해당 단어에 대한 비트를 비교해서 전부 on이라면 (즉, 해당 단어의 알파벳들의 비트와 기억하는 단어의 비트가 같다면) 해당 단어는 기억하는 단어로 Count를 올려준다. 알파벳 26개에 대한 bit 26개를 전부 1로 켜준다 -> (1 11111111111111111111111111 (26개) 주어지는 단어에 대해서 각 단어 별로 해당하는 알파벳을 켜준다. db -> 1010 za -> 10000000000000000000000001 각 단어를 잊거나 기억하는 조건에 따라 알파벳을 꺼주거나 켜준다..

https://www.acmicpc.net/problem/20437 🐢 설명 하나의 문자열에 대해서 두가지 조건에 부합하는 문자열의 길이를 구하는 문제이다. 일단 첫번째 조건이 부합하지 않으면 2번째 조건도 부합하지 않으므로 첫번째 조건만 확인해서 -1을 출력할지 값을 출력할지 해주면된다. 조건을 체크하는 방법 먼저 문자열 전체를 순회하면서 알파벳 별로 등장한 인덱스를 담아준다. 각 알파벳 리스트를 확인하면서 크기가 조건에서 제시한 개수보다 많다면 확인해준다. 확인할 때는 슬라이드 윈도우 방식으로 확인한다. 슬라이드 윈도우 방식 인덱스를 left, right 값으로 갖게하고 right 값을 증가시킨다 right - left + 1이 K (특정 알파벳이 포함된 개수) 라면 그때의 값을 최소값과 최대값으로 ..

https://www.acmicpc.net/problem/17472 🐢 설명 2차원 맵에 있는 섬들을 직선의 다리를 놓아서 연결하되 다리의 총 길이가 최소가 되도록 하는 문제이다. 모든 섬들을 구분해서 번호를 맺기 위해 DFS를 사용했다. 만들수 있는 모든 다리를 만들고 다리를 비용이 낮은 순으로 탐색하기 위해 우선순위큐를 사용했다. 각 모든 섬들을 다리로 묶어서 연결됨을 나타내기위해 union-find를 사용했다 우선순위 큐에 담긴 모든 다리를 하나씩 확인하면서 해당 다리가 잇는 섬이 이미 연결되었는지 안되었는지를 확인하고, 연결이 안되었다면 연결시키고 다리비용을 추가시켰다. 마지막으로 모든 다리에 대해 비교를 끝내고 모든 섬들의 부모를 확인해서 하나라도 다른 섬이 있다면 연결되지 않았다고 판단했다. ..

https://www.acmicpc.net/problem/13904 🐢 설명 디데이와 포인트가 있는 숙제들에 대해서 가장 높은 점수를 얻었을 때 그 점수를 구하는 문제이다. 먼저 점수를 가장 우선적으로 정렬하고, 점수가 같다면 날짜가 빠른게 더 우선하도록 정렬을 한다. 날짜를 기준으로 하지 않는 이유는 d-1, 1 d-2, 2 d-3, 100 d-3, 100 이 있을 때, d-1, d-2, d-3을 푸는것보다 d-2, d-3, d-3을 푸는게 더 이득이기 때문에 날짜가 아니라 점수를 우선적으로 정렬하는 것이다. 이후 점수가 같으면 날짜가 더 빠른걸 우선하게 하면된다. 모든 숙제들중 가장 늦게 풀수있는 숙제의 d-day 만큼의 숙제를 풀 날짜에 해당하는 배열을 만들어준다. 정렬된 숙제들에 대해서 우선순위대..

https://www.acmicpc.net/problem/13422 🐢 설명 N개의 집을 연속적으로 M번 골라서 K원 미만의 금액이 되는 조합을 구하면 되는 문제이다. 집들이 원형 구조라서 N-1번집은 0번집과 연결되어있다는 점과 N과 M이 동일할 경우 N개의 집에서 연속적으로 M개를 고르는 조합은 모두 동일하다는 점을 주의하면 된다. 예를들어 집이 3개가 있고 연속적으로 3개의 집을 털어야하는 경우를 생각해보자. A B C의 집을 돈다면 1) A -> B -> C 2) B -> C -> A 3) C -> A -> B, 총 3가지 경우가 존재한다. 하지만 결국 턴 집은 A, B, C로 동일한 조합이므로 이를 처리해 줘야한다. 그래서 N == M 인 경우만 예외로 빼주고 나머지는 투포인터로 고른 집이 M개..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 🐢 설명 너무 어려운 트리문제를 맞닥뜨리고 충격을 먹고 골드 하위 문제 트리 문제를 풀려고 했다. 이 문제는 LCA 유형의 문제로 최단거리내 공통 조상을 찾는 문제이다. 문제접근은 먼저 인접리스트를 이용해서 부모 -> 자식의 단방향 그래프를 그리고, 추후 자식들이 부모를 찾아 올라가는 과정을 위해서 (자식 - 부모) 쌍의 map을 사용했다. ro..

https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 🐢 설명 DP문제이다. 동전 문제처럼 접근하면 될거같지만 조금 다른점이 있는데 금액별 동전들에 대해 개수제한이 있다. 따라서 각 동전별로 개수 내에서 M원까지의 금액에 대해 갱신을 해줘야한다. 개수제한이 없다면 1 ~ M원까지 모든 동전들을 비교하면 되겠지만 개수를 확인해줘야 하므로 2차원 배열을 만들어서 동전번호 별로 DP를 괸리하도록 하자. 먼저 A원동전이 A원을 나타내는 방법..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 🐢 설명 다이나믹 프로그래밍 문제로 N번째 결과를 구하기 위해 N - 1번째 결과를 구하는 점화식이 필요하 문제이다. 이런 DP문제는 테이블을 만들어서 접근하는 것이 가장 좋으며 메모이제이션 기법을 활용해야한다. N개의 동전으로 M원을 만들기 위한 가짓수를 출력하는 문제이므로 DP[M] : M원을 만들 수 있는 총 가짓수 형태로 풀어보자. 2, 3, 5원 동전이 존재하고 만들려는 ..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🐢 설명 DP문제를 열심히 풀어야 겠다고 생각했다. 문제는 간단한데 점화식을 떠올리는게 쉽지 않았다. N, K가 주어질 때 1 ~ N의 수가 있고 K개를 뽑아서 더해서 N을 만들어야 하는 문제이다. 이를 점화식을 나타내보자면 K개를 골라서 N을 나타내야 하므로 DP[K][N]으로 나타낼 수 있다. 즉, DP[K][N] : 1 ~ N의 수 중에서 K개를 뽑아서 더했을 때 N인 경우의 수 가된다. 이를 이용해서 점화식을 구해보면 DP[K-1][N] + 0 = DP[K][N], DP[K-1][N - 1] + 1 = DP[K][N..

https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 🐢 해설 먼저 빌딩과 도로가 존재하고 양방향이며 도로의 비용이 1로 고정되어 있으므로 해당 간선과 정점을 가지고 각 빌딩에 대해서 다른 모든 빌딩에 대한 거리 최소 비용을 구해야한다. 이후 구한 거리값을 가지고 어디에 치킨집을 차렸을 때(2개로 고정) 모든 빌딩의 왕복 합이 낮은지 구하면 된다. 특정 빌딩이 아니라 모든 빌딩에 대해 최소 거리값을 구해야 하므로 플로이..

https://www.acmicpc.net/problem/22255 22255번: 호석사우루스 (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (3, 4) -> (4, 4) -> (5, 4) -> (5, 5) 8번 만에 갈 수 있고 이게 최소이다. www.acmicpc.net 🐢 해설 방문처리가 복잡했던 문제였다. 무엇보다 첫번째 시작이 1번이고 이동하는 횟수 N번이 3N, 3N + 1, 3N + 2에 따라서 이동할 수 있는 방향이 달라지는 것이 중요했다. -> 이동횟수 별 탐색 방향 : (N % 3 == 1 : 상하, N % 3 == 2 : 좌우, N % 3 == 0 : 상하좌우) 한번 방문 했다고 바로 방문 처리를 하면 안될 뿐더러 특정 방향을 가질때 어디로 ..