전체 글74 [백준] 13549번 숨바꼭질 3 해당 문제의 원문은 여기서 확인하자. 문제 이해 수빈이와 동생이 숨바꼭질을 하고 있다. 현재 수빈이는 점 N, 동생은 점 K에 있을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제이다. 수빈이는 걷거나 순간이동을 할 수 있다. 걷는다면 1초 후에 현재 위치에서 -1 or +1로 이동하고, 순간이동하면 0초 후에 '* 2'로 이동하게 된다. 첫째 줄에 N, K가 주어진다. 제한사항은 다음과 같다. 0 ≤ N, K ≤ 100,000 접근 방식 BFS의 개념을 이용해 문제를 해결하였다. 핵심은 K가 N보다 작은 경우 -1의 이동으로만 접근 가능한 것과 이미 방문했던 지점에 대해선 이동 시간이 더 짧은 경우만 탐색을 진행하는 것이다. 먼저, K가 N보다 작은 경우에 대해서 살펴보.. 2022. 8. 11. [프로그래머스] 가장 먼 노드 해당 문제의 원문은 여기서 확인하자. 문제 이해 n개의 노드가 있는 그래프가 있을 때, 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진(최단경로로 이동했을 때 간선의 개수가 가장 많은) 노드의 개수를 구하는 문제이다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 주어진다. 제한 사항은 다음과 같다. 2 ≤ n ≤ 20,000 1 ≤ 간선의 수 ≤ 50,000 간선은 양방향이다. vertex [a, b]는 a번 노드와 b번 노드에 간선이 있다는 의미이다. 접근 방식 BFS의 개념을 이용해 문제를 해결하였다. 핵심은 재방문을 방지해야 하고 탐색하려는 노드의 범위를 명확히하는 것이다. 예제를 통해 알아보자. 시작 지점은 항상 1번 노드부터이다. 1번 노드와 .. 2022. 8. 9. [백준] 1707번 이분 그래프 해당 문제의 원문은 여기서 확인하자. 문제 이해 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 문제이다. 첫째 줄에 테스트 케이스의 개수 K가 주어지고, 각 테스트 케이스의 첫째 줄에 그래프의 정점 개수 V와 간선 개수 E가 빈 칸을 두고 주어진다. 각 정점은 1번부터 V까지를 번호로 사용하고, 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 입력된다. 제한 사항은 다음과 같다. 2 ≤ K ≤ 5 1 ≤ V ≤ 20,000 1 ≤ E ≤ 200,000 이분 그래프가 맞으면 YES.. 2022. 8. 8. [Suitable_Benefit] 프로젝트를 시작하며 무엇을 할까? 국가근로장학금, 청년정책 등 제공되는 혜택은 다양하지만 알려진 경우가 적거나 자신이 조건에 부합하는지 몰라서 혜택을 제대로 누리지 못 하는 경우가 있다. 이런 점에 착안하여 다양한 혜택들을 쉽게 접할 수 있고 내가 해당 혜택을 받을 수 있는지를 판단해주는 서비스가 있으면 좋을 것 같아 토이프로젝트 형태로 진행해보려 한다. 어떤 식으로 만들까? 해당 서비스의 중점은 내가 받을 수 있는 혜택이 어떤 것이 있는지 쉽게 확인할 수 있다는 것이다. 다음과 같은 문제들을 해결해야 한다. 혜택들은 너무 많은데 뭐가 뭔지 모르겠어 이 혜택 내가 받을 수 있을까? 혜택을 받으려면 어떻게 해야되는 거야? 우선 SNS나 유튜브 형식처럼 혜택에 대한 정보를 제공하여 어떤 혜택들이 있는지 한 눈에 확인할 수 있도.. 2022. 8. 7. [프로그래머스] N으로 표현 해당 문제의 원문은 여기서 확인하자. 문제 이해 다음과 같이 5와 사칙연산만으로 12를 표현할 수 있으며 이 중에서 5를 가장 적게 사용한 경우는 4이다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 이처럼 사용할 숫자 N과 number(만들어야 하는 대상)가 주어질 때 N 사용횟수의 최솟값을 구하는 문제이다. 제한 사항은 다음과 같다. 1 ≤ N ≤ 9 1 ≤ number ≤ 32,000 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시한다. 최솟값이 8보다 크면 -1을 반환한다. 접근 방식 DP의 개념을 이용해 문제를 해결하였다. 위에서 소개한 예제인 5를 이용해 50을 만드는 과정에 대해서 살펴보자. 먼저.. 2022. 8. 4. [프로그래머스] 입국심사 해당 문제의 원문은 여기서 확인하자. 문제 이해 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르며 처음에 모든 심사대는 비어있는 상태이다. 한 심사대에서는 동시에 한 명만 심사할 수 있으며 입국심사를 위해 줄을 서있는 n명 중 가장 앞에 서 있는 사람이 비어 있는 심사대로 가서 심사 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다. 이때 모든 사람이 심사를 받는데 걸리는 최소 시간을 구하는 문제이다. 입국심사를 기다리는 사람 수 n이 주어지고, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어진다. 제한 사항은 다음과 같다. 1 ≤ n ≤ 1,000,000,000 1 ≤ 심사 시간 ≤ 1,000,000,000 .. 2022. 8. 4. 이전 1 ··· 4 5 6 7 8 9 10 ··· 13 다음
