알고리즘 고수가 되기까지

CS 정리

1. CPU 스케줄링 정리

2. 캐시 정리

코테 준비

1. 백준 1162 - 도로포장

: 다익스트라는 bfs의 연속이라고 보면 쉽다. 방문처리를 boolean으로 하는 것이 아닌 거리로 표현하여 이용하는 것임을 기억하자

2. 백준 2151 - 거울설치

: 방문처리를 할 때 어떤 것이 겹칠지를 더 상세히 생각해보자.

점점 TIL이 짧아지고있지만... 항상 복습하면서 꾸준히 쓰자!!!

부트캠프 온라인 강의

1. 상속은 언제 사용할까?

   (1) 일반적으로 코드의 재사용성으로 알고 있지만, 그 뿐만이 아님

   (2) 부모의 클래스를 좀 더 확장 또는 구체적으로 만들때 사용

1. 문제
   - 부모의 private 메서드를 override 가능할까?

2. 시도
   - 직접 해보자

3. 해결
   - 부모의 private은 접근 자체가 불가능해서 되지 않는다

4. 알게된 점
   - override 조건
      ① 이름이 같고, 매개변수가 같고, 반환타입이 같아야함
      ② 부모보다 접근제한자가 더 넓어야 함
      ③ 부모보다 많은 수의 예외를 발생할 수 없음
      -> 만약 자식에서 예외를 발생한다면, 부모에서도 예외를 던지게끔 바꿔야함
      -> 만약 부모에 throw가 있다고 하더라도 자식 메서드는 예외를 던지지 않아도됨
   - private은 오로지 그 클래스 내부에서만 사용할 수 있음

코테준비

1. 백준 9466 - 텀 프로젝트

: 사이클을 찾고, 사이클에 해당하는 노드들의 개수를 세는 것. 다양하게 dfs를 적용시켜보자

2. 백준 1937 - 욕심쟁이 판다

: dfs를 이용한 dp문제. 많이 풀어본 유형이라 쉽게 끝낼 수 있음

내일은 네트워크 준비 착실히 해가자. HTTP와 HTTPS의 차이, 대칭키 공개키에 대해서 공부하자

코테준비

1. 백준 7662 - 이중 우선순위 큐

: 처음에는 두 개의 우선순위 큐를 이용해서 구현했다. 이 후 다른사람들의 풀이를 보고 TreeMap 자료구조를 알게되었다. 데이터 삽입, 삭제시 시간복잡도 O(logN)이므로, 정렬된 데이터에서 빈번하게 삽입과 삭제가 일어날 때 유용하게 사용할 수 있는 자료구조라고 생각했다.

2. 백준 17280 - 카풀 매칭

: end가 작고 start가 작은 운전자부터 매칭을 시작한다. 승객을 TreeMap 자료구조에 넣어놓고 운전자부터 lower_bound를 찾아서 승객과 매칭시켜준다. 그리디 알고리즘이 어려운 이유는 어떻게 탐욕적으로 선택할 것인가 이다. 다양한 문제를 풀어보며 방법을 익혀야한다고 생각한다.

부트캠프 온보딩강의 빠르게 clear한 후에 넘어가자. 할 것이 많다.

부트캠프 실시간 강의

1. 문제
   - 가변인자(ex. int... numbers)에서 인자를 전달하지 않으면 매개변수에 어떻게 들어갈까?
   - 인자로 null을 전달하면?
   - 가변인자 사용시 내부적으로 배열을 사용한다고 알고 있다. 위 두 상황일 경우 어떻게 될지 알아보자

2. 시도
   - 직접 확인해보자

3. 해결
   - 인자에 아무것도 전달하지 않을 경우(ex. sum()) -> numbers에는 길이가 0인 배열이 들어감
   - 인자에 null을 전달했을 경우(ex. sum(null)) -> numbers에 null이 들어감
   - 인자에 배열을 전달했을 경우(ex. sum(arr)) -> numbers에 arr의 주소가 들어감
   - 인자에 2차원 배열을 전달했을 경우 -> 컴파일 에러 발생, 가변인자는 1차원 배열만

4. 알게된 점
   - 가변인자는 sum(a, b, c) 이렇게 보통 사용되고, 내부적으로 배열을 생성해서 사용한다
   - 인자를 전달하지 않았을 경우 길이가 0인 배열이 전달된다

코테준비

1. 백준 1991 - 트리 순회

: 기본적인 트리 문제. 나중에는 정확한 트리를 구현해서 문제를 풀어보자

2. 백준 1967 - 트리의 지름

: 트리 탐색 문제. 모든 노드에서 갈 수 있는 최대 거리리 중 최대를 구하는 문제

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

부트캠프 강의

1. 문제
   - char c2 = c1++; 가 왜 컴파일 에러가 나지 않을까?
   - int 하위 타입은 연산될 때 int로 변환되는 것으로 알고있었음
   - 따라서, c2에 담으려면 (char)로 형변환을 해줘야할 것 같다고 생각함

2. 시도
   - 다양한 케이스를 시도해보자

3. 해결
   - c1++;이 컴파일 에러가 나지 않는 이유
   : c1++는 형변환 없이 c1에 있는 값을 1 증가시키기 때문임
   - char c2 = c1 + '1'은 컴파일 에러
   : 앞서 생각한 것과 같이 c1과 '1' 모두 int로 변환돼서 연산되기 때문
   - char c2 = 'a' + 1은 컴파일 에러가 나지 않음
   : 리터럴 간 연산은 컴파일 시점에 미리 계산돼기 때문에 c2 = 'b'로 바뀜

4. 알게된 점
   - c1++과 같은 단한연산자는 형변환이 일어나지 않음
   - 내가 기억하고 있는 int 아래 형은 모두 int로 변환돼서 연산됨(잘 기억하고 있었다)
   - 리터럴 간 연산은 컴파일 시점에 미리 계산됨

코테준비

1. 백준 10800 - 컬러볼

: 생각한 방향에서 시간복잡도를 계산하고 정확하게 구현하자. 그러면 풀 수 있다!!!

2. 백준 1826 - 연료 채우기

: 왜 헤맸을까? 사실 굉장히 간단한 로직인 '갈 수 있는 주유소 중에서 가장 많은 주유를 할 수 있는 곳을 선택한다'가 전부인데. 아직은 이런 문제가 나왔을 때 이러한 풀이법을 처음 접해서 그런것이라고 생각하자. 너무 조급하게 생각하지말고 천천히 익혀나가보자

오늘 하루고 고생 많았다!!!

부트캠프 강의 - OOP

1. 객체 자신을 가리키는 this

   (1) this

      ① 인스턴스 자신의 메모리를 가리킴

      ② 생성자에서 다른 생성자를 호출할 때 사용

      ③ 자신의 참조값을 가리킴

   (2) 만약에 day.setYear(2000) 메소드가 호출되면, 호출 스택에 setYear메서드가 올라가고 그 스택에 this도 함께 올라감. 그래서 this를 사용할 수 있음

   (3) 생성자에서 다른 생성자를 호출할 경우, 인스턴스 생성이 완전하지 않으므로 this()이전에 다른 statement를 작성할 수 없음

나머지는 아는 내용이므로 pass

코테준비

1. 백준 27652 - AB

: A에 들어가는 모든 접두사와 B에 들어가는 모든 접미사를 Hash에 담아서 정리해서 풀이했음. 그렇지만 더 좋은 방법은 Trie를 만들어서 하는 방법이 더 적절할 듯함. 나중에 Trie를 공부할 때 다시 풀어보면 좋을 문제!!!

2. 백준 10840 - 구간 성분

: 구간에 있는 알파벳의 종류와 숫자를 26개의 문자열(ex. 019000...00)로 만들어서 풀이. 맞긴했지만... 다시 생각해보니 갯수마다 구분자를 넣어줘야할 것 같다. 그렇지 않으면 중복될 경우도 있다. 테스트 케이스가 부족해서 운좋게 맞았다.

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

코테준비

1. 백준 3078 - 좋은 친구

: 큐에 K만큼 담고, 그 안에서 같은 길이의 이름의 갯수를 더해주면 친구 쌍의 총 수를 구할 수 있다. 이름 길이에 따라서 카운트 배열을 갱신해 나가는 것이 포인트

2. 백준 11577 - Condition of deep sleep

: 분명 큐를 써야한다는 것을 알았는데도 방법을 떠올릴 수 없었다. 왜일까??? 전구를 끄는 순서는 중요하지 않다는 것까 알았다. 3 - 1 - 2 순서로 끄나, 1 - 2 - 3 순서로 끄는 것이 상관이 없었다.

첫 번째 생각하지 못한 점은 한번 끈 전구를 다시 끌 필요가 없다는 점이다. 1번 전구를 한 번 껐으면, 다시 킬 일은 없다. 왜냐면 이럴경우 그냥 안키면 되는 것이므로

두 번째 생각하지 못한 점은 그리디하게 접근해서 앞에서부터 전구를 끄는 것이다. 앞에서부터 차례로 켜져있을 경우 K개만큼 스위치를 누르는 생각을 못했다. 아마도 워낙 완전탐색 문제만 많이 풀다보니 이것에 익숙해져있고, 더 나은 생각을 하지 못하는 것 같다. 단순하게 완전탐색만 생각하는 것이 아닌, 더 좋은 방법이 없는지 고민하는 습관을 들이자!!!

만약 두 번째까지 생각했다 하더라도 큐까지 쓰는 것을 생각하지 못했을 것 같다.

이번 스택과 큐 문제를 풀면서 느낀점은 '완전탐색으로 풀 수 없는 시간복잡도 문제와 무언가 그 주변에 관련된 일을 묻는 문제라면 스택과 큐를 쓰는 것을 고려하자'라는 생각을 했다. 어떻게 스택과 큐를 쓰는 것인지는 좀 더 다양한 문제를 접해보며 차차 키워나가야 한다고 생각한다.

내가 필요한 것들 공부할 것들 이번주 내로 정리해서 하나씩 나아가보자. 오늘도 고생했다!!!

부트캠프 - 온보딩

1. HTTP 요청과 응답

   (1) 프로토콜이란 ?

      ① 서로간의 통신을 위한 약속 규칙

      ② 주고 받을 데이터에 대한 형식을 정의한 것

      ③ 어떤 형식으로 주고 받을 건지 약속을 정한 것 -> 그래야 서로 데이터를 알 수 있음

      ④ 예를 들어 야구에서 모자를 만지면 번트, 코는 안타 -> 서로간의 약속으로 소통

   (2) 따라서, 프로토콜은 약속이다

   (3) HTTP : Hyper Text Transfer Protocol

      ① HTTP는 하이퍼 텍스트를 전달하는데 사용되는 약속이다

      ② 텍스트 기반으로 되어있음. 예를 들어, [ GET /hello HTTP1.1 ... ] 처럼 주고받을 데이터가 텍스트로 되어있어서 단순하고 사람이 읽기 쉬움

      ③ 상태를 저장하지 않음. 클라이언트 정보를 저장하지 않음 -> 이를 보완하기 위해 쿠키 & 세션을 사용

      ④ 확장이 가능함. 헤더에 사용자가 직접 만든 헤더를 추가할 수 있음

   (4) HTTP는 편지와 비슷함(Header와 내용으로 구성되어 있음)

   (5) HTTP는 클라이언트와 서버 간 요청 편지와 응답 편지를 주고받는 것과 비슷하다

   (6) 동작 순서

      ① 클라이언트가 브라우저에 URL을 입력

      ② 브라우저는 요청 메시지를 HTTP에 맞춰서 만든 후에 서버에 전송

      ③ 서버는 응답 메시지를 HTTP에 맞춰서 다시 클라이언트에 전송

      ④ 클라이언트는 응답 메시지를 분석해서 내용을 브라우저에 보여줌

   (7) 응답 메시지의 구성

      ① 상태코드 : 1xx, 2xx, ... 5xx

      ② 헤더

      ③ 바디

      -> 이렇게 구성되어 있는 것이 HTTP 규약에 맞는 '응답 메시지'. 이렇게 작성되어있어야 클라이언트가 이해할 수 있음

   (8) 요청 메시지의 구성

      ① 요청라인 : GET, POST 

      ② 헤더

      ③ 바디

   (9) GET은 버서에 리소스를 얻어오는 용. 그래서 바디가 없음. 그렇지만 쿼리스트링으로 데이터 전송 가능

   (10) POST는 서버에 리소스를 보내는 용. 바디에 리소스를 담음(ex. 게시글 등록, 로그인, 회원가입)

2. 텍스트와 바이너리 MIME, Base64

   (1) 텍스트 기반 프로토콜에서 바이너리 데이터(ex. 이미지, 파일)을 전송하려면 어떻게 할까?

   (2) HTTP의 Content-Type 헤더를 사용 -> Content-Type은 바디 데이터의 타입을 명시하는 헤더임

   (3) Post 방식의 form-data를 이용하면 body에 바이너리 데이터를 보낼 수 있음

   (4) 이 바이너리 데이터는 Base64(64진법)으로 나타내서 보내짐. 64비트를 사용하는 이유는 모든 OS에서 기본적으로 사용하는 문자를 사용해서 디코딩을 가능하게끔 하기 위해

3. 관심사의 분리와 MVC 패턴

   (1) 관심사의 분리 : 기존 코드는 ① 입력, ② 처리, ③ 출력 으로 나누어져 있음(3개의 관심사로 나누어져 있음)

   (2) 입력의 분리 -> 입력을 처리하는 부분을 앞으로 분리

   (3) 처리와 출력의 분리 -> 계산하는 부분과 출력하는 부분을 분리. 그런데 처리한 데이터를 출력부분과 연결지어야 하므로 이 때 사용하는 것이 Model 객체임

   (4) C(데이터 처리) -> M(모델) -> V(뷰, 출력) -> 이 모양이 MVC패턴임

4. MVC 패턴의 원리

   (1) DispatcherServlet은 Reflection을 이용해서 사용할 클래스(Controller)의 메서드를 알아내고 그 매개변수에 필요한 값을 넣어줌

   (2) 어떻게 Controller가 view이름만 전달해도 뷰를 반환해줄까?

   (3) DispatcherServlet은 해시맵인 model을 만들고 반환 받은 view에 model을 같이 전달한다

5. 서블릿과 JSP

   (1) jsp와 서블릿은 거의 비슷. 그리고 이를 발전시킨 것이 Spring

   (2) Servlet은 Java코드 안에 HTML

   (3) JSP는 HTML코드 안에 Java

   (4) JSP는 서블릿으로 변경되어서 서블릿으로 등록된다

1. 문제
   - 직접 Servlet을 만들어서 등록하면 DispatcherServlet은 거치지 않겠네?

2. 시도
   - 직접 해보자

3. 해결
   - 그렇다. 직접 Servlet을 등록할 경우 DispatcherServlet은 거치지 않는다

4. 알게된 점
   - Servlet을 직접 등록하면, DispatcherServlet과 함께 Servlet은 두 대가 된다
   - DispatcherServlet도 하나의 Servlet에 불과하다. Servlet 다음인 Controller에서 비즈니스 로직에 집중할 수 있도록 도와주는 Servlet일 뿐임

코테 준비

1. 백준 2812 - 크게 만들기

: stack 자료구조를 이용해서 푸는 문제이다. 사실 stack 문제라는 걸 알고 풀어서 쉽게 풀었지만, 만약 몰랐다면 어땠을까. 자료구조를 이용한 문제를 많이 풀어보면서 감을 익혀야 할 것 같다

2. 백준 3425 - 고스택

: 새로운 stack을 만드는 아주 빡빡한 구현문제였다

하루하루 꾸준히!!!