[240509] 코딩테스트 문제풀이

1. 네트워크 (⭐️복습하기)

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

def solution(n, computers):

    def dfs(v) :
        visited[v] = True
        for i in range(n) :
            if not visited[i] and computers[v][i] == 1 :
                dfs(i)
    count = 0
    visited = [False] * n
    for j in range(n) :
        if not visited[j] :
            dfs(j)
            count += 1

    return count

 

---

2. 정수삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

def solution(triangle):
    dp = [[0 for i in range(len(triangle))] for _ in range(len(triangle)) ]
    # 점화식 초기화
    dp[0][0] = triangle[0][0]


    for i in range(1,len(triangle)) :
        for j in range(0,i+1) :
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]


    return max(dp[-1])

 

---

3.  야근지수

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

 

시간초과 

def solution(n, works):
    for i in range(n) :
        max_number = max(works)
        max_index = works.index(max_number)
        works[max_index] = max_number - 1
        if works[max_index]  < 0 :
            works[max_index]  = 0

    answer = 0
    for j in range(len(works)) :
        answer += works[j] * works[j]
    return answer

 

 

---

 

4. 등굣길

• dp 문제 풀 때 유의할 것 : 인덱스 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ행 인덱스 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 열 인덱스 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

def solution(m, n, puddles):
    dp = [[0 for _ in range(m+1)] for i in range(n+1)]

    dp[1][1] = 1

    for i in range(1,n+1) :
        for j in range(1,m+1) :
            if i == 1 and j == 1: continue
            if [j,i] not in puddles :
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007

            else :
                dp[i][j]= 0
    return dp[-1][-1]

 

 

---

5. 기지국

시간초과...

https://school.programmers.co.kr/learn/courses/30/lessons/12979

프로그래머스

import math
def solution(n, stations, w):
    S = [True for i in range(n)]

    for i in stations :
        st_point =  int( i-1 - w )
        end_point = int (i-1 + w )
        if st_point <= 0 : st_point = 0
        if end_point >= n : end_point = n-1
        for j in range(st_point, end_point+1) :
            S[j] = False
    answer = []
    k = 0
    while k < n :
        stack = []
        while S[k] != False :
            stack.append(k)
            k += 1
            if k == n :
                break
        lenght = len(stack)
        if lenght != 0 : answer.append(lenght)
        k += 1

    count = 0

    for i in answer :
        count += math.ceil(i / (w*2+1))


    return count

import math
def solution(n, stations, w):
    distance = list()
    # 기지국과 기지국 사에의 거리 append
    for i in range(1,len(stations)) :
        distance.append((stations[i]-w-1) -(stations[i-1]+w))

    # 처음에서 - 최초 기지국 사이의 거리
    distance.append(stations[0] - w - 1 )
    # 끝에서 - 마지막 기지국 사이의 거리
    distance.append(n - (stations[-1] + w ))
    result = 0

    for i in distance :
        if i <= 0 : continue
        result += math.ceil(i/((w*2)+1))
    return result

 

---

6. 멀리뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

def solution(n):
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    dp[1] = 1


    if n>= 2:
        for i in range(2,n+1) :
            dp[i] = ( dp[i-1] + dp[i-2] ) % 1234567

    return dp[-1]

 

---

7. 예상대진표

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

def solution(n,a,b):
    answer = 0
    while a!=b :
        if a%2 == 0 :
            a = a//2
        else :
            a = a//2 + 1
        if b%2 == 0 :
            b = b//2
        else :
            b = b//2 + 1
        answer += 1

    return answer

print(solution(8,4,7))