문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 얼리 아답터가 아닌 사람은 자신의 친구가 모두 얼리 아답터인 경우에 아이디어가 전파되는 상황에서 얼리 아답터의 최소 수를 구하는 문제였다. 문제 풀이 처음에 u - v의 관계가 항상 u가 부모, v가 자식이라고 생각하고 단방향 그래프를 만들어 풀었는데 그게 아닐수도 있었다. 처음의 풀이는 루트 노드를 찾은 다음 레벨 별 순회를 하며 해당 서브트리의 dp를 갱신해줬다. 하지만 무방향 그래..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/1831 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N을 만들 수 있는 경우의 수를 구하는 문제였다. *++이 3단고음이고 *은 3을 곱하기, +는 1을 더하기이다. 3단고음 중간에 3단 고음을 실행할 수 있다. 문제 풀이 처음에 1에서 시작해 N을 만드는 방법으로 했는데, 시간 초과가 계속 났고 풀이를 참고해서 다시 풀었다.. N부터 시작해서 1까지 도달하게 했고, *는 3으로 나누기, +는 3으로 나눈 나머지를 빼도록 했다. 3으로 나눠진다..
문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 진행하면서 움직일 수 있는 동전의 최대 횟수를 구하는 문제였다. 문제 풀이 많은 시행착오가 있었고, 결국 다른 블로그를 참고해서 해결했다. 처음에는 단순히 백트래킹을 이용했는데, 6%에서 시간 초과가 나타났다. 이를 해결하기 위해서 좌표와 횟수, 방향 정보를 우선순위 큐에 넣어 bfs를 돌렸는데 해결되지 않는 경우가 있었다. 그리고 map의 각 칸에 set을 만들어 이전에 방문한 적이..
문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 각 레벨의 양 끝 노드간의 거리 중 최댓값을 구하는 문제였다. 문제 풀이 처음에는 트리 노드에 달려 있는 노드들의 합으로 위치를 계산하려고 했는데, 중위순회를 하면 순회하는 순서가 위치가 될 것 같아서 다시 풀었다. 1번 노드의 parent를 계속 거슬러 올라가 루트 노드를 찾는다. 루트노드에서부터 중위순회를 돌려 각 노드의 위치를 찾는다. 트리를 레벨 별로 순회를 ..
문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기상어가 최대 몇 초 동안 물고기를 먹을 수 있는지 구하는 문제였다. 문제의 조건은 다음과 같았다. 아기상어는 크기가 작은 물고기만 먹을 수 있다. 크기가 같은 물고기일 경우 지나갈 수 있다. 먹을 수 있는 물고기 1마리 → 먹으러 감 먹을 수 있는 물고기 2마리 이상 → 거리 가장 가까운 물고기 거리 : 지나야 하는 칸 개수 최솟값 가까운 물고기가 많으면 가장 위, 위인 물고기도 ..
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1초마다 먼지가 확산되고 공기청정기가 가동되는 상황에서 T초 후의 방 안에 남은 먼지 개수를 구하는 문제였다. 문제 풀이 문제에서 요구하는 대로 구현하기만 하면 되는 문제였다. 1초마다 먼지가 확산되는 메서드와 공기청정기가 가동되는 메서드를 실행시키고, T초가 끝난 후에 map에 있는 먼지를 다 더해준 것이 답이었다. #define _CRT_SECURE_NO_WARNINGS #include..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카드 게임을 진행해서 게임에서 도달 가능한 최대 라운드 수를 구하는 문제였다. 문제 풀이 게임을 진행하면서 카드를 살 수 있는 경우에 바로 사거나 보류하도록 했다. 각 카드의 상대 숫자의 라운드가 0일 때는 코인이 1개가 필요하고, 현재 라운드보다 작거나 같을 때에는 코인이 2개가 필요하다. 상대 카드가 현재 라운드보다 큰 라운드에 위치해 있다면 아직 살 수 없다. coin 1개 필요 ->..
문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 각 도시별 홍보 비용과 이 비용으로 유치할 수 있는 고객이 정해져 있을 때, 호텔 고객을 C명 이상 늘리기 위해 투자해야 하는 비용의 최솟값을 구하는 전형적인 DP 문제였다. 문제 풀이 점화식을 세워서 dp 값을 계속 갱신했다. i는 비용이고 각 dp[i]의 값은 해당 비용으로 늘릴 수 있는 최대 사람 수로 정했다. 이때 dp 값이 C 이상일 때의 i가 정답이 된다. dp[i] = max..
