[TIL]20220601

CS 스터디

챕터 24: 알고리즘은 이상, 프로그래밍은 현실, 챕터 25: 다른 프로그램을 처리하기 위한 프로그램

알고리즘

추상적이고 이상적인 절차를 기술한 것. 어떤 문제의 해결을 위해 필요한 절차를 기술한 것이다.

그 절차나 방법을 이해할 수 있다면 어떤 방법으로도 기술할 수 있다.

• 입력이 있어야 한다.
• 결과를 구할 수 있어야 한다.
• 각 단계(방법)는 명백하고 모호하지 않아야 한다.
• 순서대로 실행을 할 수 있고, 실행이 종료되어야 한다.
• 모든 절차는 오류 없이 실행되어야 한다.

프로그램

실제 컴퓨터가 과제를 완료하기 위해 수행해야 하는 모든 단계를 구체적으로 서술한다.

즉, 컴퓨터가 어떤 일을 처리할 수 있게 하는 명령어의 집합을 말한다.

• 하나 이상의 알고리즘이 컴퓨터가 직접 처리할 수 있는 형태로 표현한 것일 수도 있다.
• 결과가 구해지지 않을 수도 있다.
• 순서대로 실행이 되지만, 실행이 종료되어야만 하는 것은 아니다.
• 오류가 발생할 수도 있다.

프로래밍 언어

1. 저수준 언어(Low-level)
   • 명령어와 데이터를 이진수로 변환하고 카드나 종이 테이프에 구멍을 뚫어서 그 수를 기계가 판독할 수 있게 만든 다음, 컴퓨터 메모리에 적재해야 한다.
2. 어셈블리 언어(Assembly Language)
   • 컴퓨터가 알아들을 수 있는 기계어와 일대일로 대응이 되는 컴퓨터 프로그래밍의 저급언어이다.
   • 컴퓨터는 0과 1만을 인식 할 수 있는데, 이를 사람이 이해하기 쉽게 약간 변형하여 만든 언어이다.
   • 기계어와 가장 가깝기 때문에 컴퓨터 구조를 이해하기 용이한 장점이 있지만, 길고 복잡하며 프로세서마다 언어가 다르다는 단점이 있다.
   • 어셈블리어로 작성한 프로그램으로 프로그램에 의해서 기계어로 변환하는 것을 어셈블러라고 한다.
   • 어셈블러는 프로그램을 수정하는 일을 훨씬 쉽게 해준다.

---

알고리즘

최단 경로 (2)

• 다익스트라:
  • 출발점을 정했을 때 다른 노드에 이르는 최단거리.
• 플로이드-워셜:
  • 모든 지점에서 다른 모든 지점까지 최단거리.
  • 자기자신으로 가는 비용은 0
  • 직접 연결되어있지 않은 경로는 무한대.

구현

INF = int(1e9)


def floyd_warshall(graph):
    N = len(graph)
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d

    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist

---

알고리즘 문제

 

플로이드 - 백준

최단경로 - 백준

운동 - 백준

녹색 옷 입은 애가 젤다지? - 백준 

전보 - 이코테