WEEK02

yeopto·2022년 4월 17일

CSAPP SW사관학교 정글 algorithm python sw정글

SW사관학교 정글

목록 보기

4/14

22.04.07

문법

리스트 컴프리헨션
- array = [i for i in range(10)] → 기본
- array = [i for i in range(20) if i % 2 == 1] → 홀수
- array = [i * i for i in range(1, 10)] → 제곱값
global 키워드
- global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조함.
람다 표현식
- print((lambda a, b: a + b)(3, 7))

자료구조

스택(stack)
- 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조다.
- 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
큐(Queue)
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조.
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
- 파이썬에서 큐를 이용하고자 할 땐 from collections import deque 를 사용하자

알고리즘

재귀함수
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
DFS (깊이 우선 탐색)
- 동작과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

22.04.08

알고리즘

binary search
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 → 시작점, 끝점, 중간점(인덱스)을 이용하여 탐색 범위를 설정한다.
- BOJ 1920 - 수 찾기
```
import sys

n = int(sys.stdin.readline())
A = sorted(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
targets = map(int, sys.stdin.readline().split())

def binary(A, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if target == A[mid]:
        return 1
    elif target < A[mid]:
        return binary(A, target, start, mid - 1)
    else:
        return binary(A, target, mid + 1, end)

for target in targets:
    start = 0
    end = len(A) - 1
    print(binary(A, target, start, end))
```
  - 확인해볼 배열 → A
  - 있는지 없는지 확인해봐야할 숫자 리스트 → targets
  - 이진탐색은 정렬을 한 뒤 수행하기 때문에 start 값이 end값 보다 크면 못찾은 것이라서 종료조건이 start > end가 됨
  - 중간 점은 start와 end를 더해 2로 나눈다.
  - mid값인 인덱스와 target이 같으면 찾은 것이므로 return
  - target이 중간점 보다 왼쪽에 있을 때, 오른쪽에 있을 때로 조건을 나누어 줌.

Two Pointers

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

BOJ 2470 - 두용액

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split(' ')))

arr.sort()

left = 0
right = n - 1

answer = 2000000001 # 나올 수 있는 최대의 합
final = []

while left < right:
    s_left = arr[left]
    s_right = arr[right]

    total = s_left + s_right

    if abs(total) < answer:
        answer = abs(total)
        final = [s_left, s_right]
    
    if total < 0:
        left += 1
    else:
        right -= 1

print(final[0], final[1])

22.04.09

알고리즘

분할정복
- 분할 : 문제의 입력사례를 둘 이상의 작은 입력사례로 분할
- 정복 : 작은 입력사례들을 각각 정복, 작은 입력사례들이 충분히 작지 않으면 재귀 호출

22.04.10

문법

unpacking
- packing 되어있는 것에 애스터리스크(*)를 붙여주면 unpacking된다.

22.04.11

자료구조

deque
- deque는 ‘double-ended queue’의 줄임말로서 스택과 큐를 합친 것과 같은, 양방향에서 데이터를 삽입 및 추출 할 수 있는 자료형
- deque는 ‘deck’(덱)으로 발음
- deque는 빠른 고정 길이 작업에 최적화 되어있음
- 메서드(method)
  - appendleft()
    - deque의 앞에 값을 추가
  - popleft()
    - deque의 앞에 값을 빼줌
  - deque(maxlen=n)
    - maxlen=n은 deque의 최대 길이를 n으로 제한
heapq 모듈
- 데이터를 정렬된 상태로 저장하기 위해서 사용하는 heapq 내장 모듈이 파이썬에 있다.
- heapq 모듈은 이진 트리(binary tree) 기반의 “최소 힙(min heap)” 자료구조를 제공한다.
- min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치한다.
- 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2)보다 크기가 작거나 같도록 원소가 추가되고 삭제됨.
- heap[k] ≤ heap[2*k+1] and heap[k] ≤ heap[2*k+2]
- 모듈 임포트 → import heapq
- 최소 힙 생성 → heap = [] 이렇게 리스트를 생성하고 heapq 모듈을 통해 원소를 추가하거나 삭제하면 heap이 그냥 최소 힙이 된다.
- 메서드(method)
  - heapq.heappush(heap, 4)
    - heap 에 4를 추가
    - 여러 원소를 추가해보면 heap 이 자동으로 정렬된다.
  - heapq.heappop(heap)
    - 가장 작은 원소를 pop한다.
  - heapq.heapify(heap)
    - 기존 리스트를 힙으로 변환
- 최대 힙(응용)
  - heapq 모듈은 최소 힙 기능만을 동작하기 때문에 최대 힙으로 활용하려면 약간의 요령이 필요하다.
  - 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용하여 힙에 튜플을 원소로 추가하거나 삭제해서 최대값을 구해준다.
우선순위 큐
- 우선순위 큐는 데이터를 추가한 순서대로 제거하는 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조다.

22.04.12

Computer Systems (CSAPP)

1.5 - 캐시가 중요하다
- 반도체 기술의 발달로 인한 프로세서와 메모리 간 격차에 대응하기 위해 시스템 설계자는 보다 작고 빠른 캐시메모리(간단한 캐시)라고 부르는 저장장치를 고안하여 프로세서가 단기간에 필요로 할 가능성이 높은 정보를 임시로 저장할 목적으로 사용한다.
- 캐시 메모리

1.6 - 저장장치들은 계층구조를 이룬다
- 메모리 계층구조
  
  출처 - https://velog.io/@emplam27/CS-컴퓨터-시스템-1.51.7장-캐시-메모리-운영체제
- 계층의 꼭대기에서부터 맨 밑바닥까지 이동할수록 저장장치들은 더 느리고, 더 크고, 바이트당 가격이 싸짐.
- 메모리 계층구조의 주요 아이디어는 한 레벨의 저장장치가 다음 하위레벨 정장치의 캐시 역할을 한다는 것. → L1과 L2의 캐시는 각각 L2, L3의 캐시다.
1.7 - 운영체제는 하드웨어를 관리한다
- 응용프로그램이 하드웨어를 제어하려면 언제나 운영체제를 통해서 해야한다.
- 운영체제의 두가지 목적
  - 제멋대로 동작하는 응용프로그램들이 하드웨어를 잘못 사용하는 것을 막기 위해
  - 응용프로그램들이 단순하고 균일한 메커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치들을 조작할 수 있도록 하기 위해
- 프로세스
  - 운영체제는 프로세스가 실행하는 데 필요한 모든 상태정보의 변화를 추적한다. 컨텍스트라고 부르는 상태정보는 PC, 레지스터 파일, 메인 메모리의 현재 값을 포함하고 있다.
  - 예시) hello 프로그램은 두 개의 동시성 프로세스가 존재한다. 쉘 프로세스와 hello 프로세스. 처음에는 쉘 프로세스가 혼자서 동작하고 있다가 명령줄에서 입력을 기다린다. hello 프로그램을 실행하라는 명령을 받으면, 쉘은 시스템 콜이라는 특수 함수를 호출하여 운영체제로 제어권을 넘겨준다. 운영체제는 쉘의 컨텍스트를 저장하고 새로운 hello 프로세스와 컨텍스트를 생성한 뒤 제어권을 새 hello 프로세스로 넘겨준다. hello가 종료되면 운영체제는 쉘 프로세스의 컨텍스트를 복구시키고 제어권을 넘겨주면서 다음 명령 줄 입력을 기다린다. → 한개의 CPU를 가지는 단일 프로세서 시스템인 경우의 예
  - 하나의 프로세스에서 다른 프로세스로의 전환은 운영체제 커널에 의해 관리됨. 커널은 운영체제 코드의 일부분이고, 메모리에 상주함.
  - 응용 프로그램이 운영체제에 의한 어떤 작업을 요청하면, 컴퓨터는 파일 읽기나 쓰기와 같은 특정 시스템 콜을 실행해서 커널에 제어를 넘겨줌. → 커널은 요청을 수행하고 응용프로그램으로 리턴함.
- 쓰레드(Thread)
  - 각각의 쓰레드는 해당 프로세스의 컨텍스트에서 실행되고, 동일한 코드와 전역 데이터를 공유한다. 다수의 프로세스들에서보다 데이터의 공유가 더 쉽고, 쓰레드가 프로세스보다 더 효율적이다.
- 가상메모리
  - 가상메모리는 각 프로세스들이 메인 메모리 전체를 독점적으로 사용하고 있는 것 같은 환상을 제공하는 추상화이다. 각 프로세스는 가상주소 공간이라고 하는 균일한 메모리의 모습을 갖게 된다.
  - 리눅스에서, 주소공간의 최상위 영역은 모든 프로세스들이 공통으로 사용하는 운영체제의 코드와 데이터를 위한 공간이다. 위쪽으로 갈수록 주소가 증가함.
  - 가상메모리 구조
    - 프로그램 코드와 데이터 : 코드는 모든 프로세스들이 같은 고정 주소에서 시작하며 다음에 C 전역변수에 대응되는 데이터 위치들이 따라온다.
    - 힙(Heap) : 코드와 데이터 영역 다음으로 런타임 힙이 따라옴. 힙은 프로세스가 실행되면서 C 표준함수인 malloc이나 free를 호출하면서 런타임에 동적으로 그 크기가 늘었다 줄었다 한다.
    - 공유 라이브러리 : 주소공간의 중간 부근에 C 표준 라이브러리나 수학 라이브러리 같은 공유 라이브러리의 코드와 데이터를 저장하는 영역이 있다.
    - 스택(Stack) : 사용자 가상메모리 공간의 맨 위에 컴파일러가 함수 호출을 구현하기 위해 사용하는 사용자 스택이 위치함. 사용자 스택은 프로그램이 실행되는 동안에 동적으로 늘어났다 줄어들었다 한다. 함수를 호출할땐 커지며 리턴되면 줄어든다.
    - 커널 가상메모리 : 주소공간의 맨 윗부분은 커널을 위해 예약되어 있음.
- 파일
  - 파일은 연속된 바이트들이다.

참고 - 컴퓨터 시스템(Coputer Systems A Programmer's Perspective 3rd)

22.04.13

문법

Counter 모듈
- Counter는 리스트를 값으로 주게 되면 해당 원소들이 몇 번 등장했는지 세어 딕셔너리 형태로 반환.

알고리즘

bisect 모듈
- bisect는 파이썬에 내장되어있는 이진탐색 모듈
- bisect_left(list, value) 는 list에서 value가 들어갈 가장 왼쪽 인덱스 반환
- bisect_right(list, value) 는 list에서 value가 들어갈 가장 오른쪽 인덱스 반환

BOJ 10816 숫자 카드 2 - 해시(Hash)풀이

import sys

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

hash = {}

for i in card:
    if i in hash:
        hash[i] += 1
    else:
        hash[i] = 1

for i in test:
    if i in hash:
        print(hash[i], end=' ')
    else:
        print(0, end=' ')