WEEK01

yeopto·2022년 4월 9일

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

SW사관학교 정글

목록 보기

3/14

22.03.31

문법

sys.stdin.readline()

input()함수말고 sys.stdin.readline()를 사용하자 → 속도가 빠름 확실히, 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력 받아진다.

import sys  
a = list(map(int, sys.stdin.readline().split()))
# a = [1, 2, 3, 4, 5]

a, b = map(int, sys.stdin.readline().split())
print(a, b)
# 입력 1 2
# 결과 a = 1, b = 2

# 여러 줄 찍을 때
T = int(sys.stdin.readline())
a = [sys.stdin.readline().split() for i in range(T)]

split()은 아무 값도 넣어주지 않으면 공백(스페이스, 탭, 엔터 등)을 기준으로 나눔.
변수 타입이 문자열 형태(str)로 저장되기 때문에, 정수로 사용하기 위해서 형변환을 거쳐야 함.

22.04.01

문법

range()
- range(1, 11)은 숫자 1부터 10까지(1 이상 11 미만)의 숫자를 데이터로 갖는 객체이다.
- range(n)은 n까지(n 미만).
- 마지막 인자는 증가값이 들어갈 수 있음.
파이썬의 경우 문자열을 더하고 곱할 수 있다는 강점이 있고, 직관성이 있는 언어.
end = ‘구분자' 는 출력 시 디폴트값인 개행문자와 다른 구분자로 출력할 수 있게 해줌.
ord()는 문자를 아스키코드 값으로 변환해주는 함수이다.
리스트 슬라이싱 → 리스트변수[시작인덱스:종료인덱스:step]으로 이루어진다. [::-1]은 역순.

22.04.02

문법

반복문에서 언더스코어(_)를 사용하는 이유는 range() 함수가 for문을 순환하면 반환하는 값을 사용할 필요가 없을때 사용한다.
파이썬에서는 데이터, 함수, 클래스, 묘듈, 패키지 등을 모두 객체로 취급한다. 객체는 자료형을 가지며 메모리를 차지한다. 이런 특징 때문에 파이썬의 변수는 값을 갖지 않는다.
변수는 객체를 참조하는 객체에 연결된 이름에 불과
모든 객체는 메모리를 차지하고, 자료형뿐만 아니라 식별 번호를 가진다.

22.04.03

Algorithm

소수 판별법 → n이 소수인지 판별 하려면 n을 2부터 n-1 까지의 수들로 나누어봤을 때 나누어 떨어지는 수가 없다면 소수다. → 이건 시간 복잡도가 n이기 때문에 비효율적이다. 약수는 대칭으로 되어있다. 예륻 들어 8은 2로 나누어도 떨어지고 4로 나누어도 떨어지는데 그럼 2만 확인하면되기에 대칭의 기준의 제곱근인 수까지 확인하면된다. → 제곱근만큼의 시간복잡도를 갖는다.
재귀함수
1. 재귀 호출된 함수가 무슨 일들을 했는지 (예를 들면 그 안에서 또 어떤 재귀 호출들이 있었는지)는 중요하지 않다. 그것이 어떤 결과를 돌려주는지만이 중요하다. → 문제의 정의를 정확하게.
2. 재귀를 사용하는 함수는 반드시 재귀 호출을 하지 않는 경우 (기저 케이스)를 하나 이상 포함해야 한다. 그러지 않으면 재귀 호출이 무한히 발생하게 된다. → 종료 조건을 반드시 명시해야함.

22.04.04

문법

'구분자'.join(리스트)
- '구분자'.join(리스트)를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 이런 식의 리스트를 'abc'의 문자열로 합쳐서 반환해주는 함수.

Algorithm

하노이 탑
1. 시작 기둥에 하나가 남았을 땐 종료.
2. N개의 원반을 옮기기 위해선 N-1개의 원반을 이웃한 기둥으로 옮겨야 한다.
3. 마지막 남은 원반 한개는 마지막 기둥으로 옮긴다.
4. 두번째 기둥에 있는 N 개의 원반 중 N-1개를 마지막 기둥으로 옮긴다
- 옮기는 횟수는 2의 n제곱 - 1 → 1개 ~ 4개 옮길 때 횟수들이 규칙성이 있음. 규칙을 찾으면 식이 저렇게 된다.
- 참고 → https://www.youtube.com/watch?v=uSSC0aKXbWQ
- 2^n - 1 구하는 과정 → https://www.youtube.com/watch?v=j-7Or640lX4
정렬
- set() → 중복을 걸러줌.
- sort() → <list>.sort(key = <function>, reverse = <bool>)
  - 원본 자체를 수정한다.
  - Tuple , Dictionary, Str 에는 사용이 불가하다.
  - key = len 이면 len대로 정렬
파이썬 코딩테스트 주요 라이브러리
- 참고 - https://mgyo.tistory.com/161

22.04.05

Computer System (CSAPP)

시스템에 관한 공부의 시작은 프로그램이 프로그래머에 의해 만들어지고, 시스템에서 실행되고, 단순한 메시지를 출력하고, 종료될 때까지의 수명주기를 추적하는 것으로 시작한다.

프로그램
- 에디터로 작성한 소스 프로그램 → hello.c 라는 텍스트 파일로 저장 → 소스 프로그램은 0 or 1로 표시되는 비트들의 연속, 바이트라는 8비트 단위로 구성됨. → 각 바이트는 프로그램의 텍스트 문자를 나타낸다.
아스키 코드
- ‘#’을 10진수로는 35, 2진수로는 0010 0011로 표현가능한데, 소스프로그램은 2진수로 이루어져있다.(바이트로 구성되어있다.)
텍스트 파일, 바이너리 파일
- 오로지 아스키 문자들로만 이루어진 파일들은 텍스트 파일이라고 부르고 다른 모든 파일들은 바이너리 파일이라고한다.
인스트럭션
- hello.c를 시스템에서 실행시키려면, 각 C 문장들은 다른 프로그램들에 의해 저급 기계어 인스트럭션들로 번역되어야 한다.
- 이 인스트럭션들은 실행가능 목적 프로그램이라고 하는 형태로 합쳐져서 바이너리 디스크 파일로 저장된다. 목적 프로그램은 실행가능 목적 파일이라고도 부른다.
- 컴파일러 드라이버는 유닉스 시스템에서 다음과 같이 소스파일에서 오브젝트 파일로 번역한다 → gcc -o hello hello.c
컴파일 시스템
- GCC 컴파일러 드라이버는 소스파일 hello.c를 읽어서 실행파일인 hello로 번역한다. 네단계를 거쳐서 실행하는데 네 단계를 실행하는 프로그램들(전처리기, 컴파일러, 어셈블러, 링커)을 합쳐 컴파일 시스템이라고 부른다.
1) 전처리 단계
- 전처리기는 본래의 C프로그램을 #문자로 시작하는 디렉티브에 따라 수정한다. 예를 들어 첫 줄의 #include<stdio.h> 는 전처리에게 시스템 헤더파일인 stdio.h 를 프로그램 문장에 직접 삽입하라고 지시한다. 그 결과 일반적으로 .i 끝나는 새로운 C프로그램이 생성됨.
2) 컴파일 단계
- 컴파일러는 텍스트파일 hello.i 텍스트파일인 hello.s로 번역하며, 이 파일에는 어셈블리어 프로그램이 저장된다.
3) 어셈블리 단계
- 다음에는 어셈블러가 hello.s 를 기계어 인스트럭션으로 번역하고 이들을 재배치가능 목적프로그램의 형태를 묶어서 hello.o 라는 목적파일에 그결과를 저장한다.
  
  4) 링크 단계
- hello 프로그램이 C컴파일러에서 제공하는 표준 C 라이브러리에 들어있는 printf 함수를 호출하는 것에 주목할 필요가 있음. printf 함수는 이미 컴파일된 별도의 목적파일인 printf.o 에 들어 있으며, 이 파일은 hello.o 파일과 어떤 형태로든 결합되어야한다. 링커 프로그램이 이 통합작업을 수행함. 그 결과 hello파일은 실행가능 목적파일로 메모리에 적재되어 시스템에 의해 실행됨.

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

22.04.06

Algorithm

N-Queen 로직
1. 초기 값을 (0,0) 위치에 퀸을 놓는다. → dfs(0)
2. 놓았으면 놓인 위치의 열을 확인 하지 않고 다음 행을 확인한다. (1, 0) → 다음행을 확인할때 dfs(i + 1) 즉, dfs(1)
3. dfs(1) 에서 그 열을 다 확인해주는데 (1,0)위치에서 위로 같은행이 있는지 확인하고, 대각선 확인해서 겹치면 false 겹치지 않으면 true
4. true 면 다음 행을 탐색 할 dfs(i + 1) 호출, false면 다음열 확인
5. dfs 종료조건은 i == n이 같아질때.

WEEK01 풀었던 문제 소스코드 - https://github.com/yeopto/SW-jungle/tree/main/WEEK01