모서리 IT 블로그

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

내 문제풀이

1. 현재 컴퓨터와 연결된 컴퓨터가 있는 경우, 해당 컴퓨터와 연결된 다른 컴퓨터를 계속해서 탐색하기 위해서 DFS를 사용했다. DFS는 stack, 재귀함수를 활용한다.

2. 네트워크 갯수를 계산하는 answer, 연결된 컴퓨터를 표시하기 위한 stack을 초기화한다.

3. 0번 컴퓨터부터 각 컴퓨터별 네트워크를 확인하기 위해 반복문을 수행한다. 반복문 내에서는 dfs() 함수를 호출한다. 
예외처리로는 2가지 경우를 구현했다.
- 현재 컴퓨터 번호가 stack에 표시되어 있다면, 이미 네트워크에 포함되어 있다는 것이기 때문에 dfs() 를 호출하지 않고 continue를 수행한다. 
- stack의 값이 모두 1이라면, 바로 answer를 반환한다.

4. dfs() 함수는 다음의 총 4개의 인자를 받는다.
n(총 컴퓨터 갯수), idx(현재 컴퓨터 번호), computers(컴퓨터 연결 정보 배열), stack(연결된 컴퓨터 표시)
해당 함수는 현재 컴퓨터와 연결되어 있으며, stack에 표시되지 않은 컴퓨터가 있는 경우를 탐색한다. 이 경우, 새로운 컴퓨터를 stack에 표시하고 해당 컴퓨터 번호로 dfs()를 다시 호출한다. 마지막에는 stack을 반환한다.

5. solution()에서 dfs()를 반복 호출하고, dfs() 내에서 재귀적으로 수행하다보면, 최종 결과 값이 반환된다.

내 코드-파이썬

def dfs(n, idx, computers, stack):
    for i in range(0, n):
        if computers[idx][i]==1 and stack[i]==0: #연결되어 있고, stack에 표시 x
            stack[i] = 1
            dfs(n, i, computers, stack)
    return stack

def solution(n, computers):
    answer = 0 #네트워크 갯수
    stack = [0]*n #연결된 컴퓨터 표시
    for c in range(0, n): #각 컴퓨터별 네트워크 확인
        if stack[c] == 1: continue
        if sum(stack)==n: return answer
        answer += 1        
        stack = dfs(n, c, computers, stack)
        
    return answer

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

내 문제풀이

1. numbers 배열의 각 숫자마다 +와 -를 사용한 모든 계산을 수행하기 위해 재귀함수를 활용한 DFS를 구현한다.

2. dfs함수의 인자로는 (numbers 배열의 숫자를 선택할 index, 차례대로 계산 중인 결과 값, numbers, target) 이다.

3. 재귀함수를 호출할 때마다 index는 1씩 증가시키고, 계산은 각 숫자를 + 또는 -하여 수행한다.

4. index가 numbers의 길이와 같아지면 numbers의 모든 숫자를 사용한 것이므로 현재까지의 계산 결과가 target과 같은지 확인하고 해당 함수 주기를 return 0으로 종료한다.

5. 만약 현재까지의 계산 결과가 target과 같다면 answer(타겟 넘버 생성할 수 있는 방법의 수)를 +1 한다.

내 코드-파이썬

answer=0

def dfs(idx, cur, numbers, target):
    global answer
      
    if idx==len(numbers):
        if cur == target:
            answer += 1
        return 0
    
    dfs(idx+1, cur+numbers[idx], numbers, target)
    dfs(idx+1, cur-numbers[idx], numbers, target)

def solution(numbers, target):
            
    dfs(0, 0, numbers, target)
    return answer

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

내 문제풀이

1. 위 처럼 패턴을 갖고 5를 4번 사용하는 경우 -> 1번 사용&3번 사용, 2번 사용& 2번 사용, 3번 사용&1번 사용 값을 활용한다.

2. n번 사용할 경우 n//2번을 넘어가면 이전 계산과 중복되므로 1~n//2+1 번까지 반복문을 수행한다. 반복문 내에서는 위의 패턴대로 각 숫자의 사용 횟수별 사칙연산을 수행한다.

3. 계산한 사칙연산 리스트에 number가 있다면 몇 번 사용했는지의 값(i)를 반환한다.

4. 계산한 사칙연산 리스트에 number가 없다면 다음 횟수 계산을 위해 total에 계산한 값 리스트(num_list)을 추가해준다.

5. 최솟값이 8보다 클 수 없다고 제한 조건을 주었기 때문에 반복문 내에서 정답이 반환되지 않으면 -1을 반환한다.

내 코드 - 파이썬

def solution(N, number):
    total = [0, [N]] # 사용횟수 별 계산 값 저장 리스트
    if N==number: return 1

    for i in range(2, 9):
        num_list = [int(str(N)*i)] # 단순 반복 값 초기화
        for j in range(1, i//2+1):
            for a in total[j]:
                for b in total[i-j]:
                    num_list.append(a+b)
                    num_list.append(a*b)
                    num_list.append(a-b)
                    num_list.append(b-a)
                    if a!=0 : num_list.append(b//a)
                    if b!=0 : num_list.append(a//b)
        if number in num_list : return i
        total.append(num_list)
    
    return -1

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

입출력 예 설명

내 문제풀이

1. 웅덩이를 피해서 되돌아가는 경우 없이 오른쪽 또는 아래로만 이동하면 모두 최소 이동 경로가 된다.

2. 집의 위치 값을 1로 두고, 각 격자의 칸마다 해당 칸으로 도착하는 서로 다른 경로(위쪽에서 아래로 오는 경우, 왼쪽에서 오른쪽으로 오는 경우)의 갯수를 저장한다.

3. 위쪽, 왼쪽에서 해당 칸으로 올 수 있으므로 위쪽, 왼쪽의 값을 더하며 격자를 채워나간다.

4. 웅덩이로 도착하는 경로는 없으므로 0으로 저장한다.

내 코드 - 파이썬

def solution(m, n, puddles):
    matrix = [[0 for i in range(m+1)] for i in range(n+1)]
    matrix[1][1] = 1
    
    for r in range(1, n+1): #행 = n
        for c in range(1, m+1): #열 = m
            if matrix[r][c] == 1: #집
                continue
            if [c, r] in puddles:
                matrix[r][c] = 0
            else:
                matrix[r][c] = matrix[r-1][c] + matrix[r][c-1]   
            
    return matrix[-1][-1]%1000000007

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

내 문제풀이

1. 집이 원형으로 배치되어 있기 때문에 단순하게 바로 옆 집을 털면 안되는 조건만 고려하면 안되고, 첫 번째 집과 마지막 집을 동시에 털 수 없는 점도 고려해야 한다.

2-1. 먼저 첫 번째 집을 제외하고 마지막 집을 포함하는 경우 첫 번째 집의 돈을 0으로 설정해둔다. 따라서 두 번째 집의 돈도 입력값대로 설정한다. 

2-2. 세 번째 집부터 반복문을 돌며 바로 전 집의 돈 vs 전전 집의 돈+현재 집의 돈을 비교하여 큰 값을 저장한다.

3-1. 마지막 집을 제외하고 첫 번째 집을 포함하는 경우 첫 번째 집의 돈은 입력값대로 설정한다. 그리고 두 번째 집은 첫 번째 집의 돈과 두 번째 집의 돈 중 큰 값으로 설정한다.(첫 번째 집의 돈이 큰 경우 첫 번째 집을 털고 두 번째 집은 털지 않는 것)

3-2. 2-2와 같은 로직으로 len(money)-1만큼만 반복문을 수행하여 마지막 집은 계산하지 않는다.

4. 첫 번째 집을 제외한 경우, 마지막 집을 제외한 경우 중 큰 값을 반환한다.

내 코드 - 파이썬

def solution(money):
    
    # 마지막 집 포함 -> 첫 번째 집 제외
    x1 = [0]*len(money)
    x1[0] = 0
    x1[1] = money[1]
    
    for i in range(2, len(money)):
        x1[i] = max(x1[i-1], x1[i-2]+money[i]) 
        
    # 첫 번째 집 포함 -> 마지막 집 제외
    x6 = [0]*(len(money)-1)
    x6[0] = money[0]
    x6[1] = max(money[0], money[1])
    
    for i in range(2, len(money)-1):
        x6[i] = max(x6[i-1], x6[i-2]+money[i]) 
    
    return max(x1[-1], x6[-1])

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

내 문제풀이

1. 삼각형의 위에서 아래로 내려가면서, 바로 윗 level의 대각선 왼쪽/오른쪽 값 중 큰 값을 현재 위치 값에 더한다.

2. 현재 위치가 현재 level의 가장 왼쪽인 경우에는 바로 윗 level의 대각선 왼쪽이 없고, 현재 위치가 현재 level의 가장 오른쪽인 경우에는 바로 윗 level의 대각선 오른쪽이 없다. 따라서 이 경우에는 직접적으로 윗 level 값 하나를 넣어준다.(반복문의 if, elif 문)

3. 2번의 경우가 아닌 경우에는, 바로 윗 level의 대각선 왼쪽/오른쪽 값 중 큰 값을 더한다.

4. 결국 삼각형의 위에서 아래로 내려오며 계산된 값이 triangle의 가장 마지막 level에 모이게 되며, 따라서 triangle[-1] 중 가장 큰 값을 반환한다.

내 코드 - 파이썬

def solution(triangle):
    
    for i in range(1, len(triangle)):
        for j in range(0, i+1):
            if j == 0: //현재 위치가 현재 level의 가장 왼쪽인 경우
                triangle[i][j] += triangle[i-1][j]
            elif j == i: //현재 위치가 현재 level의 가장 오른쪽인 경우
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                
    return max(triangle[-1])

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

내 문제풀이

1. 고속도로에서 나간 지점이 가장 빠른 순으로 routes를 정렬한다.

2. 첫 번째 카메라는 정렬한 routes의 가장 첫 번째 차량이 나간 지점에 설치한다. 따라서 설치 카메라 개수(answer)은 1로 초기화를 한다.

3. 두 번째 차량부터 확인하며 반복문을 돈다. 만약 차량이 들어온 시점이 카메라 설치 지점보다 늦다면, 단속카메라와 만날 수 없다. 따라서 해당 경우에 새로운 카메라를 차량이 나가는 시점에 설치해준다.

내 코드 - 파이썬

def solution(routes):
    answer = 1
    routes.sort(key=lambda x:x[1])
    cam = routes[0][1]
    for idx in range(1, len(routes)):
        if (routes[idx][0] > cam):
            cam = routes[idx][1]
            answer += 1        
    
    return answer

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

내 문제풀이

1. costs를 다리 건설 비용 기준 내림차순 정렬을 한다. 그리고 다리가 연결되어 이어진 섬을 1로 표시하는 리스트(island)를 모두 0으로 초기화를 한다.

2. 섬이 모두 연결된 경우인, island의 합이 섬의 갯수일 때까지 반복문을 수행한다.

3. costs의 한 원소에 있는 첫 번째 섬을 A, 두 번째 섬을 B라고 할 때, A와 B가 모두 island에 표시가 되어 있는 경우 무시하고 다음 원소를 확인한다. 

4. 하지만 A와 B 중 하나만 island에 표시가 되어 있는 경우 모두 모든 섬의 통행 가능한 최소 비용(answer)에 해당 원소의 비용을 더하고 island에 섬 A, B를 표시한다.

5. 여기에서 costs 길이만큼 반복하지 않고 while문을 도는 이유, 섬 A, B 모두 island에 없는 경우는 제외한 이유는 각각이 연결된 동 떨어진 섬들이 생기는 것을 방지하기 위해서이다. 이렇게 하지 않는다면, 섬 1-2, 섬3-4-5 와 같이 각각 따로 연결되어 있는 상태에서 해당 함수가 끝나버리게 된다.

내 코드 - 파이썬

def solution(n, costs):
    answer = 0
    island=[0]*n 
    costs.sort(key=lambda x:x[2])
    island[costs[0][0]]=1
    new_island=[]
    
    while(1):
        if sum(island)==n:
            break
        for cost in costs:
            if island[cost[0]] and island[cost[1]]:
                continue            
            elif island[cost[0]] or island[cost[1]]:
                answer+=cost[2]
                island[cost[0]]=1
                island[cost[1]]=1
                break
            
    return answer