문제 : https://programmers.co.kr/learn/courses/30/lessons/49995

▶ 코드 (정확성 100, 시간초과)

def solution(cookie):
    n = len(cookie)

    s = [0]*(n+1)
    for i in range(n): # 중복연산을 피하기 위해 i인덱스 까지의 sum배열 생성: O(n)
        s[i+1] = s[i] + cookie[i]
    #print(s)

    max_value = 0
    for M in range(1, n): # 인덱스 1~ (n-1)
        for L in range(0, M):
            for R in range(M+1, n+1): # L연산하는 순간에, R도 같이 연산해줘야한다.
                left_part_sum = s[M] - s[L]
                right_part_sum = s[R] - s[M]

                # max_value와 같거나, 더 작다면 즉시 탈출 
                if left_part_sum <= max_value or right_part_sum <= max_value: 
                    continue
                    
                #print(M, left_part_sum, right_part_sum)

                if left_part_sum == right_part_sum:
                    max_value = left_part_sum

    #print(max_value)
    return max_value
    
solution([1]) # 0
solution([2,2]) # 2
solution([2,3]) # 0
solution([1,7,8]) # 8
solution([1,2,3,5]) # 5
solution([1,1,1,1,3,4,7]) # 7
solution([1,1,2,3]) # 3
solution([1,2,4,5]) # 0

문제 : https://programmers.co.kr/learn/courses/30/lessons/12987

▶ 코드

# 문제: A의 순서를 알고있을때, B의 순서 조작해서 최대한 많이 이겨라.

import heapq

def solution(A, B):
    A.sort(reverse=True) # A를 내림차순 정렬
    
    B = [-i for i in B] # B를 음수화 (최대힙 만들기 위해..)
    heapq.heapify(B) # B를 힙구조로 변환 (B는 최대힙)
    
    c = 0
    for a in A:
        if a >= abs(B[0]): # 음수화된 B에 절대값 씌워서 비교 !
            continue
        else:
            heapq.heappop(B) # B의 원소가 빠져나가도 최대힙 구조를 유지
            c += 1
    print(c)
    return c

문제 : https://programmers.co.kr/learn/courses/30/lessons/49994

▶ 코드

import copy

def solution(dirs):
    path = [] # 지나간 길  ex) [0,0,1,0] : (0,0) -> (1,0)
    last = [0,0]
    
    for a in dirs:
        temp = copy.deepcopy(last)
        if a == 'U':
            last[1] +=1
            if last[1] <= 5 and last[1] >= -5:
                if (temp + last) not in path and (last + temp) not in path:
                    path.append(temp + last)
            else:
                last[1] -=1 # 범위 넘었을 경우 이동경로 다시 되돌려주기
        elif a == 'D':
            last[1] -=1
            if last[1] <= 5 and last[1] >= -5:
                if (temp + last) not in path and (last + temp) not in path:
                    path.append(temp + last)
            else:
                last[1] +=1 # 범위 넘었을 경우 이동경로 다시 되돌려주기 
        elif a == 'R':
            last[0] +=1
            if last[0] <= 5 and last[0] >= -5:
                if (temp + last) not in path and (last + temp) not in path:
                    path.append(temp + last)
            else:
                last[0] -=1 # 범위 넘었을 경우 이동경로 다시 되돌려주기
        elif a == 'L':
            last[0] -=1
            if last[0] <= 5 and last[0] >= -5:
                if (temp + last) not in path and (last + temp) not in path: 
                    path.append(temp + last)
            else: 
                last[0] += 1 # 범위 넘었을 경우 이동경로 다시 되돌려주기
        #print(last)
    #print(path)
    #print(len(path))
    return len(path)
    

#solution("ULURRDLLU")
#solution("LULLLLLLU")
#solution("LR")         # 1이 나와야 한다. 
#solution("L")

문제 : https://programmers.co.kr/learn/courses/30/lessons/12981

▶ 코드

# 주어진 조건대로 구현하면 되는문제

def solution(n, words):
    index = -1
    for i in range(len(words)):
        if len(words[i]) == 1:  # 한 글자인지 
            index = i
            break
        if i >= 1:
            if words[i-1][-1] != words[i][0]:   # 이전 단어랑 비교
                index = i
                break
            if words[i] in words[:i]:
                index = i
                break
    #print(index)
    if index == -1:
        return [0,0]
    else:
        #print([index%n+1, index//n+1])
        return [index%n+1, index//n+1]
    
#solution(3, ['tank', 'kick', 'know', 'wheel', 'land', 'dream', 'mother', 'robot', 'tank'])
#solution(5, [hello, observe, effect, take, either, recognize, encourage, ensure, establish, hang, gather, refer, reference, estimate, executive])
#solution(2, ['hello', 'one', 'even', 'never', 'now', 'world', 'draw'])

#몫2, 나머지2 -> [3,3]
#몫2 나머지0 -> [1,3]

문제 : https://programmers.co.kr/learn/courses/30/lessons/12980

▶ 코드

# 아이디어 : N에서 최대한 많이 2로 나눈다. 

c = 0
def iron(n):
    global c
    if n%2 != 0:  # 홀수 이면
        n -= 1
        c += 1
        if n >0:
            iron(n)
            
    else:  # 짝수 이면
        n //=2
        if n>0:
            iron(n)

def solution(n):
    iron(n)
    #print(c)
    return c

#solution(5)
#solution(5000)

문제 : https://programmers.co.kr/learn/courses/30/lessons/12977

▶ 코드

# 브루트 포스 -> itertools의 '조합'(=순서가 없는 조합) 사용

from itertools import combinations

def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def solution(nums):
    cb = combinations(nums, 3) # 주어진 숫자 중 3개 뽑은 조합  
    #print(list(c))

    c = 0
    for a in list(cb):
        if isPrime(sum(a)):
            c += 1
    #print(c)
    return c

#solution([1,2,3,4])
#solution([1,2,7,6,4])

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

▶ 코드 (시간초과 -> 배열 업데이트 O)

def solution(n, stations, w):

    t = [0]*(n+1)
    
    # (1) 주파수 닿는곳 1로 표기   ->  시간복잡도 : O(n^2)  (N은 200,000,000 이하의 자연수)
    for st in stations:
        for i in range(st-w, st+w+1):
            if i < len(t):
                t[i] = 1
    #print(t)

    # (2) 0으로만 이루어진 집합 각각의 0개수 구하기
    c_arr = []
    c = 0
    for i in range(1, len(t)):
        if t[i] == 0:
            c+=1
            if i == len(t)-1:
                if c>0:
                    c_arr.append(c)
        else:
            if c>0:
                c_arr.append(c)
            c = 0
    #print(c_arr)

    # (3) 계산 
    answer = 0
    signal = 2*w + 1 # 주파수 대역 
    for a in c_arr:
        q = a//signal
        r = a%signal
        if r == 0:
            answer +=q
        else:
            answer += (q+1)
    #print(answer)
    return answer
        

#solution(11, [4,11], 1)
#solution(16, [9], 2)

▶ 코드 (정답 -> 배열 업데이트 X)

def solution(n, stations, w):
    dist = [] # 거리 집합 

    # (1) 설치된 기지국들 사이에 전파가 닿지 않는 거리를 저장한다.
    for i in range(1, len(stations)):
        dist.append( (stations[i]-w-1) - (stations[i-1]+w)  )

    # (2) 첫번째 아파트 ~ 맨 앞 기지국 사이에 전파가 닿지 않는 거리를 저장한다.
    dist.append( stations[0]-w-1 )

    # (3) 맨 뒤 기지국 ~ 마지막 아파트 사이에 전파가 닿지 않는 거리를 저장한다.
    dist.append( n - (stations[-1]+w)  )
    #print(dist)

    # (4) 계산 
    answer = 0
    signal = 2*w + 1 # 주파수 대역 
    for a in dist:
        q = a//signal
        r = a%signal
        if r == 0:
            answer +=q
        else:
            answer += (q+1)
    #print(answer)
    return answer

#solution(11, [4,11], 1)
#solution(16, [9], 2)

# 출처 : https://inspirit941.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%B0%EC%A7%80%EA%B5%AD-%EC%84%A4%EC%B9%98-Level-3

문제 : https://programmers.co.kr/learn/courses/30/lessons/12978

▶ (참조)다익스트라 알고리즘 설명 (동빈나 유튜브) : https://www.youtube.com/watch?v=611B-9zk2o4

▶ (참조)다익스트라 알고리즘 원리, 코딩 (동빈나 블로그) : http://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234424646&categoryNo=128&parentCategoryNo=0&viewDate=¤tPage=5&postListTopCurrentPage=&from=postList

▶ 코드 ( 다익스트라 알고리즘 : 선형탐색 ver. (시간복잡도 O(n^2) )

# 다익스트라 알고리즘 : 선형탐색 ver. (시간복잡도 O(n^2))
# 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있습니다.
# <과정> 
# 1. 출발 노드를 설정합니다
# 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다.
# 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택합니다.
# 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다.
# 위 과정에서 3~4번을 반복합니다.

INF = 987654321

# dist배열 중, 방문하지 않았으면서 가장 작은 값 가진 정점 골라내기  
def getSmallDistIndex(dist, N):
    min_value = INF
    index = 0
    for i in range(N+1):
        if dist[i] < min_value and visited[i] == 0:
            min_value = dist[i]
            index = i
    return index

# 코딩편의를 위해, '이차원 배열' 형태로 만들어준다.
def normalize(road, N):
    t = [[0 for i in range(N+1)] for i in range(N+1)] 
    
    for a in road:
        if t[a[0]][a[1]] != 0:  # 이미 있는 경로일때 
            if a[2] < t[a[0]][a[1]]:    # 비교해서 더 작으면..갱신해주기 
                t[a[0]][a[1]] = a[2]
                t[a[1]][a[0]] = a[2]    # 양방향으로 넣어줘야됨 
        else:
            t[a[0]][a[1]] = a[2]
            t[a[1]][a[0]] = a[2]  
    return t

def dijkstra(road, N):
    global visited

    road = normalize(road, N)
    #print('road=', road)
    
    visited = [0]*(N+1)
    dist = [INF for i in range(N+1)]

    # 1번 정점에서 출발
    dist[1] = 0 
    visited[1] = 1
    for i in range(N+1):
        if road[1][i] != 0:
            dist[i] = road[1][i]    # 1번 정점이랑 인접한 정점들의 가중치 넣어줌 
    #print('시작 dist=', dist)
    #print()

    for _ in range(N-1): # 총 N-1번 반복(=1번 정점 제외)
        current = getSmallDistIndex(dist, N) # 현재 기준 (=거쳐서 갈 정점)
        #print('current index=',current)
        visited[current] = 1                 # current를 방문처리 
        #print('현재 visited=', visited)
        
        for j in range(1, N+1): # 1,2,,,,N
            if visited[j] == 0 and road[current][j]!=0 :    # 방문하지 않았으면서 길이 있는 경우 
                if dist[current] + road[current][j] < dist[j]:
                    dist[j] = dist[current] + road[current][j] # 최소값으로 갱신
        #print(dist)
        #print()
    return dist

def solution(N, road, K): # N=정점의 개수, K는 배달시간 최대허용치 
    answer = 0
    dist = dijkstra(road, N)
    #print(dist)
    for d in dist:
        if d <= K:
            answer += 1
    #print(answer)
    return answer

#solution(5,[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]],3)
#solution(6,[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]],4) 

▶ 코드 ( 다익스트라 알고리즘 : 우선순위 큐 ver. (시간복잡도 O(n*(log(n))) )

# https://tttuer.tistory.com/169

문제 : https://programmers.co.kr/learn/courses/30/lessons/12982

▶ 코드

def solution(d, budget):
    d.sort()
    c = 0
    for a in d:
        budget -= a
        if budget >=0:
            c += 1
    return c

문제 : https://programmers.co.kr/learn/courses/30/lessons/49993

▶ 코드

def solution(skill, skill_trees):
    c = 0
    for i in range(len(skill_trees)):
        t = []
        for j in range(len(skill_trees[i])):
            if skill_trees[i][j] in skill:	# skill에 있는 영단어 이면..
                t.append(skill_trees[i][j])
        word = ''.join(t)
        
        flag = 0
        for k in range(len(word)):
            if word[k] != skill[k]:			# skill과 index위치가 동일하지 않는게 있다면..
                flag = 1
        if flag == 0:
            c += 1
    return c