CEO

문제 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 문제 풀이 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해준 순으로 건너려고 할 때, 다리에 올라갈 수 있는 무게 제한이 있다. 트럭은 1초에 다리 한 칸을 지나갈 때, 모든 트럭이 다리를 건너는데 걸리는 시간을 구하는 문제이다. 문제를 풀기 위해서는 다음과 같은 로직을 작성하면 된다. q에 초기 값을 0으로 다리 길이만큼 채운다. 다리에 올라갈 수 있는 트럭을 파악하기 위해, 현재 다리의 무게를 계산한다. 첫 트럭부터 다리 위에 ..

문제 코딩테스트 연습 - 가장 먼 노드 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를 반..

문제 코딩테스트 연습 - 타겟 넘버 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이다. 이와 같은 연결에 따라 네트워크 개수를 체..

문제 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 풀이 특정 단어가 주어질 때, 다른 단어와 비교하여 하나만 다른 경우에 그 단어로 변환할 수 있다. DSF를 통해 처음 시작하는 문자부터, 변활 할 수 있는 문자와 비교하여 두 문자가 하나만 다른 경우 해당 문자를 기준으로 탐색할 수 있는 과정을 반복한다. 이를 위해 `stack`을 이용하고, 중복을 막기 위해 `defualtdict`를 활용하여 방문 여부를 체크하였다. 코드 from collections i..