![]()
📕문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 🔎문제 설명 트리의 지름을 구하는 문제입니다. 여기서 트리의 지름이란 가장 먼 거리의 노드를 쫙 늘려서 원형태로 만들면 가장 먼 노드 2개가 양 끝점으로 지름을 이루는 형태가 될 것입니다. 해당 그림에서는 9와 12를 꼭짓점으로 쫙 늘리면 그 경로의 길이가 트리의 지름이 될 것입니다. 이렇게 우리는 각 노드들 사이의 경로의 길이를 구해서, 그 길이가 최댓값이 되는 경우를..
![]()
문제 https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 🔎문제 설명 K의 사촌을 구하는 문제입니다. 사촌의 정의는 이제 부모가 다르지만, 할아버지, 할머니가 같은 사람들입니다. 부모를 저장하기 위해서 parent 배열을 사용했습니다. parent [idx]는 idx의 부모의 숫자가 저장되어 있습니다. 같은 부모인지 아닌지를 판단하기 위해서는 숫자의 차이를 비교하면 알 수 있습니다. 연속된 입력이 아니라면 다른 부모라는 뜻입..
![]()
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 설명 문제가 굉장히 길고 복잡해 보입니다. 하지만 주목해야 할 포인트는 아래와 같습니다. 공기청정기의 열은 고정되어 있습니다. 미세먼지는 4방향으로 확산되고, 인접한 방향에 공기청정기나, 칸이 없다면 확산이 일어나지 않습니다. 확산은 기준 칸의 미세먼지양의 5분의 1이 확산됩니다. 공기청정기의 바람은 바람의 방향대로 한칸씩 이동시키고, 시계방향과, 반시계방향이 있습니다. 먼지를 확산시..
![]()
문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니 다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다. 자연수 N개와 질문 M개가 모..
![]()
문제 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다. 출력 첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다. 🔎문제 해석 DP를 기반으로 해서 다른 알고리즘을 병행하면서 해결했다. DP를 통해서 쓸데 없는 연산을 하..
![]()
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 🔎문제 설명 문제만 보고 이게 DP문제인가? 싶었다. 그냥 무작정 BFS를 사용해서 풀었다. 그랬더니 시간초과가 났다. 이동하는 조건만 맞으면 큐에 넣어줬고, 도착지점에 도착한다면 그게 적절한 이동이라고 생각해서, 결괏값을 계속 더해줘서 함수를 탈출한다면 결과값을 출력해 줬지만 아마 배열 크기도 크고, 큐에 쓸데없는 없는 값이 많이 들어가서 그런 거 같다. 다른 사람들의 풀이를 보니 dfs..
![]()
문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이내믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할 수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📕문제 풀이 무적권을 적절한 라운드에 사용해서 최대한 많은 라운드를 버텨야 한다. 따라서 무적권을 사용하는 라운드를 선정하는 방법이 중요하다! 📗초기 풀이 방식 초기 풀이 방식은 queue에 넣어서, 모든 경우의 수를 탐색했다. 하지만 N의 길이가 커서 시간초과가 났다. 초기 알고리즘은 이렇다. queue에 원소를 계속 넣어서, 만약 가용가능한 병사의 수가 현재 라운드의 적의 수보다 적으면..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 해석 출발점에서 레버를 당겨서 탈출점까지의 최소 경로를 구하는 문제입니다. BFS 알고리즘을 사용해서 쉽게 풀 수 있습니다. 문제는 굉장히 간단합니다..(저는 너무 복잡하게 생각해서 오래 걸렸습니다ㅜㅜ) 문제를 보면 출발정메서 레버로 있는 칸으로 이동하고, 레버를 당긴 후, 탈출점으로 이동하라고 나와 있습니다. 이 문제는 반드시 탈출을 하기 위해서는 레버를 당겨야 합니다. 만약 출발..
