알고리즘 고수가 되기까지

설명 순서는 다음과 같습니다.

1. Context Switching이란
2. Context Switching이 발생하는 이유
3. Context Switching의 자세한 과정
4. 프로세스 or 스레드 Context Switching의 비교

1. Context Switching이란

   - CPU(코어)에서 실행중이던 프로세스 or 스레드가 다른 프로세스 or 스레드로 변경되는 것을 의미

   - 오늘날의 컴퓨터에서 프로세스는 하나의 스레드를 가짐. 이유는 이 스레드가 CPU(코어)에서 작업의 단위이기 때문임. 따라서 프로세스에서 프로세스로 변경된다는 의미는 프로세스의 스레드가 다른 프로세스의 스레드로 변경된다는 의미와 같음

   - Context Switching이란 말을 풀어보면 '문맥 전환'인데, 여기서 문맥은 CPU가 한 프로세스를 실행시키기 위해서 레지스터, 캐시 또는 TLB 등등에 데이터를 올려놨다가, 다른 프로세스를 실행시키기 위해서 이러한 값들이 바뀌는 것을 의미함

2. Context Switching이 발생하는 이유

   - 컴퓨터 시스템의 변천사에서 본 것처럼, 프로세스의 응답률을 높이기 위해서 여러 프로세스가 짧은 시간동안 CPU를 번갈아가며 사용하게 되는데, 이렇게 프로세스가 바뀔때마다 Context Switching이 발생함

   - 이런 멀티태스킹 방식에서 Context Switching이 발생하는 예시를 살펴보면

   - P1 -> (컨텍스트 스위칭) -> P2 -> (컨텍스트 스위칭) -> P1 ...

   - 컨텍스트 스위칭은 OS의 커널에 의해서 실행됨

3. Context Switching의 자세한 과정

   - 진행중인 프로세스 or 스레드가 다른 프로세스 or 스레드로 바뀌려면, 진행중인 프로세스의 상태를 어딘가에 저장하고 다른 프로세스의 상태를 불러와야함. 그래야 바뀐 작업을 다시 이어나갈 수 있고, 현재 진행중인 것을 나중에 다시 이어나갈 수 있기 때문임

   - 과정

      ① 커널은 진행중인 프로세스 or 스레드의 상태정보를 특정 자료구조에 저장(프로세스는 PCB, 스레드는 TCB)

      ② 바꿀 프로세스 or 스레드의 상태정보를 가져와 그것을 바탕으로 레지스터 캐시 등에 데이터를 로드함

      ③ 바꾼 프로세스 실행

4. 프로세스 or 스레드 Context Switching의 비교

   - PCB보다 TCB가 더 가벼움. 이유는 프로세스는 독립적인 메모리를 사용하는 반면 스레드들은 같은 메모리를 공유함. 그래서 TCB는 stack 및 간단한 register 정보만을 저장하기에 더 가볍다.

   - 프로세스 Context Switching은 Cache 메모리를 초기화해야함. 이유는 프로세스들끼리는 메모리를 공유하지 않기 때문에, 사용되는 메모리 또한 다르기 때문임. 그렇지만, 스레드 Context Switching의 경우 Cache를 초기화하지 않음(다른 프로세스 간 스레드일 경우는 캐시 초기화를 함)

Context Switching에 대해 알아볼 수 있었습니다   

설명 순서는 다음과 같습니다.

1. 기본적인 용어 정리
2. 컴퓨터 시스템의 변천사
3. 스레드의 등장배경
4. 스레드의 특징

1. 기본적인 용어 정리

   - 프로그램 : 컴퓨터가 실행할 수 있는 명령어들의 집합(ex. .exe파일)

   - 프로세스 : 컴퓨터에서 실행중인 프로그램. 이 때 프로세스는 독립적인 메모리 공간을 할당받고 이 공간에 명령어들과 데이터를 가짐

   - CPU : 작업(프로세스, 쓰레드)를 처리하는 연산장치

2. 컴퓨터 시스템의 변천사

   - 처음에는 단일 프로세스 시스템부터 시작

   - 단일 프로세스 시스템이란 한번에 하나의 프로세스만 동작할 수 있음. 풀어서, 현재 실행하는 프로세스를 먼저 끝내고 종료시킨 후 다음 프로세스를 진행하는 방식임

   - 이 방식은 프로세스가 실행도중 Input/Output 작업을 만나서 CPU를 사용하지 않게되면, CPU는 계속 쉬고 있는 단점이 발생함

   - 따라서, CPU의 사용률을 높이기 위해 '여러 개의 프로세스를 메모리에 올려놓고, 현재 진행중인 프로세스가 CPU를 사용하지 않을때, 대기중인 프로세스가 CPU를 사용할 수 있게 하자'는 방식이 등장 -> 멀티 프로그래밍 방식(아마도 멀티프로그래밍 방식의 등장으로 CPU 스케쥴링이 등장한 것이라고 생각)

   - 하지만, 이렇게 프로세스를 여러개 올려놓는 방식도 문제가 있음

   - 한 프로세스가 CPU를 오래 사용하는 작업이라면 뒤에 짧게 사용하는 프로세스는 모두 대기해야함(이러한 단점도 CPU스케쥴링에서 비선점형 방식의 단점이라고 생각). 프로세스의 응답시간이 낮음

   - 그래서, '프로세스는 한번 CPU를 사용할 때 아주 짧은 시간동안만 사용하도록 해서 응답률을 높이자'는 방식이 등장 -> 멀티 태스킹 방식(마치 여러개의 작업을 동시에 처리하는 것처럼 보이게 함. 실제는 프로세스를 빠르게 번갈아가며 실행시키는 방식임)

   - 실행되는 프로세스가 바뀔 때, 그 프로세스가 사용하는 데이터를 불러오는 Context-Switching이라는 비용이 발생하더라도 응답률을 높이기 위해 trade-off

3. 스레드의 등장배경

   - CPU의 성능을 계속 발전시키에는 발열등의 이슈로 한계에 봉착

   - 그래서, CPU안에 코어를 여러개 둠으로써 성능을 향상시키는 방법을 사용

   - 그러면 이제 중요한 이슈는 '어떻게 여러개의 코어를 잘 사용할까'임

   - 이를 해결하기 위해 '프로세스를 여러 개의 프로세스로 나누고 이 작업들을 각자의 코어에서 돌리자'는 방식이 등장 -> 멀티 프로세스 방식

   - 그런데 여기서 더 개선하고 싶은 여지가 있음

      ① 프로세스는 독립된 메모리 공간을 사용해서, 서로 데이터를 공유하기가 어려움

      ② 프로세스 간 Context-Switching 비용을 줄이고 싶음

   - 그래서, 한 프로세스 내부에서 '서로 데이터를 공유하기 쉽고', 'Context-Switching 비용이 적은' 작업 단위인 스레드가 등장

4. 스레드의 특징

   - 이제 한 프로세스를 여러 개의 작업으로 나눌 수 있고, 한 프로세스 내부에서 서로 데이터를 공유하기 쉽고 Context-Switching 비용이 적은 하나의 작업 단위인 스레드를 사용할 수 있음

   - 그리고 이 스레드는 코어가 실행되는 '작업의 단위'가 됨

   - 정리해보면

      ① 한 프로세스는 여러개의 스레드를 가질 수 있음

      ② 스레드는 코어에서 실행되는 작업의 단위임

      ③ 같은 프로세스의 스레드들끼리는 프로세스의 메모리를 공유 -> 그래서 데이터 공유가 쉬움. 스레드들이 독립적으로 사용하는 stack 영역이 있고, code, data, heap영역은 다른 스레드와 공유함

      ④ 위 ③으로 인해, 프로세스에 비해 Context-Switching 비용이 적음

         * 메모리를 공유하기 때문에, PCB에 비해서 TCB는 간단한 정보만 들어있기 때문

         * 프로세스 내 스레드 간 Context-Switching인 경우, 캐시 메모리를 초기화하지 않음(그 스레드 또한 같은 데이터를 사용하기 때문)

       ⑤ 하지만, 서로 다른 스레드가 데이터를 공유하다보니, 이런 자원들의 동기화를 해결해야하는 문제가 있음

프로세스와 스레드에 대해 알아볼 수 있었습니다. 

부트캠프 강의 - java

1. 문제
   - '다형성'이란?

2. 시도
   - 글을 찾아보자

3. 해결
   - '다형성'이란 말 그대로 '다양한 형태를 가질 수 있음'이란 뜻임
   - 결국 어떤 한 객체가 여러가지 타입이 될 수 있다는 뜻
   - 이 말을 좀 더 java스럽게 풀어보면, 상위클래스 타입의 참조변수로 하위 클래스의 객체를 참조할 수 있도록 하는 것임
   - 이 상위타입 참조변수는 생성된 하위클래스가 무엇인지에 따라서 같은 메소드를 실행하더라도, 오버라이딩된 것에 따라 다른 결과가 나올 수 있음

4. 알게된 점
   - 다형성 -> 다양한 형태를 가질 수 있다 -> 상속관계에서 두드러지게 나타남

1. 문제
   - System.identityHashCode()가 반환하는 값은 뭘까?

2. 시도
   - 직접 출력해보자

3. 해결
   - Object 클래스의 toString은 결국 해당 객체의 hashCode를 hexString(16진수)로 바꾼 값을 출력함
   - 그리고 Object 클래스의 hashCode는 객체의 메모리 주소를 기반으로 생성됨
   - 따라서, System.identityHashCode의 값은 메모리 기반으로 생성된 해시코드의 값을 출력하는 것
   - 실제로 객체를 하나 만들고 그 객치의 System.out.println()과 System.out.println(Integer.hexString(System.identityHashCode))의 값은 같음

4. 알게된 점
   - System.identityHashCode()는 객체의 메모리 주소 기반으로 생성된 hashcode값을 반환함

1. 문제
   - getClass와 instaceof 의 차이

2. 시도
   - 직접 알아보자

3. 해결
   - Parent p = new Child()일 때
   - getClass는 객체가 무엇으로 생성되었는지를 나타냄 -> p.getClass() == Child.class임
   - instaceof는 가능한 타입 모두를 나타냄 -> p instaceof Parent 또는 p instaceof Child 모두 가능

4. 알게된 점
   - getClass는 생성된 클래스, instanceof는 타입으로 가능한 클래스라는 차이가 있음

1. 문제
   - @FunctionalInterface의 의미

2. 시도
   - 강의

3. 해결
   - 애너테이션은 컴파일러에게 정보를 줄 때 사용
   - @FunctionalInterface 애너테이션은 해당 interface의 추상메서드는 1개라는 점을 알려주는 애너테이션
   - 그래서 만약 이 애너테이션을 사용하고 추상 메서드를 두 개이상 선언했을 때, 컴파일에서 에러가 남
   - 함수형 인터페이스는 람다를 쓸 수 있다를 알려주는 뜻이기도 함

4. 알게된 점
   - @FunctionalInterface는 추상메서드가 한개인 interface를 알려주는 애너테이션(개발자와 컴파일러 모두에게 알려줌) 

코테 준비

1. 백준 1509 - 팰린드롬 분할

: dp는 완전탐색에서 똑같은 탐색을 두 번다시 안하게 하는 기법. 탑다운 방식으로 재귀함수를 이용해서 먼저 구현하고, 이 후 중복되는 탐색을 dp배열을 이용해서 제거한다.

2. 백준 2482 - 색상환

: 모든 경우는 하나를 선택했을 때와 하나를 선택하지 않았을 때 발생하는 일의 합. 좀 더 쉽게 생각하자

오늘 고생했다!!! 

부트캠프 강의 - java

1. 문제
   - override가 동적 바인딩이라고 불리는 이유?

2. 시도
   - Superclass s = new SubClass(); s.f(); 일 때, s.f()가 SubClass의 f함수가 호출됨

3. 해결
   - 컴파일 단계에서는 s.f()는 SuperClass에 f()가 있으므로 문제가 없다고 인식하고 컴파일 완료
   - 이 후 런타임 시점에 s.f()를 실행할 때, 먼저 jvm은 s를 힙에서 찾음
   - s의 타입은 SuperClass이므로 먼저 상위타입에서 해당 메서드를 찾음
   - 그런 후, 이 인스턴스가 상속관계이므로 하위타입에서 f()가 재정의 되어있다는 것을 확인하고 아래 메서드를 찾아서 실행
   - 이렇게 런타임시에 호출하는 메서드를 동적으로 찾아서 결정하는 것을 '동적바인딩'이라고 부름

4. 알게된 점
   - overloading은 컴파일 시점에 호출하는 메서드를 찾아 결정하기 때문에 '정적바인딩'
   - overriding은 런타임 시점에 호출하는 메서드를 찾아 결정하기 때문에 '동적바인딩'

1. 문제
   - 람다 캡처링에 대해 자세히 알아보자

2. 시도
   - 람다 내부에서 지역변수를 사용할 때, 사용하려는 지역변수는 final이거나 effectively final이어야 함(지역변수의 값이 바뀌면 안됨)
   - 이유가 뭘까

3. 해결
   - 가장 먼저 JVM 메모리 구조에서 지역변수는 stack에, 인스턴스는 heap에 생성됨
   - 람다도 결국 인스턴스임. 따라서 heap에 생성됨
   - 따라서, 지역변수와 람다는 생성과 소멸 주기가 다름
   - 지역변수는 stack에서 사라졌지만, 람다는 heap에 여전히 남아있을 수 있음. 그래서 람다에서 사라진 지역변수를 참조하려고 하면 에러가 남
   - 그래서 java에서는 이러한 문제를 해결하기 위해 '람다 캡처링'을 사용함
   - 람다에서 사용하려는 지역변수를 '캡처(복사)'해서 사용함
   - 그리고 람다를 생성하는 시점과 쓰레드에서 실행하는 시점이 다를 수 있는데, 그 사이에 지역변수 값이 바뀌게 되면 문제가 발생할 수 있음
   - 그래서 람다에서 사용하는 지역변수는 final이거나 effectively final이어야 함

4. 알게된 점
   - 람다 캡처링을 알기위해서는 jvm 메모리 구조부터 중요하다
   - 기본기는 배신하지 않는다

코테준비

1. 백준 15683 - 감시

: CCTV를 어떻게 둘러보는지를 표현하는게 관건이었던 문제. 나머지는 편안한 재귀였다

2. 백준 17825 - 주사위 윷놀이

: map자체를 표현하는 게 관건이었던 문제. 나머지는 재귀 후 시뮬레이션하는 문제였다

오늘 하루도 고생했다

설명 순서는 다음과 같습니다.

1. 쿠키, 세션의 등장 배경
2. 쿠키의 동작 방식
3. 세션의 동작 방식

1. 쿠키, 세션의 등장 배경

   - 웹을 이용할 때 사용하는 프로토콜인 HTTP는 stateless임.

   - 이 뜻은 서버로 가는 모든 요청이 독립적이라서 이전에 보낸 요청과 연관성이 없다는 뜻임.

   - 그래서 만약 A가 어떤 웹사이트에 로그인을 했다면, A는 그 서버에 '나는 로그인한 사용자 A'라는 정보를 보내줘야함.

   - 이렇게 stateless한 HTTP 프로토콜에 state를 유지할 수 있게 도와주는 역할이 쿠키와 세션임 

2. 쿠키의 동작 방식

   - 동작 방식(ex. 아이디 기억)

      ① 브라우저는 아이디와 비밀번호를 입력하고, 'id 저장'이라는 체크박스를 체크 후 서버에 전송

      ② 서버는 'id 저장'이 true인 것을 확인하고, [ "rememberId" : "i123d" ] 라는 쿠키를 만들어서 브라우저에 전송

      ③ 해당 쿠키는 브라우저에 저장되고, 이 쿠키는 해당 서버에 요청할 때 자동으로 보내지게 됨

      ④ 로그인 입력창에 갔을 때, 서버는 해당 요청에 key가 "rememberId"인 쿠키가 있는 것을 확인하고, 그 value인 "i123d"를 아이디 창에 보여줌

   - 위와 같은 방식으로 이전에 했던 요청과 현재 요청을 연결함

3. 세션의 동작 방식

   - 세션은 쿠키와 함께 동작함

   - 동작 방식(ex. 로그인)

      ① 브라우저는 아이디와 비밀번호를 서버에 전송

      ② 서버는 아이디와 비밀번호가 일치하면, 해당 유저의 정보를 세션 저장소(메모리, DB...)에 저장하고 그 공간을 가리키는 unique한 id를 쿠키로 만들어서 브라우저에 전송

      ③ 브라우저는 이 후 다른 웹페이지를 요청하더라도 해당 쿠키를 같이 전송

      ④ 서버는 쿠키값을 이용해서 세션 저장소를 확인하고, 해당 요청이 로그인된 사용자라는 것을 인지

   - 위와 같은 방식으로 이전에 했던 요청과 현재 요청을 연결

   - 여기서 쿠키는 단지 세션의 unique한 id를 전달하는 것이고, 중요한 user의 정보는 모두 세션(서버쪽)에 저장됨

   - 하지만, 세션/쿠키 방식은 서버에 많은 사람의 정보를 갖고있어야한다는 점에서 서버에 부하가 올 수 있음

   - 이런 세션/쿠키 방식을 보완하기 위해 token방식이 등장(-> 다음에 조사해봐도 좋을듯)

쿠키와 세션에 대해 알아볼 수 있었습니다.

부트캠프 강의 - java

1. 문제
   - 메서드 안에 클래스를 정의해서 사용할 경우, 왜 지역 클래스 내부에서 메서드의 지역변수를 바꿀 수 없을까?

2. 시도
   - 강의, 책, 블로그를 통해 확인해보자

3. 해결
   - 지역 클래스와 메서드 내의 지역변수는 생성 및 소멸 시기가 달라서 그렇다
   - 지역 클래스의 instance는 heap에 생성되고 지역변수는 stack에 생성되는데, 만약 생성된 instance가 이미 stack에서 사라진 지역변수를 사용할 수 없기 때문임
   - 또한, 지역 클래스에서는 final로 된 지역변수에만 접근할 수 있다
   - 이유는 지역클래스는 이렇게 생성과 소멸이 다른 지역변수를 사용하기 위해서 지역변수의 복사본을 가져옴
   - 그런데, 만약 지역변수가 final이 아니라 계속 변한다면 여러 Thread들 간의 동기를 맞출 수 없음
   - 그래서 결국 지역클래스에서 지역변수를 사용하려면, 지역변수가 final이어야함(또는 effectively final)

4. 알게된 점
   - 이러한 지역클래스가 나중에 익명클래스, 람다와 연결되는 것 같다. 확실하게 알아두자

코테 준비

1. 백준 4256 - 트리

: preorder와 inorder에서 규칙을 찾고, 이에 따라 재귀함수를 작성. 규칙을 찾는것과 이를 재귀함수로 옮기는 것, 이 두 가지를 모두 숙달시켜야함

2. 백준 17480 - 개구쟁이 준석이

: 일단 해당 문자열에서 알파벳 갯수를 세는 방법으로는 26개의 알파벳 배열을 만들어서 해당 문자열의 index의 값을 증가시키는 것이 있음. 만약 문제에서 재귀함수의 방법이 주어졌다면, 해당 방법을 정확하게 구현하는 것이 핵심

오늘 하루도 고생했다!!!

설명 순서는 다음과 같습니다

1. 트랜스포트 계층의 역할
2. TCP란
3. 3 way handshake & 4 way handshake

1. 트랜스포트 계층의 역할

   - 트랜스포트 계층 프로토콜은 각기 다른 호스트에서 동작하는 애프리케이션 프로세스를 논리적으로 연결하는 역할을 담당함

   - 서로 다른 프로세스 간 데이터를 전달하고 받는 프로토콜

   - 주 목적

      ① 내 프로세스에서 받은 데이터를 다른 프로세스에게 전달

      ② 다른 프로세스에서 받은 데이터를 내 프로세스에게 전달

   - '전달'이 핵심

2. TCP란

   - 인터넷 애플리케이션 계층에게 주어지는 트랜스포트 계층 프로토콜 중 하나

   - TCP 프로토콜의 특징은 '데이터의 신뢰성'을 보장한다는 것임

   - '데이터의 신뢰성'이란 보낸 데이터가 그대로 수신자에게 전달됨을 보장한다는 뜻임

   - 만약 A와 B가 메시지를 주고 받는다고 가정하면 고려해야할 사항은 다음과 같음

      ① 메시지를 보내기 전 'B가 살아있을까? B가 맞을까?'를 확인(B 또한 A를 확인)

         : B가 받지 못하는 상황이거나 엉뚱한 사람에게 보내면 안되므로, 이를 확인하는 과정이 필요 -> 3 way handshake

      ② 보낸 메시지가 순서대로 잘 전달되었을까?

         : 패킷 단위로 전달이 되는데, 이 때 받는 순서는 바뀔 수 있음. 하지만, 보내는 사람이 패킷에 번호를 붙이고 받는 사람은 이 번호를 이용하여 다시 순서대로 재조립할 수 있게해야 함

      ③ 보낸 메시지가 모두 다 전달되었을까?

         : 보낸 패킷이 모두 전달되어야함. 따라서, 받는 사람은 패킷을 받을 때 마다 받았다는 응답을 주면 보낸 사람은 받았다는 응답 갯수로 패킷이 모두 전달되었는지 알 수 있음

3. 3 way handshake & 4 way handshake

   - 3 way handshake는 데이터를 주고받기 전, 두 엔드포인트간 서로를 확인하는 과정임

   - 진행되는 순서는 다음과 같음

      ① A는 B에게 '내가 너한테 데이터를 전달해도 되지?' 라는 메시지를 보냄 -> SYN

      ② B는 A에게 '응, 나도 너한테 데이터를 전달해도 되지?' 라는 메시지를 보냄 -> ACK + SYN

      ③ A는 B에게 '응' 이라는 메시지를 보냄 -> ACK

   - 이렇게 총 3단계를 거쳐서 데이터를 주고받기 전에 미리 '연결'을 시켜놓음 -> TCP의 연결지향형 특징

   - 4 way handshake는 연결을 끊을 때 하는 과정임

   - 진행되는 순서는 다음과 같음

      ① A가 B에게 '데이터를 다 보냈으니 연결을 끊을게' 라는 메시지를 보냄 -> FIN

      ② B는 A에게 '응' 이라는 메시지를 보냄 -> ACK

      ③ B또한 데이터를 다 보냈을 경우 A에게 '나도 연결을 끊을게' 라는 메시지를 보냄 -> FIN

      ④ A는 '응' 이라는 메시지를 보냄 -> ACK

      ⑤ 종료

   - 서로 주고받은 데이터가 완료되었음을 확인하고 안정적으로 연결을 종료

3 way handshake와 4 way handshake에 대해 알아볼 수 있었습니다.

코테 준비

1. 백준 17472 - 다리 만들기 2

: 풀어본 문제지만 전에는 mst를 이용하지 않고 dfs로 풀었다. input이 작았기에. 이번에는 크루스칼 알고리즘을 이용해서 풀어보았다. 크루스칼 알고리즘의 핵심은 간선들을 비용이 작은 순으로 정렬하고, 하나씩 골라가면서 union-find를 이용해서 연결되어있는지 확인한다.

2. 백준 1774 - 우주신과의 교감

: 크루스칼 알고리즘으로 풀이. mst일시 꼭 기억하자

문시해알 다시 적용시켜서 TIL 살려보자!!!