2024 -03-15 AI 코딩 TIL

오늘은 문제를 먼저 풀이를 다해서 문제 풀이 부터 적도록 하겠습니다

가장 먼 노드

처음에 문제를 잘못 이해 하여서 최단거리계산 중에서 가장거리가 긴 노드의 거리인 줄 알고 계산을 했는데 그게 아니라 가장거리가 긴 노드의 갯수는 몇개 인가 였습니다…

return distance.count(max(distance))

그래서 카운트를 써서 리스트 중에서 맥스 값과 같은 수가 몇개가 있는지 출력해주면 됩니다!

# Code
from collections import deque


def solution(n, edge):
    # 그래프 생성
    graph = [[] for _ in range(n+1)]
    # 노드거리
    distance = [0 for _ in range(n+1)]
    # 그래프 엮기
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
    # 큐생성
    queue = deque()
    # 큐의 1번 노드 넣기
    queue.append(1)
    # 1번 노드는 거리 1
    distance[1] = 1
    # 반복문 진행
    while queue:
        # 큐에서 꺼내기
        node = queue.popleft()
        # 노드와 연결된 모든 노드 반복
        for neighbor in graph[node]:
            # 방문한 적 없으면 큐에 넣고 전 노드 위치 값에 1 더하기
            if not distance[neighbor]:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    # 최고 거리 값 출력
    return distance.count(max(distance))


a = 6
b = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
result = solution(a, b)
print(result)

 

순위

문제를 짜다 보니 아주 복잡하게 만들어 진 것 같은데..

뭔가 여기서 좀 더 다듬을 수 있을 것 같은데.. 모르겠따……….

일단 내가 문제를 푼 방법을 설명해주자면 우리가 싸움을 한다고 생각 했을때

흔히 싸움하는 애들의 이야기 처럼 “나는 누구하고 싸워서 이겼다” 하면 상대가 “그러면 너하고 싸워서이기면 걔도 이긴거네?” 라는 생각이 들었습니다.

이 방법을 생각해서 모든 경기가 끝이 나고 선수를 돌아보면서 1은 2를 이겼고 2가 이긴 사람들은 1과 싸워도 이길 게 뻔하니깐 이긴 걸로 하자 라면서 싸우지는 않았지만 승에 넣어버리면 123을 이겨버린 4을 5번이 이겨 버리면 5번은 한 경기만에 모든 선수중에서 싸움을 잘한다는 결론이 나옵니다.

# Code
def make_result(graph):
    for i in range(1, len(graph)):
        for j in graph[i]:
            for k in graph[j]:
                if k not in graph[i]:
                    graph[i].append(k)
    return graph


def solution(n, results):
    graph_win = [[] for _ in range(n+1)]
    graph_lose = [[] for _ in range(n+1)]

    for i in results:
        graph_win[i[0]].append(i[1])
        graph_lose[i[1]].append(i[0])

    graph_win = make_result(graph_win)
    graph_lose = make_result(graph_lose)

    counter = 0
    for i in range(n+1):
        if len(graph_win[i]) + len(graph_lose[i]) == n-1:
            counter += 1
    return counter

 

방의 갯수

이번 문제는 많이 매운 편이였습니다.!

처음에는 간단하게 선이 진행을 하다가 한번이라도 점을 찍었던 곳을 만나면 방이 만들어 진다는 것을 알았습니다. 하지만 !

이 방을 만드는 문제의 생각을 해보아야 하는 점이 아주 많았습니다.

그림으로 설명을 하자면>>

먼저 
1번을 보면 이미 찍은 점을 되돌아가는 경우 방이 만들어지는 경우가 아니기 때문에 제외를 시켜야 
하며 ( 이건 마지막에 찍은 점의 위치가 이동한 후에 위치와 같으면 제외 하는 방법)
4번을 보면 이미 그어진 선 위를 지나가는 경우에도 제외가 되어야 합니다! 
(이 부분에서는 있는 점에서 또 있는 점으로 이동할 때는 제외 시키는 방법으로 진행)

3번을 보면 1번에는 문제가 없지만 4번에는 이미 있는 점에서 점으로 가서 제외가 되어버렸습니다.
(이 문제에서 4번과 3번을 만족할 수 있게 그래프를 그리면 점과 점을 서로 표시해서 그래프로 만드는 방법을 이용, 하지만 점위치를 미리 만들어 줄 수 없어 딕셔너리를 이용하였습니다! defaultdict)

2번의 경우에는 대각선으로도 만들어지는 방이 생긴다는 것을 생각해야 했는데… 
예를 들어 (0.0),(1.0),(1.1),(0.0),(0.1),(1.0) 순으로 그림을 그리면 대각선이 만나는 점은(0.5,0.5)가 됩니다
이걸 보면서 어? 그러면 2배로 키우면 (1,1)이 되겠네 싶어서 크기를 2배로 키웠습니다.
이 문제에서는 한번에 (+1,+2)를 하는 경우가 없으니 2배를 키워도 문제가 되지 않습니다.

그렇게 해서 모든 경우를 정리를 하면 아래와 같은 코드가 만들어집니다.

# Code
from collections import defaultdict


def solution(arrows):
    # 좌표 이동 방법 [0,1,2,3,4,5,6,7]
    move = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
    # 맨 처음 시작할 위치 (defaultdict 딕셔너리에 리스트를 넣을 때에는 튜플로 넣어야 합니다.)
    position = (0, 0)
    # 만들어진 방의 개수
    counter = 0
    # 방문자 {점위치 : [(x,y),(x,y),(x,y),(x,y)]} <- 이어진 점들
    visit = defaultdict(list)
    # 각 이동에 맞추어 점 이동
    for arrow in arrows:
        # 대각선을 위해서 크기를 2배로 키워준다.
        for _ in range(2):
            # 이동할 점 위치 표시
            move_position = (position[0] + move[arrow][0], position[1] + move[arrow][1])
            # 방문자 명단에서 방문한 점(key)일 경우와 방문은 했지만 해당 방향으로 입장(value)은 처음인 경우
            if move_position in visit and move_position not in visit[position]:
                # 방 한개 완성
                counter += 1
                # 출발하기 전 점과 이동한 점을 서로 연결을 시켜준다.
                visit[position].append(move_position)
                visit[move_position].append(position)
            # 방문을 기록이 없는 처음 찍는 점일 경우
            elif move_position not in visit:
                # 출발하기 전 점과 이동한 점을 서로 연결을 시켜준다.
                visit[position].append(move_position)
                visit[move_position].append(position)
            # 2배로 이동을 해야 하니 이동한 점을 출발점으로 넣어준다
            position = move_position
    # 만들어진 방 출력
    return counter


a = [6, 0, 3, 0, 5, 2, 6, 0, 3, 0, 5]
# b = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
# c = 3
result = solution(a)
# result = solution(a, b)
# result = solution(a, b, c)
print(result)

# ---구글링 도움--
# from collections import defaultdict
# def solution(arrows):
#     answer = 0
#     visit = defaultdict(list)
#     x,y = 0,0
#     dx,dy = [0,1,1,1,0,-1,-1,-1],[1,1,0,-1,-1,-1,0,1]
#
#     for arrow in arrows:
#         for _ in range(2):              # 대각선 판별을 위해 2씩
#             nx = x + dx[arrow]
#             ny = y + dy[arrow]
#             if (nx,ny) in visit and (x,y) not in visit[(nx,ny)]:    # 방문했던 점이지만 경로가 겹치지 않는 경우, 방+1
#                 answer += 1
#                 visit[(x,y)].append((nx,ny))
#                 visit[(nx,ny)].append((x,y))
#             elif (nx,ny) not in visit:                  # 방문하지 않았던 경우
#                 visit[(x,y)].append((nx,ny))            # 경로가 겹치는 경우는 따로 해줄 필요 없음
#                 visit[(nx,ny)].append((x,y))
#             x,y = nx, ny        # 이동
#     return answer

# --- 처음만들었던 방법 반례사례가 너무 많아서 실패----
# def solution(arrows):
#     dot = []
#     move = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
#     position = [0, 0]
#     dot.append(position)
#     for arrow in arrows:
#         position = [position[0] + move[arrow][0], position[1] + move[arrow][1]]
#         if position not in dot:
#             dot.append(position)
#
#     return (len(arrows)-len(dot))+1
#
#
# a = [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]
# # b = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
# # c = 3
# result = solution(a)
# # result = solution(a, b)
# # result = solution(a, b, c)
# print(result)

오늘의 문제는 3개 밖에 없어서 빨리 끝낼 수 있었던 것 같습니다.

---

 

알고리즘 강의 듣기

.isalpha() : 해당변수가 알파벳인가?

counter = {}

# 키의 value 값 추가
counter[char] = 1

# 값 추가
counter[char] += 1

 

---

튜터님의 강의!

 

그래프는 어렵지않다!

vertex = node로 이해 해두자

싸이클

 

싸이클이 없으면 트리가 된다.

메모리 낭비가 너무심함

딕셔너리화 시키자

가중치가 있는 그래프

행렬

딕셔너리

메모리 낭비를 줄이기 위해서는 행렬은 지양해야한다.

이제 방향이 있다면?

 

여기에 가중치가 있다면 값을 더 넣어주면 된다.

 

 

 

다익스트라 최단 경로 알고리즘

graph = {
    "Seoul": {"Wonju": 88, "Daejeon": 140, "Gwangju": 270, "Sokcho": 168},
    "Wonju": {"Seoul": 88, "Sokcho": 110, "Daejeon": 120, "Busan": 260},
    "Daejeon": {"Wonju": 120, "Seoul": 140, "Gwangju": 200, "Busan": 200},
    "Gwangju": {"Daejeon": 200, "Seoul": 270, "Busan": 200},
    "Busan": {"Gwangju": 200, "Daejeon": 200, "Wonju": 200, "Sokcho": 340},
    "Sokcho": {"Seoul": 168, "Wonju": 110, "Busan": 340},
}

코드작성해 보기

from collections import deque


def solve(city):
    distance = {}
    visited = {}
    for i in city:
        distance[i] = float("inf")
        visited[i] = 0
    queue = deque()
    distance[start] = 0
    queue.append(start)

    while len(queue):
        current = queue.popleft()

        if not visited[current]:
            visited[current] = 1
            for neighbor, weight in city[current].items():
                if distance[neighbor] > distance[current] + weight:
                    distance[neighbor] = distance[current] + weight
                queue.append(neighbor)
    return distance[end]


while True:
    start = input("시작 지점 지역명 \n(Seoul,Wonju,Daejeon,Gwangju,Busan,Sokcho)\n 입력:")
    end = input("종료 지점 지역명 \n(Seoul,Wonju,Daejeon,Gwangju,Busan,Sokcho)\n 입력 :")
    if (start in ["Seoul", "Wonju", "Daejeon", "Gwangju", "Busan", "Sokcho"] and
            end in ["Seoul", "Wonju", "Daejeon","Gwangju", "Busan", "Sokcho"]):
        break
    else:
        print("값이 잘못 입력 되었습니다.")

graph = {
    "Seoul": {"Wonju": 88, "Daejeon": 140, "Gwangju": 270, "Sokcho": 168},
    "Wonju": {"Seoul": 88, "Sokcho": 110, "Daejeon": 120, "Busan": 260},
    "Daejeon": {"Wonju": 120, "Seoul": 140, "Gwangju": 200, "Busan": 200},
    "Gwangju": {"Daejeon": 200, "Seoul": 270, "Busan": 200},
    "Busan": {"Gwangju": 200, "Daejeon": 200, "Wonju": 200, "Sokcho": 340},
    "Sokcho": {"Seoul": 168, "Wonju": 110, "Busan": 340},
}

print(f"찾으시는 {start}부터 {end}까지의 거리는 {solve(graph)}Km 입니다.")

뭔가 만들기는 했는데.. 튜터님이 말씀하신 heap을 이용한 방법을 구현해 내지는 못했습니다.