![]()
문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 설명 문제 초반에는 단순하게 dfs를 진행해서 최대로 갈 수 있는 칸 수를 기록하면서 진행했다. 골드 3치고 문제가 너무 쉽다고 생각했는데, 34% 정도에서 시간초과가 발생했다. 생각해 보면 당연하다. 최대 배열 크기가 500이고, 500x500을 계속해서 무식하게 탐색하면 시간초과가 나는 건데 왜 이 생각을 못했을까. 그렇다면 수정해야 될 것은 탐색을 하는 범위라고 생각했다..
![]()
📕문제 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 🔎문제설명 bfs 문제에서 조금 변형이 있는 문제입니다. 스위치를 켜면 해당 방으로 이동할 수 있는 것이 아닌, 스위치를 켜고 스위치로 이동가능한지 여부를 판단해야 하는 문제입니다. 다른 bfs문제처럼 바로바로 큐에 넣는 것이 아닌 여부를 판단하고 큐에 넣어야 하기에 헷갈릴 여지가 있다고 생각합니다. 주의할 점은 (1,1)은 원래 불이 ..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 풀이 해당 문제를 풀 기전에 유일성과 최소성을 설명하고자 합니다. 💡유일성? 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다. 위 테이블에서 칼람을 유일하게 식별할 수 있다면, 그 칼럼은 유일성이 있다고 합니다. 학번을 보면 모든 값들이 다 다른 것을 알 수 있습니다. 따라서 해당 테이블에서 학번을 통해서 유일하게 식별할 수 있습니다. 이러한 칼럼 학번은 유일성을 만족한다..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 두 집합은 큐라는 특성을 가지고, 두 집합의 원소의 합이 서로 같아질 때까지 몇 번 연산해야 하는지 구해야 합니다. 여기서 연산은 pop과 insert 한번입니다. 우선 설명을 쉽게 하기 위해서 queue1을 F, queue2를 S, queu1의 원소합을 f, queue2 원소의 합을 s라고 하겠습니다. 당연하게도! F와 S의 합이 홀수라면 절대로 두 집합의 합은 같아질 수가 없..
![]()
📕문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 🔎문제설명 모든 사회망 구성원들이 아이디어를 받아들일 수 있게끔 하기 위해 필요한 최소한의 얼리어답터의 개수를 구해야 한다. A가 얼리어답터가 되기 위해서는, A의 친구들이 모두 얼리어답터여야 합니다. 즉 A와 연결된 모든 정점들이 얼리어답터여야합니다. 기본적인 DFS는 리프노드까지 진행한 후 과정을 진행하기에, 리프노드에서부터의 작업을 진행해야 합니다. ..
![]()
📕문제 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개가 모..
