24.06.25 알고리즘, CS

알고리즘

다익스트라(Dijkstra)

• DP를 활용한 최단 경로 탐색 알고리즘
• 다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다. DP가 적용되는 이유는, 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다.
• 다익스트라를 구현하기 위해 두 가지를 저장해야 한다.
  • 해당 정점까지의 최단 거리를 저장한다.
  • 정점을 방문했는 지 저장한다.
  • 시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다.

과정

1. 최단 거리 값은 무한대 값으로 초기화한다.
2. 시작 정점의 최단 거리는 0이다. 그리고 시작 정점을 방문 처리한다.
3. 시작 정점과 연결된 정점들의 최단 거리 값을 갱신한다.
4. 방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는다.
5. 찾은 정점을 방문 체크로 변경 후, 해당 정점과 연결된 방문하지 않은 정점의 최단 거리 값을 갱신한다.
6. 모든 정점을 방문할 때까지 4-5번을 반복한다.

시간복잡도

• 인접 행렬 : O(n^2)
• 인접 리스트 : O(nlogn)
  • 선형 탐색으로 시간 초과가 나는 문제는 인접 리스트로 접근해야 한다.(우선순위 큐)
• 간선의 값이 양수일 때만 가능하다.

비트마스크(BitMask)

• 집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉이다.

사용 이유

• DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제를 해결하기 위해서.
• 작은 메모리와 빠른 수행시간으로 해결이 가능하다.
  • 원소의 수가 많지 않아야 한다.
• 집합을 배열의 인덱스로 표현할 수 있다.
• 코드가 간결해진다.

비트(Bit)란?

• 컴퓨터에서 사용되는 데이터의 최소 단위

비트 연산

• AND(&) : 대응하는 두 비트가 모두 1일 때, 1을 반환한다.
• OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일 때, 1을 반환한다.
• XOR(^) : 대응하는 두 비트가 서로 다를 때, 1을 반환한다.
• NOT(~) : 비트 값을 반전하여 반환한다.
• SHIFT(>>,<<) : 왼쪽 혹은 오른쪽으로 비트를 옮겨 반환한다.

1. 삽입

• 삽입의 경우 OR 연산을 활용한다.

2. 삭제

• 삭제의 경우 AND 연산과 NOT 연산을 활용한다.

3. 조회

• 조회의 경우 i번째 비트가 무슨 값인지 알려면, AND연산을 활용한다.

CS

컴퓨터의 구성

• 컴퓨터 시스템은 크게 하드웨어와 소프트웨어로 나누어진다.
• 하드웨어 : 컴퓨터를 구성하는 기계적 장치
• 소프트웨어 : 하드웨어의 동작을 지시하고 제어하는 명령어 집합

하드웨어

• 중앙처리장치(CPU)
  • 주기억장치에서 프로그램 명령어와 데이터를 읽어와 처리하고 명ㅇ령어의 수행순서를 제어한다.
  • 중앙처리장치는 비교와 연산을 담당하는 산술논리 연산장치(ALU)와 명령어의 해석과 실행을 담당하는 제어장치, 속도가 빠른 데이터 기억장소인 레지스터로 구성 되어 있다.
• 기억장치 : RAM, HDD
  • 프로그램, 데이터, 연산의 중간 결과를 저장하는 장치
  • 주 기억장치와 보조 기억장치로 나누어지며, RAM과 ROM도 이곳에 해당한다. 실행중인 프로그램과 같은 프로그램에 필요한 데이터를 일시적으로 저장한다.
  • 보조기억장치는 하드디스크 등을 말하며, 주기억장치에 비해 속도는 느리지만 많은 자료를 영구적으로 보관할 수 있는 장점이 있다.
• 입출력 장치 : 마우스, 프린터, 모니터 등.
  • 입력과 출력 장치로 나누어진다.
  • 입력 장치는 컴퓨터 내부로 자료를 입력하는 장치이다.
  • 출력 장치는 컴퓨터에서 외부로 표현하는 장치이다.

소프트웨어

• 시스템 소프트웨어 : 운영체제, 컴파일러
• 응용 소프트웨어 : 워드 프로세서, 스프레드 시트 등.

시스템 버스

• 하드웨어 구성 요소를 물리적으로 연결하는 선이다.
• 각 구성요소가 다른 구성요소로 데이터를 보낼 수 있도록 통로가 되어준다.
• 용도에 따라 데이터 버스, 주소 버스, 제어 버스로 나누어진다.
• 데이터 버스
  • 중앙 처리 장치와 기타 장치 사이에서 데이터를 전달하는 통로
  • 기억장치와 입출력장치의 명령어와 데이터를 중앙처리장치로 보내거나, 중앙처리장치의 연산 결과를 기억장치와 입출력장치로 보내는 ‘양방향’ 버스이다.
• 주소 버스
  • 데이터를 정확히 실어나르기 위해서는 기억장치 ‘주소’를 정해주어야 한다.
  • 주소버스는 중앙처리장치가 주기억장치나 입출력장치로 기억장치 주소를 전달하는 통로이기 때문에 ‘단방향’ 버스이다.
• 제어 버스
  • 주소 버스와 데이터 버스는 모든 장치에 공유되기 때문에 이를 제어할 수단이 필요하다.
  • 제어 버스는 중앙처리장치가 기억장치나 입출력장치에 제어 신호를 전달하는 통로이다.
  • 제어 신호 종류
    • 기억장치 읽기 및 쓰기, 버스 요청 및 승인, 인터럽트 요청 및 승인, 클락, 리셋 등
  • 제어 버스는 읽기 동작과 쓰기 동작을 모두 수행하기 때문에 ‘양방향’ 버스이다.
• 컴퓨터는 기본적으로 읽고 처리한 뒤 저장하는 과정으로 이루어진다. 이 과정을 진행하면서 끊임없이 주기억장치와 소통한다. 이때 운영체제가 64bit라면, CPU는 RAM으로부터 데이터를 한번에 64비트씩 읽어온다.