어셈블러(assembler)

• 컴퓨터에서 사용하는 저급 프로그래밍 언어인 어셈블리 언어를 기계어로 변환하는 소프트웨어
• 어셈블리 언어는 컴퓨터의 기계어에 대응하는 기호적인 표현을 사용하기 때문에, 각 기계어 명령어는 어셈블리 언어의 명령어와 일대일 대응이 가능하다.
• 어셈블러의 주요 작업은 어셈블리 언어의 각 명령어를 해당하는 기계어 코드로 변환하는 것
• 이런 변환은 기본적으로 대체 작업이지만, 레이블을 메모리 주소에 맵핑하는 등의 추가 작업도 포함될 수 있다.

어셈블리 언어는 컴퓨터 아키텍처에 매우 의존적이다. 즉, 서로 다른 컴퓨터 아키텍처에서는 동일한 기능을 가진 명령어라도 다른 어셈블리 코드를 가질 수 있다. 따라서, 특정 컴퓨터 아키텍처에 대한 깊은 이해 없이는 어셈블리 언어를 효과적으로 사용하는 것이 어렵다.

어셈블리 언어는 주로 시스템 프로그래밍에서 사용되며, 시스템의 하드웨어나 운영체제와 직접적으로 상호작용해야 하는 코드를 작성할 때 주로 사용된다. 이러한 경우, 고급 프로그래밍 언어에서는 처리하기 어려운 저수준의 작업을 수행할 수 있다.

어셈블리 언어

• 컴퓨터 프로그래밍 언어 중에서 가장 저수준의 언어 중 하나로, 기계어 코드에 직접적으로 대응하는 사람이 읽을 수 있는 코드를 제공
• 기본적으로 컴퓨터 아키텍처의 기계어 명령 집합에 대한 기호적인 표현
• 어셈블리 언어는 각기 다른 CPU 아키텍처마다 고유한 명령어 집합을 가진다.
• 즉, 어셈블리 언어로 작성된 프로그램은 그 프로그램이 작성된 특정 컴퓨터 아키텍처에서만 실행될 수 있다.

어셈블리 언어는 다음과 같은 특징을 가지고 있다:

1. 기계 친화적: 어셈블리 언어는 기계어와 매우 밀접한 관련이 있어, 시스템의 내부 작동 방식을 제어하는 데 매우 유용하다.
2. 성능 최적화: 프로그래머가 메모리나 프로세서 명령을 직접 제어할 수 있으므로, 성능을 최적화하는 데 필요한 세밀한 제어를 할 수 있다.
3. 하드웨어 상호작용: 특정 하드웨어를 제어하거나 운영체제의 저수준 기능을 활용해야 하는 경우에 사용된다.

그러나 어셈블리 언어는 프로그래밍이 복잡하고, 디버깅이 어렵고, 코드를 이해하거나 유지보수하기 어렵다는 단점이 있다. 또한 어셈블리 언어로 작성된 코드는 해당 아키텍처에 종속적이므로, 다른 아키텍처에서는 재사용할 수 없다.

오늘날 대부분의 소프트웨어 개발은 고급 프로그래밍 언어를 사용하여 이루어지지만, 임베디드 시스템, 컴퓨터 바이러스, 운영체제, 게임 엔진 등 특정 영역에서는 여전히 어셈블리 언어가 사용된다.

어셈블리 언어 프로그래밍

• 저수준의 컴퓨팅 작업에서 요구되는 것과 같은 특정 작업을 수행하기 위해 어셈블리 언어를 사용하는 프로그래밍 작업
• 어셈블리 언어 프로그래밍은 컴퓨터의 중앙 처리 장치(CPU)가 수행할 수 있는 명령어를 직접 기술하는 방식으로 이루어진다.
• 이 명령어들은 컴퓨터 메모리의 특정 위치를 지정하거나, 계산을 수행하거나, 입력/출력 작업을 실행하거나, 조건에 따라 프로그램의 흐름을 제어하는 등의 작업을 수행한다.

어셈블리 언어 프로그래밍은 아래와 같은 몇 가지 단계로 이루어진다:

1. 코드 작성: 어셈블리 언어로 코드를 작성한다. 이는 프로그래머가 특정 작업을 수행하기 위해 CPU에 내릴 명령어를 명시하는 것을 포함한다.
2. 어셈블리: 작성한 어셈블리 코드는 어셈블러를 통해 기계어로 변환된다. 기계어는 컴퓨터가 직접 이해하고 실행할 수 있는 언어이다.
3. 링킹: 여러 어셈블리 코드 파일이 하나의 실행 가능한 프로그램으로 결합된다. 이 단계는 링커(linker)라는 도구를 통해 이루어진다.
4. 디버깅 및 최적화: 프로그램의 작동을 확인하고, 문제가 있으면 디버깅 필요한 경우, 프로그램의 실행 속도나 메모리 사용량을 줄이기 위해 코드를 최적화한다.

어셈블리 언어 프로그래밍은 복잡하고 시간이 많이 걸리며, 종종 고급 프로그래밍 언어를 사용하는 것보다 훨씬 어렵다. 그러나 어셈블리 언어를 사용하면 하드웨어를 더욱 세밀하게 제어하고, 시스템의 성능을 극대화하는 등의 이점이 있다. 따라서 하드웨어에 대한 깊은 이해가 필요한 프로그래밍 작업, 예를 들어 임베디드 시스템, 드라이버, 운영체제 등에서 어셈블리 언어 프로그래밍이 요구되곤 한다.

용어 정리

• 어셈블러(assembler) : 특정한 처리를 수행하는 프로그램, 다른 프로그래머 사전에 작성했던 프로그램에서 필요한 부분을 모으는 역할을 하기도 했기에 붙은 이름
• 어셈블리 언어 : 어셈블러 프로그램 작성에 사용되는 언어
• 어셈블리 언어 프로그래밍 : 어셈블러 프로그램을 작성하는 프로그래밍

어셈블러의 장점

• 프로그램을 수정하는 일을 쉽게 해준다.
• 명령을 추가/삭제 할때 변경 기록을 직접 관리하는 대신 어셈블러가 각 명령어와 데이터 값이 메모리상 어느 위치에 있을지 파악해주기 때문에.

어셈블러의 특징

• 프로세서의 명령어와 일대일로 연결되는 해당 아키텍처에 특화된 언어이다.
  • ex) 맥과 PC 인텔의 어셈블리 언어는 다르다.
• 명령어가 이진수로 인코딩 되는 특정한 방식과 메모리에 정보가 배치되는 방식 등을 알고 있다.
• 즉, 특정 컴퓨터용 프로그램이 다른 컴퓨터에서 실행되도록 변환하려면 프로그래머는 두 프로세서의 세부사항을 모두 숙달하여야 한다.

어셈블러의 기원과 역사

• 1950년대 , 프로그래밍 시 단순 반복 작업을 처리하기 위한 프로그램을 만들었는데, 이것이 어셈블러의 기원이다.
• 최초의 전자식 컴퓨터에서의 프로그래밍은 카드나 종이에 구멍을 뚫어서 그 수를 기계가 판독하게 만들어야 했다. 즉, 수동으로 명렁어와 데이터를 변경 또는 추가를 해야했고, 프로그램을 바꾸는 것이 매우 어려웠다.
  • 여기서 패치의 기원이나온다. 원래 뜻은 옷에 뚫린 구멍을 덮을 때 쓰는 천 쪼가리 이지만, 구천공카드에 뚫린 구멍을 매꾸는 고침(수정)이 패치라는 언어로 굳어졌다.

알고리즘

추상적이고 이상적인 절차를 기술한 것

구현에 필요한 세부 사항과 현실적인 고려 사항을 무시

알고리즘은 추상적이고 이상적인 절차를 기술한 것으로, 구현에 필요한 세부사항과 현실적인 고려사항을 무시한다. 알고리즘은 정확하고 명로한 레시피이다.

알고리즘은 결국 멈춰야 함

프로그램

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

하나 이상의 알고리즘이 컴퓨터가 직접 처리할 수 있는 형태로 표현된 것

실직적인 문제도 신경 써야 함(메모리 부족, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점)

실제 컴퓨터가 과제를 완료하기 위해 수행해야 하는 모든 단계를 구체적으로 서술한다. 불충분한 메모리, 제한된 프로세서 속도, 유효하지 않거나 악의적으로 잘못된 입력 데이터, 하드웨어 결함, 네트워크 연결 불량, 인간적인 약점 등의 문제가 포함된다.

알고리즘과 프로그램 사이에는 명확한 차이점이 있다.

알고리즘이란 문제를 해결하기 위한 일련의 정해진 절차를 의미한다. 개념적이고 추상적인 형태로 표현되며, 어떤 언어로도 표현될 수 있다. 알고리즘은 문제를 해결하는 방법을 구체적으로 정의하며, 주어진 입력에 대해 예상 가능한 출력을 제공해야 한다.

프로그램은 이 알고리즘을 특정 프로그래밍 언어로 구현한 것이다. 컴퓨터에 의해 실행될 수 있는 구체적인 코드입니다. 프로그램은 알고리즘을 실제로 동작하게 하는 방법에 초점을 맞추며, 이 과정에서 여러 현실적인 제약 사항을 고려해야 한다. 메모리 용량, 프로세서 속도, 입출력 데이터의 유효성, 하드웨어의 기능, 네트워크 상태 등이 포함된다.

따라서 알고리즘과 프로그램을 비교하면, 알고리즘은 이상적인 요리 레시피라고 볼 수 있다. 이 레시피는 어떤 요리사에게도 전달될 수 있으며, 재료와 조리 방법을 제공합니다. 반면, 프로그램은 이 레시피를 구체적으로 실행하는 요리사라고 할 수 있다. 요리사는 주방의 환경, 재료의 상태, 조리 도구 등의 실제 사항을 고려해야 한다.

완전 탐색은 가능한 모든 경로를 탐색하여 최적의 경로를 찾는 방식이다. 이 방식은 경로의 수가 적을 때는 유용하지만, 경로의 수가 많아질수록 연산 비용이 증가하는 단점이 있다. 그리디 알고리즘은 항상 현재 상황에서 가장 좋은 선택을 하는 방식으로 최적의 해를 찾는 방법이다. 이를 위해 각 도시 간의 거리 정보가 필요하며, 이를 이용하여 현재 위치에서 가장 가까운 도시를 선택해 나가면 된다.

1.알고리즘 '복잡도(complexity)'

복잡도란

• 알고리즘의 성능을 나타내는 척도
• 크게 시간 복잡도, 공간 복잡도로 나눌 수 있다.

1.시간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.
• 알고리즘을 위해 필요한 연산의 횟수
• 복잡도를 표현하기 위해 빅오 표기법을 사용한다.
• 최악의 경우에 대한 연산 횟수가 가장 중요하다.
• N의 범위에 따라 시간 복잡도를 계산하고 사용할 수 있는 알고리즘을 선택하는 방법도 있다.

※ 빅오 표기법 (O, big-O)

빅오란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

• 빅오는 점근적 실행 시간을 표기할 때 가장 널리 쓰이는 수학적 표기 방법이여, 여기서 점근적 실행 시간이란 간단하게 N이라는 입력값이 무한대로 커질때의 실행 시간의 추이를 의미한다.
• 따라서 충분히 큰 입력값에서의 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

빅오 표기법 표현 설명

2.공간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
• 알고리즘을 위해 필요한 메모리의 양

2. P vs NP

1.다항 시간 알고리즘(Polynomial-Time Algorithms)

• 다항 시간(합리적인 시간)안에 풀 수 있는 문제.
• 모든 문제가 다항 시간안에 해결되지 않는다.
  • Ex) 튜링의 "Halting Problem(정지 문제)" : 정지 문제란
  프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라.
  • 1936년 앨런 튜링이 모든 가능한 입력값에 대해 정지 문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다.

2.클래스 P

• 다항 시간내에 해결되는 알고리즘을 가지고 있는 결정(decision) 문제의 클래스
  • 어떤 상수 k에 대해 O(N^K) 시간에 풀 수 있는 문제
• O(P(N)) - 이때 P(N)은 N상의 다항시간
• 항상 올바른 답을 계산하는 방법
• 다항시간내에 해결되지 않으면 비효율적

3.클래스 NP

• '비결정적인 다항시간' 상에 존재(stand)
• 주로 "추측" or "평행선화(parallelize)"방식으로 계산
• 다항 시간에 "확인할 수 있는" 문제로 구성
  • 해의 "후보"가 주어지면 문제 입력 크기에 대한 다항 시간에 그 후보가 올바른 해인지 확인할 수 있음을 의미
• 이 방식의 문제점은 "속도(quickly)"

4.P ⊆ NP (아직 증명X)NP-complete(완비) 문제는 NP에서 가장 어려운 문제이다.대부분의 전문적인 문제는 P or NP-complete 문제이다.NP-complete 문제 : P로 해결 가능하지만 NP로 해결되지 않는 문제(미제문제)

3.여행하는 외판원 문제(Traveling-Salesman-Problem)

1.여행하는 외판원 문제(TSP)

외판원 문제 또는 순회 외판원 문제는 초합 최적화 문제의 일종이다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

• 외판원은 자신이 사는 도시에서 출발해서 어떤 순서로든 다른 도시를 모두 방문하고 나서 다시 출발점으로 돌아와야 한다.
  • 여기서 목표는 각 도시를 정확히 한 번씩(반복 없이) 방문하고,
  • 전체 여행한 거리를 최소로 만드는 것이다.⇒ 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순회를 구하라" 라고 표현할 수 있고, 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 계산 복잡도는 변하지 않는다.
• 외판원 순회 알고리즘은 무식하게 풀 수 있다. 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않다.
• 그러면 남은 도시들을 어떤 순서로 방문할지를 정하기만 하면 된다.
• 남은 n-1개의 도시를 나열하는 방법으로는 (n-1)!가지가 있다.
• 그래서 재귀 호출을 통해 쉽게 외판원 순회 알고리즘을 설계할 수 있다.
• 그러나 보통 n!의 풀이는 사용하지 않는다. 12!만 해도 479,001,600라는 엄청난 수를 지니기 때문이다.

2.외판원 순회 알고리즘을 더 빠르고 효율적으로 구하는 방법은?

• 모든 정점을 한 번씩 방문하는(출발 정점 제외) 최단 순환 경로를 탐색하는데 최적의 효율로 탐색하기 위해서 사용한다.

DP 메모제이션

• (n-1)!의 모든 경로를 조사하지 않고 중복된 경로를 제거하는 dp 메모제이션 기법을 사용하면 된다.
  • 동일한 하위 문제의 반복을 막아줌으로써 더 높은 효율로 연산이 이루어지게 해준다. 중복되는 경로의 조사를 제거해주는 것이다.
• 예를 들어, 피보나치 함수는 dp 메모제이션 기법을 통해 O(2^n)의 복잡도를 O(N)까지 줄여준다. **그렇다고 무조건 dp 메모제이션을 적용하면 각 문제의 성질이 다르기 때문에 O(n)으로 줄어든다는 뜻은 아니다.

비트마스킹

• 비트마스킹을 사용하면 bit연산이기 때문에 다른 자료구조(boolean배열)을 사용하는 것보다 훨씬 빠르게 동작되고 코드도 간결해진다.
• 가장 큰 장점은 N이 16개인 경우 2^16가지의 경우를 16bit로 표현이 가능하다.

⇒ 정리하면 TSP(외판원 순회)는 최단 순환 경로를 탐색해야하는데 1) N! 의 중복 경로를 제거해주는 DP 메모제이션 기법을 사용한다. 그래도 2^N의 모든 경우의 수를 표현해야 하기 때문에 그만큼의 공간복잡도가 필요하다. 2) 메모리 사용량도 줄이고 성능 향상을 위해서 2^N의 경우의 수를 Nbit로 표현할 수 있는 비트마스킹으로 사용한다.

⇒ 올라가야 할 계단의 수를 100 개에서 1개로 줄여주는 설계 방법 이라고 보면 된다.

그렇다면 왜 한 정점만 탐색해도 될까?

• DP 메모제이션 기법으로 엄청나게 시간을 단축 할 수 있는 것은 그만큼 중복되는 경로가 많기 때문이다.
• 이 순회 경로는 싸이클로 n개의 정점 중 어느 정점에서 탐색을 시작해도 결과는 똑같다는 것을 알아야 한다.

• 어차피 최적 경로 싸이클은 어디서 시작해도 똑같이 나오기 때문에 한 정점에서만 탐색해줘도 된다.
• 1번에서 출발 : 1 → 2 → 5 → 3 → 4 → 12번에서 출발 : 2 → 5 → 3 → 4 → 1 → 23번에서 출발 : 3 → 4 → 1 → 2 → 5 → 3

알고리즘 참고 영상 :

[youtube] hungarian dance - sorting algorithms

참고 링크 :

[알고리즘] 복잡도란 무엇인가

빅오 표기법 (O, big-O)

정지 문제

P와 NP

여행하는 외판원 문제(TSP)