기록

그래프

그래프 : 복잡하게 연결된 자료 객체 사이의 관계를 효율적으로 표현한 것

객체 : 정점

관계 : 간선 (= 객체간의 관계)

그래프 : 접점과 간선의 집합으로 구성됨 -> A와 B를 연결하는 간선 (A, B)

인접 : 간선으로 연결된 두 정점을 인접해 있다고 함

차수 : 정점에 연결된 간선의 수

경로 : 간선을 따라 갈 수 있는 길을 순서대로 나열한 것

연결그래프 : 모든 정점사이에 경로가 존재하는 그래프

트리 : 사이클을 가지지 않는 연결 그래프

그래프의 표현 : 인접리스트를 이용한 표현

인접리스트 : 각 정점이 인접한 정점 리스트를 갖도록 하는 것 -> [[], [2, 5], [1, 5, 4, 3], [4, 2], [3, 6, 5, 2], [2, 1, 4], [4]]

그래프 순회 : 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문하는 작업

깊이우선탐색 (DFS)

시작 정점에서 한 방향으로 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향을 다시 탐색

# 2. dfs를 실행해주는 함수를 만든다
# g : graph, / start : 탐색을 시작하는 정점, / visited : 방문했는지 확인하는 리스트
def DFS(graph, start, visited):
    # 시작하는 정점은 탐색을 했기 때문에 방문했다고 체크
    visited[start] = True
    print(start, end=' ')

    # 시작 정점부터 탐색 시작
    for i in graph[start]:
        if visited[i] is False:
            DFS(graph, i, visited)

g =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]
# 1. 방문했는지 여부를 기록하는 리스트를 만든다.
visited = [False] * len(g)

# 3. 함수를 실행한다
DFS(g, 1, visited)

너비우선탐색 (BFS)

시작 정점에서 가장 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문

# 2. deque를 import 해준다
from collections import deque

# 3. bfs를 구현한다
# g : graph, / start : 탐색을 시작하는 정점, / visited : 방문했는지 확인하는 리스트
def BFS(graph, start, visited):
    queue = deque()
    # 큐에 들어왔기 때문에 방문했다고 체크
    queue.append(start)
    visited[start] = True

    while queue:
        # 큐에서 제거하는 순간 진짜로 방문된 것
        v = queue.popleft()
        print(v, end=' ')
        # 방문한 정점과 인접한 정점 탐색
        for i in graph[v]:
            # 방문하지 않은 정점이라면
            if visited[i] is False:
                # 큐에 넣고 방문했다고 체크
                queue.append(i)
                visited[i] = True

g =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]

# 1. 정점의 방문 여부를 체크하는 리스트를 만든다
visited = [False] * len(g)

# 3. 함수를 실행한다
BFS(g, 1, visited)

첫 번째 시도

• 옹알이를 한 단어를 split을 이용해서 또 리스트로 나누려고 함
• 생각해보니 re.split()은 문자를 제거하고 남은 부분만 반환해서 결과가 이상함
• 옹알이가 가능한 단어가 딱 한번만 수행할 수 있는 줄 알았음

import re
babbling = ["aya", "yee", "u", "maa"]
def solution(babbling):
    ans = 0
    for i in babbling:
        s = re.split(r"[a,y,w,m]", i)
        dic = {"a": ["aya", False], "y": ["ye", False], "w": ["woo", False], "m": ["ma", False]}
        cnt = 0
        for j in s:
            if j[0] == "a" and dic["a"][1] != True:
                if j == dic["a"][0]:
                    cnt = cnt + 1
                    dic["a"][1] == True
            if j[0] == "y" and dic["y"][1] != True:
                if j == dic["y"][0]:
                    cnt = cnt + 1
                    dic["y"][1] == True
            if j[0] == "w" and dic["w"][1] != True:
                if j == dic["w"][0]:
                    cnt = cnt + 1
                    dic["w"][1] == True
            if j[0] == "m" and dic["m"][1] != True:
                if j == dic["m"][0]:
                    cnt = cnt + 1
                    dic["m"][1] == True
        if cnt == len(s):
            ans = ans + 1


    return ans

print(solution(babbling))

정답

• 옹알이가 가능한 단어가 딱 한번만 수행할 수 있는 줄 알았음 -> 그냥 연속해서만 안 하면 됨
  • if w * 2 not in i : 이런식으로 연속해서 두 번 나왔는지 체크 가능
  • i.strip() : 앞뒤로 공백을 제거하는 함수 -> 옹알이가 가능한 부분은 모두 공백으로 치환 후 strip()으로 변경
  • i = i.replace(w," ") -> i 내부의 w를 " " 으로 치환
• 연속해서 옹알이를 하면 안된다는 경우를 이때 알음 (문제를 잘 읽자..)

def solution(babbling):
    ans = 0
    word = ["aya", "ye", "woo", "ma"]
    for i in babbling:
        for w in word:
            if w * 2 not in i: #연속해서 옹알이를 하지 않았다면
                i = i.replace(w," ")#공백으로 치환
        
        if i.strip() == "": #앞 뒤 공백을 모두 제거하고 아무것도 없다면
            ans = ans + 1 #조건 충족
        
    return ans

정답

def solution(lottos, win_nums):
    answer = []
    min_match = 0
    rank = {6:1, 5:2, 4:3, 3:4, 2:5, 1:6, 0:6}
    idx = 0
    lottos.sort(reverse = True)
    win_nums.sort(reverse = True)
    for i in lottos:
        if i == 0:
            break
        for j in win_nums:
            if i == j:
                min_match = min_match + 1
        idx = idx + 1
    
    max_match = min_match + len(lottos) - idx
    
    answer.append(rank[max_match])
    answer.append(rank[min_match])
    return answer

첫 번째 시도

• 시간초과로 실패!

def solution(number, limit, power):
    ans = 0
    for i in range(1, number + 1):
        cnt = 0
        for j in range(1, i + 1):
            if cnt > limit:
                break
            if i % j == 0:
                cnt = cnt + 1
        
        if cnt > limit:
            ans = ans + power
        else:
            ans = ans + cnt
    return ans

탐색 범위를 제곱근까지만 구하기

• 약수는 짝이 맞춰서 있기 때문에 제곱근까지만 탐색해도 해당 값의 약수의 갯수를 모두 구할 수 있음
• 예시 : 20의 약수를 구하고 싶다
  • 1은 20의 약수 : 20 / 1 = 20 -> 20도 20의 약수
  • 2는 20의 약수 : 20 / 2 = 10 -> 10도 20의 약수
  • 4는 20의 약수 : 20 / 4 = 5 -> 5도 20의 약수
  • 20의 제곱근(4.xx)까지만 탐색해도 모든 약수 [1, 2, 4, 5, 10, 20]을 모두 구할 수 있음
• x가 N의 약수라면 N / x 도 N의 약수이다

정답

• 제곱수인 경우 중복되는 경우를 제외하기 위해서 if j != n // j: 조건 추가
  • 16의 약수를 구하는 경우 첫번째로 구한 약수는 4이고 그와 대응하는 약수를 구할 때 해당 대응 약수도 4이므로 중복 카운트 방지

def solution(number, limit, power):
    ans = 0
    for i in range(1, number + 1):
        cnt = 0
        for j in range(1, int(i ** 0.5) + 1):
            if cnt > limit:
                break
            if i % j == 0:
                cnt = cnt + 1
                if j != i // j:
                    cnt = cnt + 1
        
        if cnt > limit:
            ans = ans + power
        else:
            ans = ans + cnt
    return ans

정답

• start + m - 1 을 하면 페인트를 칠할 수 있는 최대 범위의 수가 나옴
• 칠해야 하는 다음 구역이 해당 최대 범위의 수에 포함된다면 넘어가고 그 수보다 크다면 페인트를 칠하는 횟수를 한번 증가시키고 해당 다음 구역부터 페인트칠 시작
• section[0]부터 시작하는 것이 핵심

def solution(n, m, section):
    ans = 1
    start = section[0] #페인트 칠하는 시작점
    for i in range(1, len(section)):
        if start + m - 1 < section[i]:
            ans = ans + 1
            start = section[i]
    return ans

접근방법

특정 길이의 리스트에서 3가지의 수를 뽑는 모든 경우의 수 구하기

백트래킹

1. 첫 번째 숫자를 고정하고,
2. 두 번째 숫자를 첫 번째 숫자 이후의 값 중에서 선택,
3. 세 번째 숫자를 두 번째 숫자 이후의 값 중에서 선택하여,
4. 모든 경우의 수를 탐색하는 방식으로 구현

소수를 구할 때는 범위를 √n까지만 확인하면 된다!

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):  # √n까지만 확인
        if n % i == 0:
            return False
    return True

정답

import itertools
def solution(nums):
    answer = 0
    num = list(itertools.combinations(nums, 3))
    for i in num:
        isPrime = 0
        k = sum(i)
        for j in range(2, k):
            if k % j == 0:
                isPrime = 1
                break
        if isPrime == 0:
            answer = answer + 1
    return answer

첫번째 시도

• 인덱스를 초기화하는 부분에서 문제 발생 -> 나머지 연산자로 해결

def solution(answers):
    sol1 = [1, 2, 3, 4, 5]
    sol2 = [2, 1, 2, 3, 2, 4, 2, 5]
    sol3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]

    idx1 = 0
    idx2 = 0
    idx3 = 0

    cnt = {1:0, 2:0, 3:0}

    for i in answers:
        if idx1 < len(sol1):
            if i == sol1[idx1]:
                cnt[1] = cnt[1] + 1
                idx1 = idx1 + 1
            else:
                idx1 = idx1 + 1
        else:
            idx1 = 0

        if idx2 < len(sol2):
            if i == sol2[idx2]:
                cnt[2] = cnt[2] + 1
                idx2 = idx2 + 1
            else:
                idx2 = idx2 + 1
        else:
            idx2 = 0

        if idx3 < len(sol3):
            if i == sol3[idx3]:
                cnt[3] = cnt[3] + 1
                idx3 = idx3 + 1
            else:
                idx3 = idx3 + 1
        else:
            idx3 = 0

    max_val = max(cnt.values())
    ans = []
    for i in cnt:
        if cnt[i] == max_val:
            ans.append(i)

    ans.sort()
    return ans

정답

• 나머지연산자로 인덱스 구현

def solution(answers):
    sol1 = [1, 2, 3, 4, 5]
    sol2 = [2, 1, 2, 3, 2, 4, 2, 5]
    sol3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]

    idx1 = 0
    idx2 = 0
    idx3 = 0

    cnt = {1:0, 2:0, 3:0}

    for i in answers:

        if i == sol1[idx1 % len(sol1)]:
            cnt[1] = cnt[1] + 1
        idx1 = idx1 + 1

        if i == sol2[idx2 % len(sol2)]:
            cnt[2] = cnt[2] + 1
        idx2 = idx2 + 1

        if i == sol3[idx3 % len(sol3)]:
            cnt[3] = cnt[3] + 1
        idx3 = idx3 + 1

    max_val = max(cnt.values())
    ans = []
    for i in cnt:
        if cnt[i] == max_val:
            ans.append(i)

    ans.sort()
    return ans

정답

• 역순 슬라이싱 : score[-1 : -1-m : -1] 혹은 score[-m:], 첫번째는 데이터가 반대로 흘러가서 역방향으로 조회됨
• 리스트에서 해당 범위를 삭제 : del a[start:end]

def solution(k, m, score):
    score.sort() # 오름차순 정렬
    ans = 0

    while len(score) >= m:
        s = score[-m:]
        del score[-m:]
        ans = ans + s[0] * m
    return ans