공부

https://school.programmers.co.kr/learn/courses/30/lessons/68935

여기서의 핵심은 3진법으로 바꾼배열 nums 를 뒤집어야 3진순로 변환된 문자열이 된다는 것이다.

def radixChange(num, radix):
	if num == 0: return '0'
    nums = []
    while num:
    	num, digit = divmod(num, radix) # num에는 몫이, digit에는 나머지가 담기게 된다
        nums.append(str(digit))
    return ''.join(reversed(nums)) // 예를들어 45를 3진법으로 나타냈으면 nums에는 0021이 담기게된다.
    
  def solution(n):
  	return int(radixChange(n, 3)[::-1], 3)

https://school.programmers.co.kr/learn/courses/30/lessons/12973

def solution(s):
	stack = []
    for case in s:
   		if stack and stack[-1] == case: stack.pop()
    	else: stack.append(sase)
    
  	return 0 if stack else 1

다음의 질문에 답할 수 있는지 생각해보자

• 커널이란 무엇인가?
• 운영체제의 서비스 종류는 무엇이 있는가?
• 시스템 콜과 이중 모드는 무엇인가?

운영체제의 심장, 커널

운영체제는 현존하는 프로그램 중 규모가 가장 큰 프로그램 중 하나이다.

구글에 리눅스 코드의 줄이 몇개인지 검색해보면 2,700백만 줄이라는 것을 볼 수 있다.

운영체제는 종류가 다양하고, 제공하는 기능도 다양하다.(가장 핵심적인 서비스는 존재한다)

이러한 운영체제의 핵심 서비스를 담당하는 부분을 커널(kernel)이라고 한다.

그럼 운영체제에는 속하지만 커널에는 속하지 않는 기능도 있을까? 유저 인터페이스(User Interface)가 여기에 속한다. 사용자와 컴퓨터 간의 통로일 뿐 운영체제의 핵심 기능(커널)은 아니다.

이중 모드와 시스템 호출

사용자가 실행하는 프로그램은 자원에 직접 접근할 수 있을까? ex) 메모리, CPU, 하드디스크 등등...

정답은 안된다. 자원에 직접 접근하는 것은 위험하다. 운영체제는 응용 프로그램들이 자원에 접근하려 할 때 오직 자신을 통해서만 접근하도록 하여 자원을 보호한다.

응용 프로그램이 하드 디스크에 접근하는 것을 그림으로 살펴보자.

운영체제를 통해서 접근하는 것을 볼 수 있다.

이중 모드

• CPU가 명령어를 실행하는 모드를 크게 사용자 모드와 커널 모드로 구분하는 방식
• 사용자 모드 : 운영체제 서비스를 제공받을 수 없는 실행 모드, 커널 영역의 코드를 실행할 수 없는 실행 모드, 자원 접근 불가
• 커널 모드 : 운영체제의 서비스를 제공받을 수 있는 실행 모드, 자원 접근을 비롯한 모든 명령어 실행 가능

시스템 호출

• 커널 모드로 전환하여 실행하기 위해 호출
• 일종의 소프트웨어 인터럽트이다. (시스템 호출이 처리되는 방식은 하드웨어 인터럽트 처리 방식과 유사하다)

운영체제의 핵심 서비스

• 프로세스 관리
• 자원 접근 및 할당
• 파일 시스템 관리

프로세스 관리 

• 프로세스 == 실행 중인 프로그램
• 수많은 프로세스들이 동시에 실행된다
• 동시다발적으로 실행/생성/삭제되는 다양한 프로세스를 일목요연하게 관리한다(=프로세스와 스레드, 프로세스 동기화, 교착상태 해결)

자원 접근 및 할당

• CPU (CPU 스케줄링 : 어떤 프로세스를 먼저, 얼마나 오래 실행할까?)
• 메모리 (페이징, 스와핑 등등)
• 입출력 장치

파일 시스템 관리

• 관련된 정보를 파일이라는 단위로 저장 장치에 보관
• 파일들을 묶어 폴더(디렉터리) 단위로 저장 장치에 보관

https://school.programmers.co.kr/learn/courses/30/lessons/12930

홀수와 짝수를 구별하는 문제이다. 가장 쉬운 방법은 변수를 하나 더 만들어 짝수인지 홀수인지 구별하는 것이다.

def solution(s):
    s = list(s)
    cnt = 0 # 짝수/홀수 구분

인덱스 변수를 기준으로 2로 나누어 떨어질  때(짝수), 나누어 떨어지지 않으면(홀수) 라고 정의할 수 있다. 다만 공백을 만나면 새 단어를 준비한다는 의미이므로 짝수/홀수 구분 변수의 값을 초기화 해야한다.

def solution(s):
   s = list(s)
   cnt = 0
   
   for i in range(len(s)):
       if s[i] == ' ': # 공백을 만난 경우
          cnt = 0      # cnt 변수를 초기화해준다.
          continue
       s[i] = s[i].upper() if cnt % 2 == 0 else s[i].lower()
       cnt += 1
      
      
   return ''.join(s)

https://school.programmers.co.kr/learn/courses/30/lessons/12926

여기서 생각해봐야 할 문제는 주어진 숫자만큼 더하다 보면 숫자가 알파벳의 범위를 벗어날 수 있다는 것이다. 만약 결과가 알파벳의 범위를 벗어나면 해당 알파벳의 처음인 a 또는 A로 돌아가야 한다.(소문자z -> 소문자 a, 대문자 Z -> 대문자 A).

def solution(s, n):
	s = list(s)
    for i in range(len(s)):
     	if s[i] == ' ' : continue
        corr = ord('A') if s[i].isupper() else ord('a')
        s[i] = chr((ord(s[i]) - corr + n) % 26 + corr)
        
    return ''.join(s)

문자열의 특징

문자열(string)이란 문자(char) 또는 문자들로 구성된 집합을 의미한다. 파이썬에서는 기본적으로 "(큰따옴표)와 '(작은따옴표) 문법을 모두 지원한다. 

문자열이란

먼저 컴퓨터가 받아들이는 문자열과 사람이 보는 문자열은 차이가 꽤 크다. 모든 것을 숫자로 이해하는 컴퓨터가 문자를 인식하도록 하려면 '문자를 숫자로 변환하는 과정'을 추가로 거쳐야 하며, 이 과저에서 보통 문자 집합(character set)중 가장 대표적인 유니코드를 사용한다.

만약 변수에 문자열로 "Programmers is good"을 할당하면 컴퓨터는 사람이 선언한 문자열을 각 글자에 해당하는 숫자로 인식한다. 그리고 모든 글자에 대한 정보를 한곳에 담아야 하기 때문에 암묵적으로 배열로 선언한다. 기존의 배열처럼 [] 형태로 선언하지는 않지만 엄연히 배열로 취급하며, 배열처럼 사용한다.

1. 문자열 뒤집기

문자열을 통째로 뒤집는 것은 매우 쉽다. 문자열에 슬라이싱으로 [::-1]을 사용해 역으로 만들면 된다. 

2. 아스키 코드 다루기

파이썬에서는 문자를 숫자로 바꿔주는 ord() 함수와 숫자를 문자로 바꿔주는 char() 함수를 제공한다. 이러한 함수들을 사용하여 a에 1을 더하여 b로 만드는 드의 행동을 할 수 있으며, 기본적으로 알파벳 순회 같은 문제에서 자주 등장한다.

3. 진법 변경하기

파이썬에서는 기본적으로 자주 사용하는 2진법 bin(), 8진법 oct(), 16진법 hex() 함수를 지원하며, 이 외의 진법은 따로 함수로 구현해야 한다.

4. 기준에 맞춰 재정렬하기

알파벳순, 숫자순 등 특정 기준이 주어지면 그 기준으로 문자열을 정렬하거나 추출하는 작업이 필요한 경우, 가장 많이 사용하는 라이브러리는 collections 이며, 단어를 세는 것 이외에도 많은 일을 할 수 있어 여러 방면으로 활용된다.

5.  문자열 치환하기

string에 있는 replace() 함수를 사용하면 좋다. 

1차원 배열 + 1차원 배열?

다른 언어에서는 '배열은 한 변수에 데이터 여러 개를 선언할 수 있게 해주는 자료형'이라고 할 것이다. '배열은 연속적으로 데이터를 집어넣을 수 있는 1차원 형식의 자료 구조'라고 정의할 수 있다.

배열 안의 배열, 즉 2차원 배열은 어떨까? 2차원 배열은 다음 모습과 같다.

data = [[1,2,3],[4,5,6]]

1차원 배열을 선언하면 다음과 같이 한 방향으로 연속적인 데이터가 나열된다.

조회하려는 항목의 순서인 N에서 1을 뺀 숫자가 바로 원하는 데이터를 조회할 수 있는 인덱스이다. 여기에 배열을 하나 더 얹어 2차원으로 선언할 경우 다음과 같이 사각형이 된다.

이 배열에서 원하는 값을 찾으려면 1차원 배열과 다르게 '세로 위치 -> 가로 위치' 순으로 조회해야 한다. 세로 방향으로 먼저 행을 고른 다음, 가로 방향으로 열을 고르면 원하는 데이터를 찾을 수 있다.

2차원 배열의 가장 큰 핵심은 '그룹'이다. 1차원 배열과 다르게 본격적으로 데이터에 의미를 부여하기 시작하는 구조이며, 이런 정보를 기반으로 새로운 데이터를 구축하거나, 원하는 정보를 얻어내기 위해 조작을 한다. 

배열을 이미지로 생각하면 더욱 빠르게 정보를 이해할 수 있다.

문제 해결에 필요한 입력값과 문제를 해결하는 프로그램이 주어졌을 때, 프로그램이 입력값을 받아 동작하고 결과를 만들어내는 데 걸리는 정도를 복잡도라고 한다. 그 중 얼마나 오래 걸리는지는 시간 복잡도라고 하고, 얼마나 많은 메모리를 사용하는지는 공간 복잡도라고 한다.

빅오(Big-O) 표기법

실제로 코드를 실행해보면 소프트웨어나 하드웨어적 변수가 많아 똑같은 코드라도 환경에 따라 실행 시간이 조금씩 다르다. 이런 차이 때문에 시간을 정확한 수치로 표현하기는 어렵지만, 문법이나 구성에서 발생하는 비용을 수치화해 문제를 푸는 데 필요한 총 연산의 수를 수학적으로 표기할 수 있다. 이를 점근 표기법이라고 하며, 세 가지 표기법 중 가장 흔하게 사용하며, 최악의 경우를 계산하는 계산법을 빅오(Big-O) 표기법 이라고 한다.

빅오 표기법은 알고리즘이 해당 차수이거나, 그보나 낮은 차수의 시간 복잡도를 가지는 점근적 상한 표기 방법을 의미한다. 쉽게 '최악의 경우 이 정도의 시간이 걸린다'로 이해하면 된다.

수학적으로 정의하면 다음과 같다.

예를 들어 a 변수에 +1 을 하는 코드를 작성했다고 한다면 (코드로 a += 1) 이를 실행하기 위해 필요한 연산은 총 1번이다. 만약 데이터 개수가 n개라면 프로그램을 실행할 때 발생하는 비용을 f(x)라고 가정하면 데이터 개수만큼 연산을 1번 수행하므로 f(n) = n 이라고 표기할 수 있고, 이를 빅오 표기법으로 나타내면 O(n)이 된다.

n개의 데이터를 수행하는 데 걸리는 시간이 제곱만큼, f(n) = 4n^2 + 4n + 1이라고 한다면 동일 최대 차수인 최소 단위 시간 복잡도  g(n) = n^2이 있을 때 f(n) <= cg(n)이 성립하는 상수 c가 존재하므로 결론적으로 표기법 O(x)를 사용하여 최소 단위인 O(n^2)으로 표현할 수 있다.

즉, 연산 횟수가 최고 차항에 비례하는 흐름을 보인다면 부가적인 연산은 신경 쓸 필요가 없다. 가령 n^2 + 2n + 1 의 시간 복잡도 역시 최고 차항만 계산하여 O(n^2)으로 줄어든다. 같은 이유로 99n의 시간 복잡도는 O(n)으로 줄어든다.

시간 복잡도 그래프

각 시간 복잡도에 따른 연산 횟수를 정리하면 다음과 같다.

서버는 사용자가 누구인지 식별할 수 있어야 한다. 사용자가 누구인지 알면, 그 사용자가 어떤 작업이나 리소스에 접근할 수 있는지 결정할 수 있다. HTTP는 자체적인 인증 관련 기능을 제공한다.

HTTP의 인증요구 / 응답 프레임워크

HTTP는 사용자 인증을 하는 데 사용하는 자체 인증요구/응답 프레임워크를 제공한다. 

웹 애플리케이션이 HTTP 요청 메시지를 받으면, 서버는 요청을 처리하는 대신에 현재 사용자가 누구인지를 알 수 있게 비밀번호 같이 개인 정보를 요구하는 '인증요구'로 응답할 수 있다. 

 사용자가 다시 요청을 보낼 때는 인증 정보(사용자 이름과 비밀번호)를 첨부해야 한다. 만약 인증 정보가 맞지 않으면 서버는 클라이언트에 다시 인증요구를 보내거나 에러를 낼 수 있다. 

인증 프로토콜과 헤더

HTTP는 필요에 따라 고쳐 쓸 수 있는 제어 헤더를 통해, 다른 인증 프로토콜에 맞추어 확장할 수 있는 프레임워크를 제공한다. 아래 그림에 나열된 헤더의 형식과 내용은 인증 프로토콜에 따라 달라진다.

 HTTP에는 기본 인증과 다이제스트 인증이라는 두 가지 공식적인 인증 프로토콜이 있다. 

기본 인증

기본 인증은 가장 잘 알려진 HTTP 인증 규칙이다. 거의 모든 주요 클라이언트와 서버에 기본 인증이 구현되어 있다.

 기본인증에서, 웹 서버는 클라이언트의 요청을 거부하고 유요한 사용자 이름과 비밀번호를 요구할 수 있다. 서버는 200 대신 401 상태 코드와 함께, 클라이언트가 접근하려고 했던 보안 영역을 WWW-Authenticate에 기술해서 응답하여 인증요구를 시작한다. 브라우저는 사용자가 입력한 사용자 이름과 비밀번호를 Authorization 요청 헤더 안에 암호화해서 서버로 다시 보낸다.

Base-64 사용자 이름/비밀번호 인코딩

HTTP 기본 인증은 사용자 이름과 비밀번호 콜른으로 이어서 합치고, base-64 인코딩 메서드를 사용해 인코딩 한다. base-64 인코딩은 8비트 바이트로 이루어져 있는 시퀀스를 6비트 덩어리의 시퀀스로 변환한다. 각 6비트 조각은 대부분 문자와 숫자로 이우어진 특별한 64개의 문자 중에서 선택된다.

 아래 그림은 기본 인증에서 base-64 인코딩을 사용하는 예시이다. 사용자 이름은 'brian-totty'이고 비밀번호는 'Ow!'이다. 브라우저는 사용자 이름과 비밀번호를 콜론으로 이어서 'binary-totty:Ow!'를 만든다. 그러고 나서 이 문자열을 base-64로 인코딩해서 길고 복잡한 'YnJpYW4tdG90dHk6T3ch'를 만든다.

Base-64 인코딩은 바이너리, 텍스트, 국제 문자 데이터 문자열 받아서 전송할 수 있게, 그 문자열을 전송 가능한 문자인 알파벳으로 변환하기 위해 발명됐다. 전송 중에 원본 문자열이 변질될 걱정 없이 원격에서 디코딩할 수 있다.

컴퓨터 부품들은 전기만 공급하면 알아서 작동하지 않는다. 

모든 프로그램은 실행을 위해 자원을 필요로 한다.

자원 / 시스템 자원

• 프로그램 실행에 있어 마땅히 필요한 요소
• 컴퓨터의 네 가지 핵슴 부품

운영체제는 

• 실행할 프로그램에 필요한 자원을 할당하고
• 프로그램이 올바르게 실행되게 돕는
• 특별한 프로그램

운영체제의 메모리 관리

운영체제의 CPU 관리

운영체제의 입출력장치 관리

운영체제 덕분에 개발자는 하드웨어를 조작하는 코드를 직접 작성할 필요가 없다. 

개발자는 문제 해결 능력 - 오류 메세지에 대한 깊은 이해를 위해서는 운영체제를 알아야 한다.