FIFO(First In First Out) 개념을 가진 선형 자료구조로 먼저 들어간 값이 가장 먼저 나온다.

• DeQueue: 큐의 출력
• EnQueue: 큐의 입력

Array로 표현하기

array로 표현 시 간단하지만 front와 rear가 무한정 커질 수 있다는 단점이 있다.

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  // front 인덱스에 해당하는 값 반환.
  peek() {
    return this.queue[this.front];
  }

  // 큐의 크기 반환.
  size() {
    return this.rear - this.front;
  }
}

Linked List로 표현하기

Linked List로 표현 시 front가 head, rear가 tail로 표현된다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enqueue(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size += 1;
  }

  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size -= 1;
    return value;
  }

  peek() {
    return this.head.value;
  }
}

원형 큐(Circular Queue)

Front와 Rear가 이어져있는 Queue로 한정된 공간을 효율적으로 이용 가능.

maxSize를 정해서 큐의 크기를 제한하고, Front나 Rear가 크기를 벗어나면 다시 0번 인덱스부터 시작한다.

Array로 표현하기

class CircularQueue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  enqueue(value) {
    if (this.isFull()) {
      console.log('Queue is full.');
      return;
    }
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.maxSize;
    this.size += 1;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    this.size -= 1;
    return value;
  }

  isFull() {
    return this.size === this.maxSize;
  }

  peek() {
    return this.queue[this.front];
  }
}

slice()는 얕은 복사본을 만들어 새로운 배열 객체로 반환 ➡ 원본 배열이 변하지 않는다.

splice()는 배열의 기존 요소를 삭제/교체하거나, 새 요소 추가 가능. ➡ 원본 배열이 변한다.

Array.prototype.slice()

배열의 begin 부터 end 까지(end 미포함)에 대한 얕은 복사본을 만들어 새로운 배열 객체로 반환. 원본 배열이 변하지 않는다.

arr.slice([begin[, end]])

begin

추출 시작점에 대한 인덱스

• undefined: 0번 인덱스부터 시작.
• 음수: 배열 끝에서부터의 길이를 의미.
• 배열의 길이보다 큰 경우: 빈 배열 반환.

end

추출을 종료 할 기준 인덱스, end는 미포함하고 추출.

• 지정하지 않을 경우: 배열의 끝까지 추출.
• 음수: 배열의 끝에서부터의 길이를 의미.
• 배열의 길이보다 큰 경우: 배열 끝까지 추출.

예시

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(-2));
// 배열의 끝에서부터 2부터 끝까지 추출.
// expected output: Array ["duck", "elephant"]

console.log(animals.slice(2, -1));
// 인덱스 2 부터 끝에서 첫번 째까지(포함 X).
// expected output: Array ["camel", "duck"]

console.log(animals.slice());
// expected output: Array ["ant", "bison", "camel", "duck", "elephant"]

Array.prototype.splice()

배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경. 원본 배열이 변한다.

array.splice(start[, deleteCount[, item1[, item2[, ...]]]])

start

변경을 시작할 인덱스

• 배열의 길이보다 큰 경우: 배열의 길이로 설정.
• 음수: 배열의 끝에서부터 요소를 세어나감.
• 음수일 때, 음수의 절대값이 배열의 길이보다 큰 경우: 0으로 설정.

deleteCount

제거할 요소의 수

• 생략하거나 array.length-start보다 크면: 모든 요소 제거
• 0 이하: 아무 요소도 제거하지 않는다.

item1, item2, ...

배열의 추가할 요소

• 아무 요소도 지정하지 않으면: splice()는 요소 제거만 한다.

예시

const months = ['Jan', 'March', 'April', 'June'];
months.splice(1, 0, 'Feb');
// 변경을 시작할 인덱스가 1.
// 제거할 요소는 없고, 'Feb'만 1 인덱스에 추가
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "June"]

months.splice(4, 1, 'May');
// "June"이 사라지고 'May' 추가됨.
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "May"]

months.splice(-2, 1);
// "끝에서 두번 째인 April 제거"
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "May"]

months.splice(2);
// index 2부터 끝까지 제거
console.log(months);
// expected output: Array ["Jan", "Feb"]

논리 연산자를 이용하여 로직을 축약하는 것. 논리합(||) 혹은 논리곱(&&) 연산자 이용함.

JavsScript에서 논리합과 논리곱의 결과는 true, false가 아닐 수도 있다. 표현식에서는 논리합과 논리곱의 결과로 반드시 피연산자 중 하나로 평가됨.

논리곱 단축 평가

좌 -> 우로 평가 진행. 모든 피연산자가 Truthy일 때 가장 마지막 피연산자 반환.

'First' && 'Second' // 'Second'

'First'는 Truthy로 평가되고 우측인 'Second'로 이어져 최종 결과가 'Second'가 된다.

논리합 단축 평가

좌 -> 우로 평가 진행. 하나만 Truthy로 평가되어도 그 값을 반환.

'First' || 'Second' // 'First'

'First'가 Truthy로 평가되어 'Second'는 무시되고 그대로 'First'반환

활용 예제

if문 대체하기

if (a) { // a가 Truthy하면
    b = c; // b에 c를 대입
}

위 로직을 논리곱 단축 평가를 이용하여 줄일 수 있다.

b = a && c; // a가 Truthy하면 c가 대입된다.

반대로 falsy할 때 로직은 논리합 단축 평가 이용 가능.

b = a || c; // a가 Falsy하면 c가 대입된다.

객체가 null 혹은 undefined인지 확인하기

const obj = null;
const value = obj && obj.value;
// obj가 null이면 Falsy하기 때문에 우측 피연산자가 평가되지 않는다.

기본값 부여하기

function getLength(str) {
    const newStr = str || '';
    // str이 Falsy하면 ''가 반환된다.
    return newStr.length;
}

유사 배열 객체(length속성과 인덱싱 요소를 가진 객체)나 반복 가능한 객체를 얕게 복사해 새로운 Array 객체를 만든다.

Array.from(arrayLike, mapFn, thisArg)

• arrayLike: 배열로 변환하고자 하는 유사 배열 객체/반복 객체
• mapFn은 arrayLike를 array로 변환 후 실행할 map 함수로 Array.from(arrayLike).map(mapFn) 과 같다.

string -> 배열

Array.from('foo');
// ['f', 'o', 'o']
// 참고) [...'foo']의 결과와 같음

Map객체의 key만 가져오기

const mapper = new Map([['U', 1], ['D', 2]]);
Array.from(mapper.keys());
// ['U', 'D']

mapFn 활용

Array.from({length: 5})만 실행 시 값이 모두 undefined인 길이가 5인 배열이 만들어짐.

Array.from({ length: 5 }, (v, i) => i);
// [0, 1, 2, 3, 4]

각 메서드를 언제 사용해야할까?

• for: break문을 만나면 반복문 중단 가능
• forEach: 배열의 각 요소에 대해 callback 실행,break문 사용 불가
• map: 배열의 각 요소에 callback 실행 후, 실행결과를 모은 새 배열로 리턴
• filter:배열의 각 요소에 callback 조건을 통과한 요소들만 새 배열로 리턴
• reduce: 배열의 각 요소에 reducer 함수 실행 후, 하나의 결과값 반환

array.forEach()

배열의 각 요소를 처음부터 끝까지 순회할 때 사용. map()과 reduce()와는 달리 undefined를 반환하기 때문에 메서드 체인의 중간에 사용할 수 없다.

arr.forEach(callback(currentvalue[, index[, array]])[, thisArg])

callback 각 요소에 대해 실행할 함수. 다음 세 가지 매개변수를 가진다.

currentValue 처리할 현재 요소.

index 처리할 현재 요소의 인덱스.

array forEach()를 호출한 배열.

thisArg callback을 실행할 때 this로 사용할 값.

반환 값 undefined

array.map()

배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환한다.

arr.map(callback(currentValue[, index[, array]])[, thisArg])

callback 새로운 배열 요소를 생성하는 함수. 다음 세 가지 인수를 가진다.

currentValue 처리할 현재 요소.

index 처리할 현재 요소의 인덱스.

array map()을 호출한 배열.

thisArg callback을 실행할 때 this로 사용되는 값.

array.filter()

주어진 함수의 테스트를 통과하는 모든 요소를 모아 새로운 배열로 반환한다. arr.filter(callback(currentValue[, index[, array]])[, thisArg])

callback 각 요소를 시험할 함수. true를 반환하면 요소를 유지하고, false를 반환하면 버린다

다음 세 가지 매개변수를 가진다.

currentValue 처리할 현재 요소.

index 처리할 현재 요소의 인덱스.

array filter를 호출한 배열.

thisArg callback을 실행할 때 this로 사용하는 값.

array.reduce()

arr.reduce(callback([acc, currentValue[, index, array]])[, initialValue]) 배열의 각 요소에 대해 주어진 리듀서(reducer) 함수를 실행하고, 하나의 결과값을 반환한다.

callback

배열의 각 요소에 대해 실행할 함수. 다음 네 가지 인수를 가진다.

acc 누산기는 콜백의 반환값을 누적. 콜백의 이전 반환값 또는, 콜백의 첫 번째 호출이면서 initialValue를 제공한 경우에는 initialValue의 값.

currentValue 처리할 현재 요소.

index 처리할 현재 요소의 인덱스. initialValue를 제공한 경우 0, 아니면 1부터 시작.

array reduce()을 호출한 배열.

thisArg callback의 최초 호출에서 첫 번째 인수에 제공하는 값. 초기값을 제공하지 않으면 배열의 첫 번째 요소를 사용. 빈 배열에서 초기값 없이 reduce()를 호출하면 오류가 발생.

동빈나님의 이코테 2021을 보고 정리한 게시글입니다.

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구

• 정당성 분석이 중요! 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

예시

루트 노드부터 시작하여 거쳐 가는 노드 값을 최대 합으로 만들고 싶을 때 최적의 해는?

그리디 알고리즘은 매 상황에서 가장 큰 값만 고른다.

일반적으로 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

하지만 코테에서 대부분 그리디는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제

대표 문제

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원 일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, N은 항상 10의 배수.

문제 해결 아이디어

단순히 가장 큰 화폐 단위부터 거슬러 준다.

정당성 분석

큰 단위가 항상 작은 단위의 배수이므로 작은 단위 동전들을 종합해 다른 해가 나올 수 없기 때문

만약 화폐 단위가 500원, 400원, 100원이라면 800원을 거슬러줘야할 때 그리디로는 500원 1개, 100원 3개가 나오지만 사실은 400원 2개가 최적의 해다.

이처럼 그리디 알고리즘에서는 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 한다.

시간 복잡도 분석

화폐의 종류가 K라고 할 때, 화폐의 종류만큼 반복하므로 시간복잡도는 $O(K)$이다.

그리디 유형 문제 풀이

문제 1) 1이 될 때까지

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택 가능.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수는? N(1 <= N <= 100000), K(2 <= K <= 100000)

예시

N = 17, K = 4 1번 과정을 한 번 수행하면 N은 16 이후에 2번 과정 두 번 수행하면 N은 1 ✅ 전체 과정 실행 횟수: 3

문제 해결 아이디어

주어진 N에 대해 최대한 많이 나누기를 수행하면 된다. N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있기 때문.

정당성 분석

가능하면 최대한 많이 나누는 작업이 최적의 해를 보장할 수 있을까?

N이 아무리 큰 수여도, K가 2 이상이기 때문에 나누는 것이 기하급수적으로 빠르게 줄일 수 있다. 또한 N은 항상 1에 도달하게 된다.

풀이

if문으로 나누어 떨어지면 나누고 그렇지 않으면 1을 빼는 방법도 있지만 한번에 나누어 떨어지는 값을 만든다음에 나눠주는 방법이 더 효율적이다.

n, k = map(int, input().split())

count = 0
while True:
    # n이 k로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k
    count += (n - target)
    n = target
    # n이 k로 더 이상 나눌 수 없을 때 탈출
    if n < k:
        break
    # k로 나누기
    n //= k
    count += 1

# 남은 수에서 1씩 빼기    
count += (n - 1)
print(count)

✅ 시간 복잡도: $O(logN)$

첫째, 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열 1, 1, 2, 3, 5, 8, 13, ...

재귀함수 사용

$f(n) = f(n-1) + f(n-2)$ 이기 때문에 가장 먼저 생각해 볼 수 있는 방법은 재귀함수로 구현.

예를 들어, F(5)를 구한다고 할 때 재귀함수로 구현하면,

이미 계산했던 부분이 계속 반복적으로 호출되는 것을 확인할 수 있다. N이 커지면 커질 수록 시간복잡도, 공간복잡도가 커짐.

✅ 시간 복잡도: $O(2^n)$ (해당 트리의 높이만큼) ✅ 공간 복잡도: $O(2^n)$

반복문 사용

다음 항을 계산하고, 현재 항과 다음 항을 저장하는 것을 반복.

n = int(input())
a = b = sum = 1

for i in range(3, n+1):
  sum = a + b;
  a = b;
  b = sum;

✅ 시간 복잡도: $O(N)$ ✅ 공간 복잡도: $O(1)$

내장함수 sum() 사용

sum(range(n+1))

✅ 시간 복잡도: $O(1)$ ✅ 공간 복잡도: $O(N)$

▪ n이 커질 경우에 꽤 많은 메모리를 소모할 수 있다.

가우스의 공식 사용

S = 1 + 2 + 3 + 4 + 5 S = 5 + 4 + 3 + 2 + 1

2S = (n+1) * n개

S = n * (n+1) // 2

✅ 시간 복잡도: $O(1)$ ✅ 공간 복잡도: $O(1)$

N부터 M까지의 합

가우스의 공식을 응용하여, 2S = (n + m) * (m-n+1)개

S = (n+m) * (m-n+1) // 2

# n, m의 대소관계가 정해져있지 않은 경우
(n + m) * (max(n,m) - min(n,m) + 1) // 2

반효경 교수님의 운영체제 강의를 듣고 정리한 게시글입니다.

동기식 입출력과 비동기식 입출력

두 경우 다 I/O의 완료는 인터럽트로 알려줌

동기식 입출력(Synchronous I/O)

I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감

1. 구현 방법 1:(Programmed I/O)

• I/O가 끝날 때까지 CPU를 낭비시킴
• 매 시점 하나의 I/O만 일어날 수 있음.
• 인터럽트 x

*2. 구현 방법 2:(Interrupt-driven I/O) *

• I/O가 완료될 때까지 해당 프로그램에게서 CPU를 빼앗음
• I/O 처리를 기다리는 줄에 그 프로그램을 줄 세움
• 다른 프로그램에게 CPU를 줌

비동기식 입출력(Asynchronous I/O)

I/O가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감

입출력을 위한 하드웨어 구성에 따라

독립적인 입출력(Isolated I/O = I/O mapped I/O)

CPU와 입출력 장치들이 I/O Bus, CPU와 메모리는 메모리 Bus를 통해 연결되어있다.

I/O instruction이 명령어 집합(Instruction Set)에 따로 추가되므로 제어로직이 복잡해지고, I/O Bus를 장착하는데 추가 비용이 든다.

메모리 주소지정 입출력(Memory-mapped I/O)

입출력 장치들이 메모리와 함께 메모리 Bus에 연결되어 있어 입출력을 위한 instruction을 따로 두어 사용하지 않고, 메모리에 대한 명령어를 사용하여 입출력을 하는 방식

입출력 장치들이 각각 메모리의 번지를 할당받아 그 주소 공간만큼의 메모리를 활용할 수 없는 단점.

저장장치 계층 구조

밑으로 갈수록 용량은 크고, 속도가 느리고, 비용은 낮아진다.

Primary : CPU에서 직접 접근, Volatile(휘발성) Secondary : CPU에서 직접 접근 X, Non-volatile(비휘발성)

💡 캐싱(Chaching)? 속도 차이를 완충하기 위해서 당장 필요한 정보나 자주 사용되는 정보를 저장해놓는 것, 재사용을 목적으로.

프로그램의 실행(메모리 Load)

프로그램이 File System에 실행 파일 형태로 저장되어 있고, 프로그램을 실행하면 메모리에 올라가 프로세스가 된다.

Virtual Memory

프로그램이 메모리에 바로올라가는 것이 아니라 Virtual Memory를 거친다.

프로그램을 실행시키면 그 프로그램의 독자적인 Address Space(메모리 주소 공간)이 형성되고 Code, Data, Stack 영역으로 구성되어 있다.

Code

CPU에서 실행할 기계어 코드

Data

전역 변수같은 프로그램이 사용하는 자료구조

Stack

Code가 함수 구조로 되어있기 때문에 함수를 호출하거나 리턴 시 데이터를 임시로 저장하는 용도로 사용하는 곳

Virtual Memory에서 주소 변환(Address translation)을 통해 당장 필요한 부분만 물리적인 Memory에 올려 사용하고, 그렇지 않은 부분은 Disk의 Swap area에 내려 놓는다.

💡 Swap area? 메모리 용량의 한계로 연장 공간으로써 디스크에서 사용하는 부분으로 전원이 나가면 내용이 사라진다.

커널 주소 공간의 내용

커널 주소 공간도 마찬가지로 Code, Data, Stack 으로 구성되어있다.

Code

• 시스템콜, 인터럽트 처리 코드
• 자원 관리를 위한 코드
• 편리한 서비스를 제공하기 위한 코드

Data

하드웨어와 프로세스를 관리하기 위한 자료 구조

프로세스를 관리하기 위한 자료 구조인 프로세스 제어 블록인 PCB(Process Control Block)

Stack

OS 역시 함수 구조로 되어있기 때문에 함수 호출하거나 리턴 시 필요한 공간

사용자 프로그램이 사용하는 함수

사용자 정의 함수

자신의 프로그램에서 정의한 함수

라이브러리 함수

자신의 프로그램에서 정의하지 않고 갖다 쓴 함수 자신의 프로그램 실행 파일에 포함되어 있다.

커널 함수

운영체제 프로그램의 함수 커널 함수의 호출 = System Call

프로그램의 실행

유저 모드에서 사용자 정의함수나 라이브러리 함수를 호출하다가 System Call을 하여 커널 함수를 호출하면 커널 모드로 CPU가 동작하고, 끝나면 다시 유저 모드로 CPU가 동작한다.

[보충 참고자료] 김주균, OS? Oh Yes! 누워서 보는 운영체제 이야기

반효경 교수님의 운영체제 강의를 듣고 정리한 게시글입니다.

컴퓨터 시스템 구조

Memory

CPU의 작업공간

Device Controller

각 I/O device에 붙어있는 일종의 작은 CPU로 각 장치들을 제어. I/O 요청이 들어오면 CPU가 직접 읽어오는 것이 아닌 Device controller에게 시키고 device controller가 해당 값을 자신의 local buffer에 저장해 놓는다.

💡 Device driver(software) OS 코드 중 각 device를 처리하기 위한 routine

Local buffer

CPU도 작업 공간인 메인 메모리가 있듯이 각 Device Controller들도 작업 공간이 필요한데 이를 Local buffer라 부른다.

CPU

매 클럭마다 메모리에서 Instruction을 하나씩 읽어 수행

Register

CPU 내부에 메모리보다 빠르면서 정보를 저장할 수 있는 작은 공간으로 처리할 명령어나 연산의 중간 값 등을 일시적으로 기억하는 임시 기억장소

Mode bit

CPU에서 실행되는 것이 커널모드인지 유저모드인지 구분해 주는 bit 사용자 프로그램의 잘못된 수행으로 다른 프로그램 및 OS에 피해가 가지 않기 위한 보호 장치

• 커널모드(0): OS 코드 수행
• 유저모드(1): 사용자 프로그램 수행

Interrupt나 Exception 발생 시 0으로 사용자 프로그램에게 CPU를 넘기기 전에 1로 셋팅

Interrupt line

인터럽트(Interrupt)의 발생을 감지하는 라인으로 매 instruction을 실행 후 CPU는 Interrupt line을 체크한다.

Timer

특정 프로그램의 CPU 독점을 막기위해 Timer에 할당된 시간만큼 프로그램이 동작한다. 시간이 다 되면 timer interrupt가 발생하여 OS에게 CPU를 넘겨주고, OS가 다음 프로그램에게 timer를 설정하여 CPU를 넘겨준다.

DMA(Direct Memory Access) controller

• 빠른 입출력 장치를 메모리에 가까운 속도로 처리하기 위해 사용.
• CPU의 중재 없이 device의 local buffer의 내용을 메모리에 block 단위로 직접 전송.

예를 들어, Input의 작업이 끝나고 local buffer에 있는 값을 메모리로 복사를 해야하는데 원래 메모리는 CPU만 접근할 수 있어서 CPU에게 인터럽트를 걸어야 하므로 버퍼 크기 이상의 데이터를 옮길 때 I/O 장치의 인터럽트가 너무 많이 발생하여 오버헤드가 발생한다.

➡ DMA 방식 이용: CPU 대신 입출력 작업을 대신 해 줄수 있는 채널(Channel)을 통해 한 번의 입출력 단위인 블록(Block) 단위로 CPU에게 인터럽트를 보내 1번의 인터럽트로 처리할 수 있다.

💡** Cycle Stealing이란?** CPU와 DMA가 동시에 메모리 접근 요구 시 속도가 빨라 접근 기회를 더 많이 가지는 CPU가 DMA의 채널에게 기회를 주어 원할한 입출력이 이루어질 수 있도록 하는 방법으로 채널이 CPU의 메모리 접근 사이클을 훔친다고 해서 Cycle Stealing이라 한다.

Memory controller

CPU와 DMA controller가 특정 메모리 영역을 동시 접근하면 문제가 생길 수 있기 때문에 중재 역할

입출력(I/O)의 수행

모든 입출력 명령은 커널 모드에서 수행하여야 한다. 사용자 프로그램에서는 운영체제에게 I/O 요청 ➡ Trap(소프트웨어 인터럽트)을 사용하여 인터럽트 벡터의 특정 위치로 이동 ➡ 제어권이 인터럽트가 가리키는 인터럽트 처리 루틴으로 이동 ➡ 올바른 I/O요청인지 확인 후 수행 ➡ 제어권을 시스템콜 다음 명령으로 옮김

인터럽트(Interrupt)

각 device들이 능동적으로 자신의 상태변화를 CPU에게 알리는 방식. 인터럽트를 당하면 현 상태 정보를 메모리의 제어 스택에 저장 후 CPU의 제어를 인터럽트 처리 루틴으로 넘긴다.

하드웨어 인터럽트

하드웨어가 발생시킨 인터럽트, I/O나 timer 등.

소프트웨어 인터럽트(Trap)

소프트웨어가 발생시킨 인터럽트, 오류를 발생시키는 명령(Exception), 시스템콜(System call) 등.

💡 시스템콜(System Call)이란?

사용자 프로그램이 OS의 서비스를 받기 위해 커널 함수를 호출하는 것

인터럽트 벡터

해당 인터럽트의 처리 루틴 주소를 가지고 있음

인터럽트 처리 루틴(=인터럽트 핸들러)

해당 인터럽트를 처리하는 커널 함수

[보충 참고자료] 김주균, OS? Oh Yes! 누워서 보는 운영체제 이야기

반효경 교수님의 운영체제 강의를 듣고 정리한 게시글입니다.

운영체제란 무엇인가?

컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층

• 좁은 의미: 커널(kernel). 즉, 운영체제의 핵심 부분으로 메모리에 상주하는 부분
• 넓은 의미: 커널 뿐 아니라 각종 주변 시스템 유틸리티를 포함한 개념

운영체제의 목적

1. 컴퓨터 시스템의 자원을 효율적으로 관리

• 프로세서, 기억장치, 입출력 장치 등 효율적 관리
• 사용자 및 운영체제 자신의 보호
• 프로세스, 파일, 메시지 등 관리

2. 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 제공

• 동시 사용자/프로그램들이 독자적 컴퓨터에서 수행되는 것처럼 환경을 제공
• 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행

운영체제의 분류

동시 작업 가능 여부에 따른 분류

단일 작업(single tasking)

한 번에 하나의 작업만 처리 한 명령의 수행이 끝내기 전에 다른 명령을 수행시킬 수 없다. ex) MS-DOS

다중 작업(multi tasking)

동시에 두 개 이상의 작업 처리 한 명령의 수행이 끝나기 전에 다른 명령이나 프로그램을 수행할 수 있다. ex) UNIX, MS Windows

사용자의 수에 따른 분류

단일 사용자(single user)

한 명의 사용자만 시스템 사용 ex) MS-DOS

다중 사용자(multi user)

동시에 여러 사용자들이 시스템 사용 ex) UNIX

처리 방식에 따른 분류

일괄 처리(batch processing)

데이터 처리에서 즉시성을 필요로 하지 않을 경우, 일정량 또는 일정 기간 데이터를 모아서 한꺼번에 처리

시분할(time sharing)

여러 작업을 수행할 때 컴퓨터 처리 능력을 일정한 시간 단위로 분할(time slicing)하여 사용

실시간(Realtime)

정해진 시간 안에 어떠한 일이 반드시 종료됨이 보장되어야하는 실시간 시스템을 위한 OS로 데드라인(Deadline) 존재

• 경성(Hard) 실시간 시스템: 미사일, 원자로 제어 등
• 연성(Soft) 실시간 시스템: 동영상 재생 등

💡 몇 가지 용어 정리

task(태스크)

작업의 최소 단위로 프로세스(process), 스레드(thread) 모두 작업의 단위가 될 수 있다.

program(프로그램)

어떤 작업을 위해 실행할 수 있는 명령어의 집합인 파일

process(프로세스)

실행 중인 프로그램, 메모리에 적재되어 운영체제의 제어를 받는 상태 각 프로세스는 각각의 독립된 메모리 영역

thread(스레드)

프로세스의 실행단위, 프로세스는 하나 이상의 스레드를 가지고있다.

Multitasking(다중작업)

운영체제의 스케쥴링에 의해 task를 번갈아가며 수행하여 여러 작업(task)를 동시에 수행하는 것처럼 느끼게 하는 것

Multiprogramming(다중프로그래밍)

여러 프로그램이 메모리에 올라가 있음을 강조 ➡ for CPU 이용률 극대화

Time sharing(시분할)

CPU의 시간을 분할하여 나누어 쓴다는 의미를 강조 ➡ for 응답 시간 최소화

Multiprocessing(다중처리)

하나의 프로그램을 여러개의 프로세스로 구성하여 multiprocessor를 이용하여 병렬적으로 작업을 수행하는 것

• 프로세스 간 공유해야 할 데이터가 생기면 프로세스 사이의 통신 구축(IPC) 필요
• 장점: 안전성(메모리 침범 문제를 OS 차원에서 해결)
• 단점: 각각 독립된 메모리 영역을 갖고 있어, 작업량 많을수록 오버헤드 발생. Context Switching으로 인한 성능 저하.

Multithreading

하나의 프로세스를 여러개의 스레드로 처리하여 프로세스를 효율적으로 실행하는 것

• 스레드는 stack만 따로 할당받고 나머지 영역은 서로 공유
• 장점: 공유 메모리만큼 시간, 자원 손실 감소.
• 단점: 안전성. 하나의 스레드가 데이터 공간을 망가뜨리면, 모든 스레드가 작동 불능.

Multiprocessor

하나의 컴퓨터에 CPU(processor)가 여러 개 존재하고 있음을 의미

운영체제의 구조

• CPU 스케줄링
• 메모리 관리
• 파일 관리
• 입출력 관리
• 프로세스 관리

[보충 참고자료]

BillyTheKid님의 블로그 Murphy Gyoogle님의 👶🏻신입 개발자 전공 지식&기술 면접 백과사전

VSFe님의 github repository와 파이썬을 파이썬답게 강좌를 참고하여 작성하였습니다.

*(asterisk)

파이썬에서 *(asterisk)는 다음과 같은 상황에서 사용

• 곱셈, 거듭제곱
• List형 컨테이너를 반복해서 확장
• 가변 인자
• Unpacking

가변인자

• 입력 받은 list에서 첫번째, 마지막 값만 얻고 싶은 경우

• 입력 받은 list에서 첫번째, 마지막 값을 제외하고 싶은 경우

이런 경우 다음 예시와 같이 사용하면 된다.

_list = [1, 2, 3, 4, 5]
first_index, *rest, last_index = _list
print(rest)  # 2 3 4

위의 예시에서 rest에 사용한 것은 가변인자로 인자의 갯수가 몇 개가 될지 확실하지 않은 경우에 사용. first_index, last_index가 첫번째, 마지막 값을 가져가고, rest가 나머지를 가져간다.

Unpacking

Unpacking은 말그대로 풀어낸다는 뜻으로 list, tuple, set같은 컨테이너형 구조에서 모두 적용가능하다.

_list = [1, 2, 3, 4, 5]
print(_list) # [1, 2, 3, 4, 5]
print(*_list) # 1 2 3 4 5

그냥 _list를 출력하면 리스트 형태가 그대로 나오지만, *(asterisk)를 사용하여 unpacking하면 풀어서 출력된다.

💡 Packing

a = 1, 2, 3
print(a) # (1, 2, 3)

Packing은 말그대로 묶는다는 뜻으로, 하나의 변수에 여러 값을 할당하면 튜플로 묶인다.

List Comprehension

기본적인 List Comprehension은 파이썬 문법 부수기 포스트 참조

리스트 뿐만 아니라 tuple, set, dict도 만들 수 있다.

[심화 예시]

# 주어진 리스트를 그대로 담되, 15가 넘어가는 값은 15로 바꿔서 저장하기
_list = [i if i <= 15 else 15 for i in tmp]

# 값이 두개 들어있는 튜플을 받아 리스트를 생성하되, 튜플 내부의 값을 뒤집어서 저장하기
list_of_tuple = [(i, j) for i in range(100), for j in range(100, 0, -1)]
_list = [(j, i) for i, j in list_of_tuple]

# 두 개의 리스트를 합치되, 가능한 모든 조합을 저장하는 리스트를 만들기
x = [i for i in range(5)]
y = [i for i in range(5)]
_list = [(i, j) for i in x, for j in y]

앞 쪽에 붙는 if는 삼항 연산자의 if, 맨 끝에 붙는 if는 값을 for문의 if조건으로 값을 값을 넣을지, 뺄지 결정하는 조건

Set & Dictionary 잘 사용하기

Dictionary와 Set이 있다는 것은 알지만 어디에 사용하면 좋은지, 어떻게 해야 잘 사용할 수 있는지 알아보자

Dictionary와 Set은 Hash Table 구조를 띄고 있어 삽입, 삭제, 탐색 연산의 시간복잡도가 $O(1)$이다.

초보자들이 값을 찾기 위해 보통 list에서 in을 사용하는데 이 경우엔 순차적으로 탐색하게 되므로 데이터 양이 많아질수록 많은 시간이 소요됨.

이럴 땐 set을 사용하자.

set 사용

set을 사용하여 $O(1)$의 시간복잡도로 탐색 가능.

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
_data_set = set(data)

for i in range(10000):
    if i in _data_set:
        print(1)

set(집합)은 또한 같은 값이 들어올 수 없기에 다음과 같이 응용이 가능하다.

# 중복된 값을 포함하는 리스트에서 중복값 제거
duplicate_element = [21, 31, 65, 21, 58, 94, 13, 31, 58]
completed_list = list(set(duplicate_element)) # 21, 31, 65, 58, 94, 13

# 소문자로 바꾼후 중복된 원소들 제거
test_list = ['Test', 'test', 'TEST', 'tteesstt']
converted_list = list(set(map(lambda string: string.lower(), test_list))) # test, tteesstt

Dictionary

dictionary는 키와 쌍으로 이루어져있다.

fruit = ['apple', 'grape', 'orange']
price = [3200, 15200, 9800]
_dict = {}

for i in range(len(price)):
    _dict.append((fruit[i], price[i]))

 # {'apple' : 3200, 'grape' : 15200, 'orange' : 9000}

여기서 zip을 활용하면 더 쉽게 dictionary를 만들 수 있다.

zip

zip은 각 iterables의 요소들을 모으는 iterator를 만든다.

zip 함수에 서로 다른 길이의 리스트가 인자로 들어오는 경우 길이가 짧은 쪽까지만 이터레이션이 이루어진다.

fruit = ['apple', 'grape', 'orange']
price = [3200, 15200, 9800]

_dict = dict(zip(fruit, price))

 # {'apple' : 3200, 'grape' : 15200, 'orange' : 9000}

setdefault

딕셔너리에서 없는 값을 찾으려고 하면 오류가 난다. 이 때, setdefault를 사용하면 값이 있을 땐 해당 값을 리턴하고, 값이 없을 때는 두번째 인자로 넘겨준 값을 추가하고 추가한 값을 리턴해준다.

fruit = ['apple', 'grape']
price = [3200, 15200]
_dict = dict(zip(fruit, price))

print(_dict.setdefault('strawberry', 0)) # 0
# {'apple': 3200, 'grape': 15200, 'strawberry': 0}

defaultdict

매번 setdefault를 실행하는 데에 번거로울 때 defaultdict을 이용하면 setdefault를 암묵적으로 실행해준다.

from collections import defaultdict

movie_review = [('Clementine', 5), ('Parasite', 4.5), ('Clementine', 5)]

index = defaultdict(list)

for review in movie_review:
    index[review[0]].append(review[1]) 
# {'Clementine': [5, 5], 'Parasite': [4.5]}

print(index['Train to Busan']) # []
# {'Clementine': [5, 5], 'Parasite': [4.5], 'Train to Busan': []}

문자열 뒤집기

string = 'I am Hungry...'
print(string[::-1])
print("".join(reversed(string)))

첫 번째 방법은 모든 iterable한 데이터에서 사용 가능. 두 번째 방법은 역순으로 뒤집은 iterator 리턴하여 join이나 for i in ~ 구조 사용

기타

for, while문 에서의 else

이중 이상의 반복문에서 flag를 넣어 참/거짓 여부를 판단하여 중간에 break 하는 경우

[예제] 5개의 숫자를 차례로 곱해 나온 수가 제곱수면 found, 모든 수를 곱해도 제곱수가 나오지 않은 경우 not found 출력

import math

numbers = [int(input()) for _ in range(5)]
multiplied = 1
flag = True
for number in numbers:
    multiplied *= number
    if math.sqrt(multiplied) == int(math.sqrt(multiplied)):
        flag = False
        print('found')
        break
if flag:
        print('not found')

import math

numbers = [int(input()) for _ in range(5)]
multiplied = 1
for number in numbers:
    multiplied *= number
    if math.sqrt(multiplied) == int(math.sqrt(multiplied)):
        print('found')
        break
else:
    print('not found')

break로 반복문을 탈출하지 않았다면 else 구간으로 진입.

divmod

정수를 나눈 몫과 나머지를 구해야 할 경우 a//b, a%b를 사용할 수도 있지만 아주 큰 숫자를 다룰 때에는 divmod도 사용할 수 있다.

참고로 divmod 사용 시 tuple 형태로 return 되기 때문에 unpacking을 이용할 수 있다.

a = 7
b = 5
print(a//b, a%b)     # 1 2
print(*divmod(a,b))  # 1 2

10진법 진법 변환

** n진수 → 10진수** 변환 시 int(string, base) 사용

문자열 정렬(ljust, center, rjust)

• 좌측 정렬 : ljust(width, [fillchar])
• 가운데 정렬 : center(width, [fillchar])
• 우측 정렬 : rjust(width, [fillchar])

fillchar 생략 시 공백으로 채워짐.

s = 'abc'
n = 7

s.ljust(n) # 좌측 정렬
s.center(n) # 가운데 정렬
s.rjust(n) # 우측 정렬

[출력]

abc    
  abc  
    abc

string 모듈(상수)

모든 소문자, 대문자, 대소문자, 숫자 가져오기

import string 

string.ascii_lowercase # 소문자 abcdefghijklmnopqrstuvwxyz
string.ascii_uppercase # 대문자 ABCDEFGHIJKLMNOPQRSTUVWXYZ
string.ascii_letters # 대소문자 모두 abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
string.digits # 숫자 0123456789

가장 큰 수, inf

아주 큰 값을 할당 할 때, inf를 사용한다. inf는 어떤 숫자와 비교해도 무조건 크다고 판정된다. -inf도 사용가능

파일 입출력 간단하게 하기

with - as 구문을 이용하면

1. 파일을 close 하지 않아도 된다: with - as 블록이 종료되면 파일이 자동 close
2. readlines가 EOF까지 읽으므로, while문 안에서 EOF 체크할 필요가 없다.

with open('myfile.txt') as file:
    for line in file.readlines():
        print(line.strip().split('\t'))

https://www.acmicpc.net/problem/11718

빠르게 입력받기

[입력]

Hello
Baekjoon
Online Judge

sys.stdin.readline()

문자열 형태로 개행문자(\n)를 포함한 한 줄만 입력된다.

import sys

print(sys.stdin.readline())

[출력]

Hello

sys.stdin.readlines()

파일의 끝까지 한번에 읽어온다. 각 줄이 개행문자(\n)가 포함되어 리스트로 저장된다.

import sys

print(sys.stdin.readlines())

[출력]

['Hello\n', 'Baekjoon\n', 'Online Judge\n']

sys.stdin.read()

파일의 끝까지 한번에 읽어오고 읽은대로 출력된다.

import sys

print(sys.stdin.read())

[출력]

Hello
Baekjoon
Online Judge

sys.stdin.read().splitlines()

파일의 끝까지 한번에 읽어오고 개행문자를 제외하여 리스트로 읽는다.

['Hello', 'Baekjoon', 'Online Judge']

https://www.acmicpc.net/problem/10951

입력이 끝날 때까지 출력하기

EOFerror 예외처리

무한 루프안에서 try, except 구문으로 예외처리, EOFerror 발생 시 반복문을 빠져나온다.

while True:
    try:
        a, b = map(int, input().split())
        print(a+b)
    except EOFError:
        break

sys.stdin.readlines() 사용하기

sys.stdin.readlines()를 사용하면 파일의 끝까지 한번에 가져올 수 있다.

import sys

lines = sys.stdin.readlines()
for line in lines:
    a, b = map(int, line.split())
    print(a+b)

동빈나님의 이코테 2021을 보고 정리한 게시글입니다.

함수와 표준 라이브러리

함수

함수(Function)란 특정한 작업을 하나의 단위로 묶어 놓은 것으로 , 불필요한 소스코드의 반복을 줄일 수 있다.

함수의 종류

• 내장 함수: 파이썬이 기본적으로 제공하는 함수
• 사용자 정의 함수: 개발자가 직접 정의하여 사용할 수 있는 함수

함수 정의하기

• 매개변수: 함수 내부에서 사용할 변수
• 반환 값: 함수에서 처리 된 결과를 반환

  def 함수명(매개변수):
    실행할 소스코드
    return 반환 값

더하기 함수 예시 1)

def add(a, b):
    return a + b

print(add(3, 7))

[실행 결과]

10

더하기 함수 예시 2)

def add(a, b):
    print("함수의 결과:", a + b)

add(3, 7)

[실행 결과]

함수의 결과: 10

파라마터 지정하기

파라미터의 변수를 직접 지정할 수 있다

• 이 경우 매개변수의 순서가 달라도 상관 없다.

  def add(a, b):
    print("함수의 결과:", a + b)
  

add(b = 3, a = 7)

\[실행 결과]

함수의 결과: 10

### global 키워드

`global` 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고, **함수 바깥에 선언된 변수를 바로 참조**

```python
a = 0

def func():
    global a  #함수 바깥에 선언된 변수를 바로 참조
    a += 1

for i in range(10):
    func()

print(a)

[실행 결과]

10

여러 개의 반환 값

파이썬에서 함수는 여러 개의 반환 값을 가질 수 있다.

def operator(a, b):
    add_var = a + b
    subtract_var = a - b
    multiply_var = a * b
    divide_var = a / b
    return add_var, subtract_var, multiply_var, divide_var

a, b, c, d = operator(7, 3)
print(a, b, c, d)

[실행 결과]

10 4 21 2.3333333333333335

람다 표현식

함수를 하나의 식으로 간단하게 작성

• 함수 자체를 입력으로 받는 경우
• 함수 기능이 매우 간단한 경우
• 한번 사용하고 말 함수인 경우

print((lambda a, b: a + b)(3, 7))

[실행 결과]

10

람다 표현식 예시

일반 함수 사용)

array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]

def my_key(x):
    return x[1]

print(sorted(array, key = my_key))

람다 함수 사용)

array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]

print(sorted(array, key = lambda x: x[1]))

[실행 결과]

[('이순신', 32), ('홍길동', 50), ('아무개', 74)]

실전에서 유용한 표준 라이브러리

• 내장 함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수 제공
• itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능 제공, 특히 순열과 조합 라이브러리
• heapq: 힙(Heap) 자료구조 제공, 우선순위 큐 기능 구현 시 자주 사용
• bisect: 이진 탐색(Binary Search)기능 제공
• collections: 덱(deque), 카운터(Counter)등의 유용한 자료구조 포함
• math: 필수적 수학적 기능 제공(팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)같은 상수)

자주 사용되는 내장 함수

• sum(): 다수의 데이터를 포함하는 리스트, 튜플 등의 원소의 합
• min(), max(): 가장 작은 값, 가장 큰 값 반환
• eval(): 수식으로 표현된 하나의 식의 계산된 결과를 반환
• sorted(): 각 원소를 정렬한 결과를 오름차순으로 반환
  • reverse=True 속성을 넣어주면 내림차순 - key 속성으로 정렬 기준 명시 가능

💡sort()와 sorted() 차이는? sort()는 리스트를 내부 정렬하는 메소드고, sorted()는 컨테이너형 데이터를 받아 정렬된 리스트를 리턴하는 함수

예시1)

#sum()
result = sum([1, 2, 3, 4, 5])
print(result)

#min(), max()
min_result = min(7, 3, 5, 2)
max_result = max(7, 3, 5, 2)
print(min_result, max_result)

#eval()
result = eval("(3+5)*7")
print(result)

[실행 결과]

15
2 7
56

예시2)

#sorted()
result = sorted([9, 1, 8, 5, 4])
reverse_result = sorted([9, 1, 8, 5, 4], reverse=True)
print(result)
print(reverse_result)

#sorted() with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted(array, key=lambda x: x[1], reverse=True)
print(result)

[실행 결과]

[1, 4, 5, 8, 9]
[9, 8, 5, 4, 1]
[('이순신', 75), ('아무개', 50), ('홍길동', 35)]

itertools: 순열과 조합

• 순열(permutations): 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것
• 조합(combinations): 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것

순열)

from itertools import permutations

data = ['A', 'B', 'C']

result = list(permutations(data, 3)) #모든 순열
print(result)

[실행 결과]

[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

조합)

from itertools import combinations

data = ['A', 'B', 'C']

result = list(combinations(data, 2)) #2개를 뽑는 모든 조합
print(result)

[실행 결과]

[('A', 'B'), ('A', 'C'), ('B', 'C')]

중복 순열과 중복 조합

중복 순열)

from itertools import product

data = ['A', 'B', 'C']

result = list(product(data, repeat=2)) #2개를 뽑는 모든 순열 구하기(중복 허용)
print(result)

[실행 결과]

[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

중복 조합)

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

result = list(combinations_with_replacement(data, 2)) #2개를 뽑는 모든 순열 구하기(중복 허용)
print(result)

[실행 결과]

[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

collections: Counter

등장 횟수를 세는 기능

리스트와 같은 반복 가능한(iterable) 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려줌.

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])

print(counter['blue']) #'blue'가 등장한 횟수
print(counter['green']) #'green'이 등장한 횟수
print(dict(counter)) #사전 자료형으로 변환

[실행 결과]

3
1
{'red': 2, 'blue': 3, 'green': 1}

math: 최대 공약수와 최소 공배수

import math

#최소 공배수(LCM)를 구하는 함수
def lcm(a, b):
    return a * b // math.gcd(a, b)

print(math.gcd(21, 14)) #최대 공약수(GCD)
print(lcm(21, 14)) #최소 공배수(LCM)

[실행 결과]

7
42

💡 math.lcm 은 없나요? math.lcm은 파이썬 3.9이상의 버전에서 사용가능하므로 최대 공약수를 이용하여 구하는 방법을 알아두자.

동빈나님의 이코테 2021을 보고 정리한 게시글입니다.

입출력, 조건문, 반복문

입출력

표준 입력 방법

• input() : 한 줄의 문자열을 입력 받는 함수
• map() : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용

  #공백을 기준으로 구분된 정수형 데이터 입력
  data = list(map(int, input().split()))
  

#공백을 기준으로 구분된 데이터의 개수가 많지 않을 때 a, b, c = map(int, input().split())

### 빠르게 입력 받기
사용자로부터 `input()` 함수 보다 **입력을 최대한 빠르게 받아야 하는 경우**
* sys 라이브러리에 정의되어 있는 `sys.stdin.readline()` 메서드 이용
* 단, 입력 후 엔터(Enter)가 줄 바꿈 기호로 입력되므로 `rstrip()` 메서드 함께 이용

```python
import sys

#문자열 입력 받기
data = sys.stdin.readline().rstrip()

표준 출력 방법

기본 출력은 print() 함수 이용

• 각 변수를 콤마(,)를 이용하여 띄어쓰기로 구분하여 출력 가능
• print()는 기본적으로 출력 이후에 줄 바꿈 수행 - 줄 바꿈을 원치 않는 경우 'end' 속성을 이용

a = 1
b = 2
print(a, b)
print(7, end=" ")
print(8, end=" ")

#출력할 변수
answer = 7
print("정답은 " + str(answer) + "입니다.")

[실행 결과]

1 2
7 8 정답은 7입니다.

간단하게 출력하기(f-string)

문자열 앞에 접두사 'f'를 붙여 사용(파이썬 3.6부터) 중괄호 안에 변수명을 기입하여 간단하게 문자열과 정수 함께 넣을 수 있다.

answer = 7
print(f"정답은 {answer}입니다.")

[실행 결과]

정답은 7입니다.

조건문

프로그램의 흐름을 제어하는 문법

x = 15

if x >= 10:
    print("x >= 10")

if x >= 0:
    print("x >= 0")

if x >= 30:
    print("x >= 30")

[실행 결과]

x >= 10
x >= 0

💡 들여쓰기

파이썬은 코드의 블록(Block)을 들여쓰기(Indent)로 지정

조건문의 기본 형태

if ~ elif ~ else로, elif나 else 부분은 경우에 따라서 사용하지 않아도 된다.

if 조건문 1:
    조건문 1이 True일 때 실행되는 코드
elif 조건문 2:
    조건문 1에 해당하지 않고, 조건문 2가 True일 떄 실행되는 코드
else:
    위의 모든 조건문이 모두 True 값이 아닐 때 실행되는 코드

[예제] 성적이 90점 이상일 때: A 성적이 90점 미만, 80점 이상일 때: B 성적이 80점 미만, 70점 이상일 때: C 성적이 70점 미만일 때: F

score = 85

if score >= 90:
    print("학점: A")
elif score >= 80:
    print("학점: B")
elif score >= 70:
    print("학점: C")
else:
    print("학점: F")

[실행 결과]

학점: B

비교 연산자

특정한 두 값을 비교할 때 이용

논리 연산자

논리 값(True/False) 사이의 연산을 수행할 때 사용

기타 연산자(in, not in)

다수의 데이터를 담는 자료형 리스트, 튜플, 문자열, 딕셔너리에서 in연산자와, not in 연산자 제공

pass 키워드

아무것도 처리하고 싶지 않을 때 사용

예시) 디버깅 과정에서 일단 조건문 형태만 만들어 놓고 조건문을 처리하는 부분은 비워놓고 싶은 경우

score = 95

if score >= 90:
    pass # 나중에 작성할 소스코드
else:
    print("학점: F")

print("프로그램을 종료합니다.")

[실행 결과]

프로그램을 종료합니다.

조건문의 간소화

조건문에서 실행될 소스코드가 한 줄인 경우, 굳이 줄 바꿈을 하지 않고 간략하게 표현 가능.

score = 85

if score >= 80: result = "Success"
else: result = "Fail"

print(result)  #Success

조건부 표현식(Conditional Expression)은 if ~ else문을 한 줄에 작성할 수 있도록 해줌.

score = 85

result = "Success" if score >= 80 else "Fail"

print(result)  #Success

조건문 내에서의 부등식

파이썬에서는 다른 프로그래밍 언어와 다르게 조건문 안에서 수학의 부등식을 그대로 사용 가능.

ex) x > 0 and x < 20과 0 < x < 20은 같은 결과 반환

반복문

특정 소스코드를 반복적으로 실행하고자 할 때 사용하는 문법

• 파이썬에서는 while문과 for문이 있는데, 어떤 것을 사용해도 상관 없지만, 코딩 테스트에서 실제 사용 예시를 확인해 보면, for문이 더 간결한 경우가 많다.

• 반복문에서 끊임없이 반복되는 구문인 무한 루프(Infinite Loop)를 유의해야함.

while문

예시) 1부터 9까지 모든 정수의 합 구하기

i = 1
result = 0

#i가 9보다 작거나 같을 때 아래 코드를 반복적으로 실행
while i <= 9:
    result += i
    i += 1

print(result)  #45

예시) 1부터 9까지 홀수의 합 구하기

i = 1
result = 0

#i가 9보다 작거나 같을 때 아래 코드를 반복적으로 실행
while i <= 9:
    if i % 2 == 1:
        result += i
    i += 1

print(result)  #25

for문

in 뒤에 오는 데이터(리스트, 튜플 등)에 포함되어 있는 원소를 첫 번째 인덱스부터 차례대로 하나씩 방문

for 변수 in 리스트:
    실행할 소스코드

• for문에서 연속적인 값을 차례대로 순회할 때는 range()를 주로 사용
  • range(시작값, 끝값 + 1) 형태로 사용
  • 인자를 하나만 넣으면 자동으로 시작 값 0

예시) 1부터 9까지 모든 정수의 합 구하기

result = 0

#i는 1부터 9까지 모든 값을 순회
for i in range(1, 10):
    result += i

print(result)  #45

continue 키워드

반복문에서 남은 코드의 실행을 건너뛰고, 다음 반복을 진행하고자 할 때 사용

예시) 1부터 9까지 홀수의 합 구하기

result = 0

for i in range(1, 10):
    if i % 2 == 0:
        continue
    result += i

print(result)  #25

break 키워드

반복문을 즉시 탈출하고자 할 때 사용

예시) 1부터 5까지 정수 차례대로 출력

i = 1

while True:
    print("현재 i의 값:", i)
    if i == 5:
        break
    i += 1

[실행 결과]

현재 i의 값: 1
현재 i의 값: 2
현재 i의 값: 3
현재 i의 값: 4
현재 i의 값: 5

enumerate

인덱스와 리스트의 값 모두 전달하여 pythonic하게 반복문 작성가능

예시)

rainbow = ['빨', '주', '노', '초', '파', '남', '보']

#range 사용
for idx in range(len(rainbow)):
    print(f'무지개의 {idx + 1}번 째 색은 {rainbow[idx]}')

#enumerate 사용
for idx, color in enumerate(rainbow):
    print(f'무지개의 {idx + 1}번 째 색은 {color}')

[실행 결과]

무지개의 1번 째 색은 빨
무지개의 2번 째 색은 주
무지개의 3번 째 색은 노
무지개의 4번 째 색은 초
무지개의 5번 째 색은 파
무지개의 6번 째 색은 남
무지개의 7번 째 색은 보

동빈나님의 이코테 2021을 보고 정리한 게시글입니다.

파이썬의 자료형

정수형, 실수형, 복소수형, 리스트, 문자열, 튜플, 사전, 집합

정수형(Integer)

정수를 다루는 자료형

• 양의 정수
• 음의 정수
• 0

실수형(Real Number)

소수점 아래의 데이터를 포함하는 수 자료형

파이썬에서 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리

소수부나 정수부가 0인 소수는 0 생략 가능

#소수부가 0일 때 0을 생략
a = 5.
print(a) #5.0

#정수부가 0일 때 0을 생략
a = -.7
print(a) #-0.7

지수 표현 방식

파이썬에서 e나 E를 이용하여 지수 표현 방식을 이용할 수 있다.

• e나 E 다음에 오는 수는 10의 지수부를 의미
• 임의의 큰 수를 표현하기 위해 자주 사용
• 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단 거리를 무한(INF)으로 설정하곤 함
• 이때 가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9를 이용할 수 있다.

실수형의 정확도

오늘날 IEEE754 표준에서는 실수형을 저장하기 위해 4바이트, 혹은 8바이트의 고정된 크기의 메모리를 할당하므로, 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가진다

예를 들어 10진수 체계에서 $0.3 + 0.6 = 0.9$ 이지만 2진수에서는 0.9를 정확히 표현할 수 있는 방법이 없고 미세한 오차 발생.

a = 0.3 + 0.6
print(a) #0.8999999999999999

if a == 0.9:
    print(True)
else:
    print(False) #False로 출력

이런 경우 round() 함수 이용하여 반올림

• 123.456 소수 셋째 자리 반올림 123.46: round(123.456, 2)

수 자료형의 연산

• 나누기 연산자(/)는 결과를 실수형으로 반환
• 나머지는 나머지 연산자(%) 이용 ex) 홀수 체크 시
• 몫은 몫 연산자(//) 이용
• 이외에도 거듭 제곱 연산자(\)** 등 존재

리스트 자료형

여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형

• C나 JAVA에서의 배열(Array)의 기능 및 연결 리스트와 유사한 기능 지원
• C++의 STL vector와 기능적으로 유사
• 배열 or 테이블이라고 부르기도 함.

리스트 초기화

• 대괄호([])안에 원소를 넣어 초기화하며, 쉼표(,)로 원소 구분
• 비어 있는 리스트 선언할 때는 list() 혹은 간단히 []를 이용
• 리스트의 원소에 접근할 때는 인덱스(Index) 값을 괄호에 넣는다. 인덱스는 0부터 시작

#크기가 N이고, 모든 값이 0인 1차원 리스트 초기화
n = 5
a = [0] * n
print(a)  #결과: [0, 0, 0, 0, 0]

리스트의 인덱싱과 슬라이싱

인덱스 값을 입력하여 리스트의 특정한 원소에 접근하는 것을 인덱싱(Indexing)이라고 한다.

• 인덱스 값으로 양의 정수, 음의 정수 모두 사용 가능
• 음의 정수를 넣으면 원소를 거꾸로 탐색

a = [1, 2, 3, 4, 5]

#뒤에서 첫 번째 원소 출력
print(a[-1])  #결과: 5

리스트에서 연속적인 위치를 갖는 원소들을 가져와야 할 때는 슬라이싱(Slicing)을 이용

• 대괄호 안에 콜론(:)을 넣어서 시작 인덱스와 끝 인덱스 설정 가능
• 끝 인덱스는 실제 인덱스보다 1을 더 크게 설정

a = [1, 2, 3, 4, 5]

#두 번째 원소부터 네 번째 원소까지
print(a[1 : 4])  #결과: [2, 3, 4]

리스트 컴프리헨션(List Comprehension)

리스트를 초기화하는 방법 중 하나로 대괄호 안에 조건문과 반복문을 적용하여 리스트 초기화

예시1)

#0부터 9까지의 수를 포함하는 리스트
array = [i for i in range(10)]

print(array) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


#1부터 9까지의 수들의 제곱 값을 포함하는 리스트
array = [i * i for i in range(1,10)]

print(array) #[1, 4, 9, 16, 25, 36, 49, 64, 81]

예시2) 일반적인 코드와 리스트 컴프리헨션

#리스트 컴프리헨션
#0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = [i for i range(20) if i % 2 == 1] 

print(array) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

#일반적인 코드
#0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = []
for i in range(20):
    if i % 2 == 1:
        array.append(i)

print(array) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

• 리스트 컴프리헨션은 2차원 리스트 초기화 할 때 효과적으로 사용
• 특히 N x M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 매우 유용

좋은 예시: array = [[0] * m for _ in range(n)]

잘못된 예시: array = [[0]*m] * n 위 코드는 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식되어 특정한 인덱스 값을 변경 시 예상치 못한 결과가 나올 수 있다

#좋은 예시
#N x M 크기의 2차원 리스트 초기화
n = 4
m = 3
array = [[0] * m for _ in range(n)]

#[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
print(array) 

#잘못된 예시
#N x M 크기의 2차원 리스트 초기화
n = 4
m = 3
array = [[0]*m] * n

#[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
print(array) 

#내부 리스트가 모두 같은 객체로 인식
array[1][1] = 5
#[[0, 5, 0], [0, 5, 0], [0, 5, 0], [0, 5, 0]]
print(array)

💡 언더바( _ )는 언제 사용할까?

반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바( _ ) 사용

리스트 관련 기타 메서드

리스트에서 특정 값을 가지는 원소 모두 제거하기

a = [1, 2, 3, 4, 5, 5, 5]
remove_set ={3, 5} #집합 자료형

#remove_set에 포함되지 않은 값만을 저장
result = [i for i in a if i not in remove_set]
print(result) #[1, 2, 4]

문자열 자료형

문자열 변수를 초기화할 때는 큰따옴표(")나 작은 따옴표(')이용

• 문자열 안에 큰 따옴표나 작은따옴표가 포함되어야 하는 경우
  • 전체 문자열을 큰따옴표로 구성하는 경우, 내부적으로 작은따옴표 포함 가능 - 전체 문자열을 작은따옴표로 구성하는 경우, 내부적으로 큰따옴표 포함 가능 - 혹은 백슬래시(\)를 사용하는 경우, 큰따옴표나 작은따옴표를 원하는 만큼 포함 가능

data = 'Hello World'
print(data) #Hello World

data = "Don't you know \"Python\"?"
print(data) #Don't you know "Python"?

문자열 연산

• 문자열 변수에 덧셈(+)을 이용하면 문자열이 더해져서 연결(Concatenate)된다.
• 문자열 변수를 특정한 양의 정수와 곱하는 경우, 문자열이 그 값만큼 여러 번 더해진다.
• 문자열에 대해서도 인덱싱, 슬라이싱 이용 가능. (다만 문자열은 특정 인덱스의 값을 변경할 수는 없다. Immutable)

a = "Hello"
b = "World"
print(a + " " + b) #Hello World

a = "String"
print(a * 3) #StringStringString

a = "ABCDEF"
print(a[2 : 4]) #CD

튜플 자료형

튜플 자료형은 리스트와 유사하지만 다음과 같은 문법적 차이가 있다.

• 튜플은 한 번 선언된 값을 변경할 수 없다
• 리스트는 대괄호([])를 이용하지만, 튜플은 소괄호(())이용

튜플은 리스트에 비해 상대적으로 공간 효율적

튜플을 사용하면 좋은 경우

• 서로 다른 성질의 데이터를 묶어서 관리해야 할 때 ex) 최단 경로 알고리즘 (비용, 노드 번호) 형태로 자주 사용

• 데이터의 나열을 해싱(Hashing)의 키 값으로 사용해야 할 때 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용 가능

• 리스트보다 메모리를 효율적으로 사용해야 할 때

사전 자료형

키(Key)와 값(Value)의 쌍을 데이터로 가지는 자료형

• '변경 불가능한(Immutable) 자료형'을 키로 사용
• 파이썬의 자료형은 해시 테이블(Hash Table)을 이용하므로 데이터의 조회 및 수정에 있어서 $O(1)$의 시간에 처리 가능.

[예시]

data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'

print(data)

if '사과' in data:
    print("'사과'를 키로 가지는 데이터가 존재합니다.")

[실행결과]

{'사과': 'Apple', '바나나': 'Banana', '코코넛: 'Coconut'}
'사과'를 키로 가지는 데이터가 존재합니다.

사전 자료형 관련 메서드

• keys() 함수: 키 데이터만 뽑아서 리스트로 이용할 때 사용
• values() 함수: 값 데이터만을 뽑아서 리스트로 이용할 때 사용
• items() 함수: 키와 값을 뽑아서 리스트로 이용할 때 사용 - 단, 위 함수들은 하나의 객체로 반환되기 때문에 실제론 list() 함수를 사용하여 list로 형 변환 후 주로 사용

[예시]

data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'

#키 데이터만 담은 리스트
key_list = data.keys()
#값 데이터만 담은 리스트
value_list = data.values()
#키와 값 데이터를 담은 리스트
item_list = data.items()

print(key_list)
print(value_list)
print(item_list)

#각 키에 따른 값을 하나씩 출력
for key in key_list:
    print(data[key])
#키와 해당되는 값을 하나씩 출력
for key, value in data.items():
    print(key, value)     

[실행결과]

dict_keys(['사과', '바나나', '코코넛'])
dict_values(['Apple', 'Banana', 'Coconut'])
dict_items([('사과', 'Apple'), ('바나나', 'Banana'), ('코코넛', 'Coconut')])
Apple
Banana
Coconut
사과 Apple
바나나 Banana
코코넛 Coconut

집합 자료형

• 집합의 특징

  • 중복을 허용하지 않는다.
  • 순서가 없다.

• 집합은 리스트 혹은 문자열을 이용해서 초기화 할 수 있다.

  • 이때 set() 함수 이용
  • 혹은 중괄호({}) 안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입

• 데이터의 조회 및 수정에 있어서 $O(1)$의 시간에 처리 가능.

#집합 자료형 초기화 방법 1
data = set([1, 1, 2, 3, 4, 5, 5])
print(data)

#집합 자료형 초기화 방법 2
data = {1, 1, 2, 3, 4, 5, 5}
print(data)

[실행 결과]

{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}

집합 자료형의 연산

기본적인 집합 연산으로는 합집합, 교집합, 차집합 연산 등이 있다.

• 합집합: $A∪B$, | 연산자 사용
• 교집합: $A∩B$, & 연산자 사용
• 차집합: $A-B$, - 연산자 사용

a= set([1, 2, 3, 4, 5])
b= set([3, 4, 5, 6, 7])

#합집합
print(a | b)

#교집합
print(a & b)

#차집합
print(a - b)

[실행 결과]

{1, 2, 3, 4, 5, 6, 7}
{3, 4, 5}
{1, 2}

집합 자료형 관련 메서드

• add() : 새로운 원소 추가
• update() : 새로운 원소 여러 개 추가
• remove() : 특정한 값을 갖는 원소 삭제

data = set([1, 2, 3])
print(data)

#새로운 원소 추가
data.add(4)
print(data)

#새로운 원소 여러 개 추가
data.update([5, 6])
print(data)

#특정한 값을 갖는 원소 삭제
data.remove(3)
print(data)

[실행 결과]

{1, 2, 3}
{1, 2, 3, 4}
{1, 2, 3, 4, 5, 6}
{1, 2, 4, 5, 6}

리스트, 튜플, 사전, 집합 비교

• 리스트와 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있다.

• 사전과 집합은 순서가 없기 때문에 인덱싱으로 값을 얻을 수가 없다.

  • 사전은 키(key), 집합은 원소(Element)를 이용해 $O(1)$의 시간 복잡도로 조회

동빈나님의 이코테 2021을 보고 정리한 게시글입니다.

알고리즘의 성능 평가

복잡도

알고리즘의 성능을 나타내는 척도로, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

시간복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

공간복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

빅오 표기법(Big-O Notaion)

가장 빠르게 증가하는 항만을 고려하는 표기법

$5N^3+2N^2+1000$ 인 알고리즘을 빅오 표기법으로 나타내면 $O(N^3)$

알고리즘 설계 Tip

일반적으로 CPU 기반 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:

• C언어를 기준으로 1~3초 시간 소요
• Python을 기준으로 5~15초 시간 소요

코딩테스트 문제에서 시간제한은 통상 1~5초 가량 문제에 명시되어 있지 않은 경우 대략 5초라고 생각

[알고리즘 설계 단계]

1. 지문 읽기 및 컴퓨터적 사고

2. 문제에서 가장먼저 시간제한(수행시간 요구사항) 확인 및 분석

   시간제한이 1초인 문제

   • N의 범위가 500인 경우: 최대 $O(N^3)$ 알고리즘 설계
   • N의 범위가 2000인 경우: 최대 $O(N^2)$ 알고리즘 설계
   • N의 범위가 100000인 경우: 최대 $O(logN)$ 알고리즘 설계
   • N의 범위가 10000000인 경우: 최대 $O(N)$ 알고리즘 설계

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩