데구리 블로그

문제 링크 www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 현재 클립보드에 들어있는 이모티콘의 개수와, 화면에 나타난 이모티콘의 개수를 바탕으로 상태를 정의합시다. $d[clip][screen]$: 클립보드에 $clip$개, 화면에 $screen$개 이모티콘이 있을 때 시간의 최솟값입니다. 한 상태에서 갈 수 있는 다른 상태가 명확합니다. 1) $clip$을 $screen$으로 변경 2) $screen$을 하나 삭제 3) $screen$을 $clip$만큼..

문제 링크 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 풀이 예제 설명을 색깔별로 친절하게 그려준 게 아마 큰 힌트가 되지 않을까 싶습니다. 1) 사다리를 쓰지 않고 이동할 수 있는 정점별로 그룹을 만들어줍니다. BFS, DFS 상관없습니다. 2) 위 그룹핑을 바탕으로 그래프를 재구성할 수 있습니다. 각 그룹을 정점으로, 그룹과 그룹 사이 사다리의 ..

문제 링크 www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 풀이 간단한 트리 DP 문제입니다. 1) 만약 현재 정점을 고르면 -> 자식들은 골라도 되고, 안골라도 됩니다. 2) 만약 현재 정점을 고르지 않으면 -> 모든 자식들을 골라야 합니다. $d[now][k]$를 k가 0일때 안고름, 1일 때 고르는 상황의 최솟값이라고 합시다. now의 모든 자식 next에 대해 $d[now][0] = \text{sum}(d[next][1])$ $d[now][1] ..

문제 링크 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 예제 2번으로 시뮬레이션해봅시다. 1번 비행기) 2번 게이트가 비어 들어갈 수 있습니다. 2번 비행기) 2번 게이트가 비어있지 않아 그 앞의 1번 게이트로 들어갑니다. 3번 비행기) 3번 게이트가 비어있어 들어갈 수 있습니다. 4번 비행기 3번, 2번, 1번 게이트가 모두 비어있지 않아 끝나게 됩니다. 문제를 풀어봅시다. 게이트의 수가 10만이라 그냥 시뮬레이션..

문제 링크 www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 풀이 1) 1부터 x 이하 모든 수의 1의 개수를 구해주는 함수 go를 구현합시다. 2) go$(B)$ - go$(A-1)$ 를 구해주면 됩니다! 이제 go함수를 만드는 방법을 알아봅시다. 1. 누적합 구하기 우선 최상위 비트가 $i$번 이하인 모든 수의 1의 개수의 합을 누적합으로 구해줘야 합니다. 편의상 $i$는 0부터 시작한다고 합시다. 이를 어떻게 구할 수 있을까요? ..

문제 링크 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 방향성 있는 그래프가 만들어집니다. 1) indgree가 0인 모든 배열을 큐에 넣어줍니다. 2) 위상 정렬을 돌립니다. 3) 어떤 팀에 속한다는 말은 곧 그래프에서 사이클을 이룬다는 말과 같습니다. 위상 정렬이 끝난 뒤 방문하지 못한 정점이 있다면, 그 정점은 사이클을 이룬다는 뜻입니다. 그러므로 위상 정렬 과정 중 방문한 정점의 개수를 출력해주면 됩니다. 정답 코드 #include using na..

문제 링크 www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 범위가 작아 무슨 짓을 해도 풀 수 있습니다. 1) 저는 bfs를 여러 번 돌려서 풀었는데, 매번 시작할 수 있는 시작점에서 출발해 갈 수 있는 데까지 가줍니다. 이 시작점은 현재 갖고 있는 열쇠 현황에 따라 달라지기 때문에 매번 새로 구해주어야 합니다. 2) 탐색 중 열쇠를 먹었다면 업데이트하고, 그 열쇠로 열 수 있는 문은 다음번 bfs에서 통과할 수 있게 됩니다. 이런 방식으로 더이상 서류나 열쇠를 먹..

문제 링크 www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 각 앱별로 사용 중인 메모리 $m$, 비활성화 했을 경우 비용 $c$가 주어집니다. 일반적으로 생각했을 땐 메모리의 모든 범위에 대해 최소 비용을 구하는 배낭 dp인데, 메모리의 범위가 너무 커 배열로 잡을 수 없습니다. 관점을 좀 달리하여 모든 비용에 대해 확보할 수 있는 최대의 메모리를 구해줍시다. 비용의 범위는 최대 100이므로 충분히 가능합니다. 그 후 비용 0부터 올라가며 우리가 필요한 메모리..

문제 링크 www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 $a+b+c+d = 0$인 조합의 개수를 찾아야합니다. 나이브하게 풀면 $O(N^4)$의 복잡도로 통과하지 못합니다. 1) 이를 $a+b = -(c+d)$로 생각하여 양 변을 따로 봅시다. 각각 $(a+b)$, $(c+d)$의 모든 조합을 구하는데 $O(N^2)$의 복잡도가 듭니다. 2) $a+b$ 배열의 각 원소마다, $c+d = -(a+b)$를 만족하는 $c+d$ 조합의 수..

문제 링크 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 점이 10만 개입니다. 이론상 모든 점을 연결할 수 있으므로 완전 그래프 꼴이긴 합니다. 간선이 너무 많은 것만 빼면 전형적인 최소 스패닝 트리 문제입니다. 근데 잘 생각해보면 굳이 모든 간선을 볼 필요가 없습니다. 우리는 최소 스패닝 트리를 만들거니까 축별로 정렬 후 이웃한 점끼리만 간선을 맺어주면 됩니다. 이게 왜 되는지 그림으로 살펴봅시다. 어떤 한 축만 고..