포스트

2021-01-12-TIL

TIL
게시 수정 작성자 August
좋아요 조회 9 분 읽는 시간
  1. docs(posts): separate the sections of every post with a thematic break +6 −0
  2. docs(posts): write every reference entry as title, then publisher +3 −3
  3. docs(til): turn the bookmark-only tils into notes (part 1) +55 −30
  4. 처음 게시

알고리즘과 자료구조 수업

알고리즘은 사용하는 일이 거의 없다. 하지만 자료구조는 매우 빈번하게 사용된다.

알고리즘의 정의

알고리즘의 조건 : 입력, 출력, 유한성

The Art of Computer Programming

  1. 유한성(Finiteness)
  2. 명확성(Definiteness)
  3. 입력(Input)
  4. 출력(Output)

Knuth가 『The Art of Computer Programming』에서 제시한 알고리즘의 성질은 위 네 가지에 유효성(Effectiveness)을 더한 다섯 가지다. 유한성은 알고리즘이 유한한 단계 뒤에 반드시 끝나야 한다는 뜻이고, 명확성은 각 단계가 모호하지 않게 정의되어야 한다는 뜻이다. 유효성은 각 연산이 사람이 종이와 연필로 유한한 시간 안에 정확히 해낼 수 있을 만큼 기본적이어야 한다는 조건이다.

성능은 상한선으로 본다

성능은 상한선이 하한선 보다 중요하다 -> 빅 오 표기법을 주로 사용한다.

웹스케일의 시대에 많은 데이터를 다루기 위해서는 시간복잡도의 상한선을 고려한 설계가 매우 중요해졌다.

O(n), O(nlogn) 정도를 빠른 알고리즘으로 생각한다

페이스북 좋아요는 어떤식으로 구현되었나? O(N)이면 감당할 수 없을것

인자 전달 방식

call by reference (class) call by address (pointer) call by value (struct)

Java는 call-by-value만 지원한다. 객체를 인자로 넘기면 객체의 주소를 복사한 값이 전달된다. 그래서 메서드 안에서 매개변수에 다른 객체를 대입해도 호출한 쪽의 변수는 바뀌지 않지만, 복사된 주소로 객체에 접근해 필드를 바꾸면 그 변경은 호출한 쪽에서도 보인다.

수업 중 메모

MDN, 스펙문서

JDK 까보기

java jdk linked list

웨어 레벨링 ssd

플래시 메모리는 블록마다 지울 수 있는 횟수가 정해져 있다. 웨어 레벨링은 쓰기를 여러 블록에 고르게 나눠 특정 블록이 먼저 수명을 다하지 않게 하는 기법이다.

큐 구현체중에 링크드리스트가 가장 깔끔

더미노드를 이용해서 서큘라 큐를 편하게 구현 - 매트릭스 센티널

idx가 cnt보다 크다면 에러를 내거나 예외처리

Bash Shell 리턴값

셸 스크립트에는 일반 언어의 return 반환값이 없고, exit로 종료 상태만 돌려줄 수 있다. 보통 0은 성공, 1부터 255는 에러다. 직전 명령의 종료 코드는 $?에 담긴다. 값을 돌려받고 싶으면 함수 안에서 echo로 출력하고 호출하는 쪽에서 $(함수명)으로 서브셸 결과를 받는다.

알고리즘 공부자료

edwith의 알고리즘 입문 강좌를 공부 자료로 기록해 두었다.

ADT

ADT(Abstract Data Type)를 정리한 글을 찾아 두었지만 지금은 열리지 않는다.

LinkedList

Singly Linked List

리스트를 배열로 구현하면 논리적인 순서를 지키기 위해 삽입과 삭제 때마다 원소를 옮겨야 한다. 그래서 삽입과 삭제가 잦으면 포인터로 원소를 잇는 연결 리스트를 쓴다. 단순 연결 리스트는 각 노드가 다음 노드로 가는 링크만 가진다.

Circular Linked List

원형 연결 리스트를 정리한 글을 찾아 두었지만 지금은 열리지 않는다. 위의 더미 노드를 이용한 원형 큐 메모와 이어지는 주제다.

Doubly Linked List

이중 연결 리스트는 단순 연결 리스트의 노드에 이전 노드를 가리키는 부분을 추가한 구조다. 생활코딩 강의는 Java로 직접 구현하는 과정을 다룬다.

HashMap

Java HashMap은 어떻게 동작하는가?

HashMap Javadoc에 따르면 해시 함수가 원소를 버킷에 고르게 흩어 놓는다는 가정에서 get과 put은 상수 시간에 동작한다. 원소 수가 load factor와 현재 용량(버킷 수)의 곱을 넘으면 해시 테이블을 다시 해시해 버킷 수를 약 두 배로 늘린다.

HashMap에서 custom key 정의하기

직접 만든 클래스를 HashMap의 키로 쓰려면 Object의 equals()와 hashCode()를 재정의해야 한다. 같은 값으로 만든 두 객체는 같은 hashCode()를 돌려줘야 하고, 그러면서도 가능한 한 서로 다른 값이 나오도록 만드는 것이 좋다.

HashMap에서 forEach()문 사용하기

Java 8부터 Map.forEach(BiConsumer)로 모든 엔트리에 대해 키와 값을 받는 동작을 실행할 수 있다.

순서가 보장된 HashMap : LinkedHashMap

LinkedHashMap은 HashMap과 달리 모든 엔트리를 잇는 이중 연결 리스트를 유지한다. 이 리스트가 순회 순서를 정하고, 보통은 키가 삽입된 순서다.

IntelliJ 에서 자바 클래스로 부터 interface 뽑아내기

IntelliJ의 Extract Interface 리팩터링 기능을 쓰면 기존 클래스의 메서드와 상수를 골라 인터페이스로 뽑아낼 수 있다.

자바 인터페이스

인터페이스는 객체의 교환성을 높여 다형성을 구현하는 데 중요한 역할을 한다. 인터페이스에 선언된 추상 메서드는 모두 public abstract이고, 구현 클래스는 같은 이름, 매개 타입, 리턴 타입을 가진 실체 메서드를 가져야 한다.

그 밖의 메모

  • 이메일로 일하는 법
참고한 자료외부 출처 17

외부 출처

TIL, 2021-TIL
TIL
이 글은 저작권자의 CC BY 4.0 라이선스를 따릅니다.

댓글

아직 댓글이 없습니다