CEO

문제 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 풀이 각 노드의 간선 정보가 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드를 파악하 한 후, 이와 같은 거리를 가진 노드가 몇 개인지 반환하는 문제이다. BFS를 통한 그래프 탐색을 이해하고 있다면 쉽게 풀 수 있는 문제이다. 그래프의 간선 정보를 하나의 리스트에 초기화 한다. 예를 들어, 1번 노드에서 2번 노드가 접근 가능하다면, `graph[1].append[2]`와 같이 진행하면 된다. 리스트 인덱스에 접근하기 위해 node들에 -1을 하여 처리하였다. 그래프는 양방향이므로, `graph[1].append[2..

문제 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 풀이 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 모든 섬이 통행 가능한 최소 비용을 구하는 문제이다. 이 문제는 전형적인 `Kruskal 알고리즘` 문제이다. 해당 알고리즘 자체가 사이클을 이루지 않고, 최소 비용을 찾는 것이다. 이와 마찬가지로 문제에서도 "다리를 여러 개 건너더라도 해당 섬에 방문할 수 있으면 된다."라는 조건이 주어진다. 따라서 각 노드의 비용(건설하는 비용)을 기준으로 정렬한 후, 방문 여부에 따라 현재의 비용을 갱신하면 된다. 주어진 예시를 Kruskal로 탐색하게 되면 위의 그림과 같은 순서로 탐색하게 된다. 따..

문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 문제 풀이 4열로 이루어진 땅이 주어질 때, 한 행에서 1열의 땅을 밟았다면 그다음 행에서는 1열의 땅을 밟을 수 없다는 조건이 있다. 이는 다음과 같이 땅의 값들을 변경시켜 줌으로써 가능하다. 다음 땅에서 획득할 수 있는 점수는 그림과 같이 다음 땅에 선택할 인덱스를 제외한 나머지에서 최대 값을 반환하여 더해주면된다. 이런식으로 값을 중첩해 나아가면 16이라는 최대값을 찾을 수 있다. 코드 def solution(land): for..

문제 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호� programmers.co.kr 문제 풀이 문자열이 주어질 때, 올바른 괄호인지 판단하여 true, false를 반환하는 문제이다. 예를 들어 `(())`는 올바른 괄호이고, `(()`는 올바르지 않은 괄호이다. 문제를 해결하기 위해서는 다음과 같은 로직에 따라 처리하면 된다. stack push. : 현재 문자열이 열린 괄호 stack pop : stack에 값이 있고, 현재 문자열이 닫힌 괄호 이외의 경우는 올바른 괄호가 아니므로, False를 반..

문제 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으� www.acmicpc.net 문제 풀이 (0, 0)에서 출발하여, (m - 1, n - 1)에 도착하는 경우의 수를 구하는 문제이다. 문제의 조건은 더 낮은 지점으로만 이동할 수 있으며, 가능한 경우의 수를 모두 구하여야 한다. 이 문제를 풀기 위해 단순히 BFS, DFS를 사용하면 각 경로를 탐색하기 위해 중복으로 탐색할 가능성이 크다. 따라서, 재귀 호출을 통해서 방문 가능한 경로의 수를 반환하고, 한번 탐색한 경로는 더 이상 탐색하지 않도록 하는 방법을 사용하여야 시간 초과를 발생시..

문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 문제 풀이 이전에 다룬 단지번호붙이기, 섬의 개수와 유사한 문제이다. 다른 점이 있다면 비가 오는 양에 따라 침수되는 지역이 달라지며, 그로 인해 안전 영역의 개수가 변동된다는 것이다. 문제를 풀기 위해서는 BFS로 탐색을 하되, 높이가 가장 낮은 곳이 침수될 때부터, 가장 높은 곳이 침수될 때까지 BFS를 탐색하여 영역의 개수를 구하고 최대 값을 반환하면 된다. 3중 반복문을 통해 BFS를 호출한다. 첫 번째 반복문 : 가장 낮은 높이 ~ 가장 높은 높이 두..

문제 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 풀이 현재 값을 더하느냐, 빼냐에 따라 2 가지로 나뉘게 된다. 이는 DFS를 통해 탐색할 경우 각 경우에 대해 판단할 수 있다. 각 노드 마다 2개의 가지로 뻣어나가게 되므로, 트리의 최대 depth(숫자의 수) 만큼 도달 하였을 때, 계산 된 값과 target과 일치하는지 확인하여 문제를 해결할 수 있다. 코드 def dfs(numbers, target, i = 0): answer = 0 if ..

문제 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 문제 풀이 네트워크의 정보가 주어질 때, 연결 정보를 통해 몇 개의 네트워크가 존재하는지 판단하는 문제이다. BFS로 풀 수 있는 문제이며 다음과 같이 풀 수 있다. 예제 #1 노드 1은 2번과 연결되어 있다. 노드 2는 1번과 연결되어 있다. 노드 3은 다른 노드와 연결되어 있지 않다. 따라서 네트워크의 개수는 2이다. 예제 #2 노드 1, 2, 3은 서로 연결되어 있다. 따라서 네트워크 개수는 1이다. 이와 같은 연결에 따라 네트워크 개수를 체..