✏️ 2022-11-11 Today I Learn

[알고리즘] 그래프

노드간의 연결관계 및 방향성에 초점이 맞춰져있는 자료구조

1-1. 방향성을 이용해 그래프를 표현하는 법

유방향 그래프 : 노드의 종착점에 화살표를 이용해 다음 노드를 향하도록 함.
무방향 그래프 : 노드간 연결에 화살표가 그려져 있지 않은 그래프

1-2. 그래프를 표현하는 방법

인접행렬 : 2차원 배열을 이용하여, x -> y 를 (x,y) 번째 배열에 체크를 하는식으로 표현한다.
인접리스트 : 각 노드의 인접노드를 배열에 담아 딕셔너리에 저장하는 방식
두 방식의 차이점
- 공간 vs 시간
- 인접행렬은 2차원배열이기 때문에 접근이 $O(N^2)$ 의 속도를 보장한다. 하지만, 배열을 사용하기 때문에 상대적으로 적은 공간을 사용한다.
- 인접리스트는 딕셔너리를 이용하기 때문에 많은 공간을 사용한다. 접근이 $O(1)$ 의 속도를 보장한다.

1-3. DFS

깊게 파고들어가 노드를 살펴보는 방식이다. 자식을 파고들어가야하기 때문에 스택을 이용하여 구현하는것이 용이하다.

1-4. BFS

횡으로 모든노드들을 찬찬히 살펴보는 방식이다. 큐를 이용하여 구현한다.

[알고리즘] DP

겹치는 부분문제(Overlapping Subproblem) : 공통의 규칙을 찾아 문제를 쪼갠다.
메모이제이션(Memoization) : 결과를 기록하여 다시 사용한다.

[CS] CPU 전반전 개론

3-1. CPU의 발전

CPU는 싱글코어에서 멀티코어로 발전해오고 있다. 무어의 법칙에 의하면, 매년 2배씩 프로세스의 성능은 발전하고 있는데 왜 갯수를 늘리는 방식을 선택할까. 성능의 향상은 발열과 직접적인 관계가 있다. 발열을 잡는데는 한계가 있기 때문에, 횡으로 갯수를 늘려 성능을 보장하는 방법을 택하고 있다.

3-2. CPU의 구성

CPU는 여러개의 코어로 구성되어 있고, 그 코어는 여러개의 레지스터로 구성되어있다. 1개의 레지스터는 1개의 상태를 의미한다.

CU(Control Unit) 프로그램이 보낸 연산요청을 특정레지스터에 저장해놓았다가, 가져온 뒤(fetch) 해석(decode)하여, 연산이 필요한 것들을 ALU에게 전달한다.
ALU(산술논리연산자) 산술논리연산을 통해 반환한 결과를 프로그램에 전달한다. 이후, 프로그램 메모리의 상태가 변경된다.
캐시 디스크와의 연산에 대한 핑퐁시간을 줄이기 위해, 빈도가 잦은 연산을 저장하여 핑퐁시간을 줄임.
캐시 일관성에 대해 조사해보기

3-3. 레지스터의 구성과 기능

구성
- 범용(general purpose)
- 특수용(special purpose)
- PC(Program Counter) register : 명령어를 순차적으로 실행할 수 있도록 돕는 레지스터

3-4. CPU와 프로그래머는 어떻게 통신할까?

CPU는 바이너리만 알아들을 수 있다.
이것을 개선하기 위해 어셈블리어가 개발되었다.
하지만, 이것또한 허들이 있어 High Level 언어인 C, C++, Java와 같은 언어가 생겼다.
각 언어는 컴파일러/인터프리터를 통해 언어를 바이너리 파일로 변환한다.
변환한 파일은 cpu로 전달하여 적절한 연산을 하여 결과를 반환한다.

3-5. ISA(Instruction Set Architecture)

기계어 명령어들의 집합.

CISC와 RISC 가 있으며, 최근엔 명령어 체계가 간단한 RISC가 자주 쓰이고 있다.
RISC 를 사용하게 되면 한 사이클 내에서 명령어 수행이 가능하다.

[회고] 221111

알고리즘 파트에 진입하게 되면서, 수강생들의 격차가 많이 나고 있다. 듣는강의의 진행도에 따라 순위를 표기해주는데, 한 파트 차이로 등수가 중간에서 상위권으로 뛰어 올라갔다.
그만큼, 많은 분들이 기본알고리즘에서 고급알고리즘으로 넘어오는데 허들을 겪고 있다는 소리이다. 그러면서, 질문방이 매우 활성화되고 있고, 아는 한에서는 적극적으로 도움을 드리고자 노력하고 있다. 하지만 가끔 속상할 때가 있다. 이미 내가 해결했다고 생각한 이슈에 댓글이 달리는 순간이 그런 순간이다. 그럴때마다 '내 답변이 충분히 문제를 해결한 것 같은데', '내가 더 잘 답변한 것 같은데' 라는 쓸데없는 생각이 들면서, 자존심이 상한다.

나는 어느순간부터 감정이 올라오면 감정을 뱉기보단, 그 감정의 원인이 무엇인지 곰곰하게 생각하는 버릇을 들이고있다. 생각해보니, 이 이슈는 내가 남들보다 답변을 쉽게 잘했다, 혹은 남들보다 더 잘 설명했다는 '자만심'에서 오는 자존심에서 발생된 이슈라고 판단했다.

다시 생각했다. '내가 이렇게 자존심을 부릴이유가 있나..? 내가 개발자로 근무를 했지만, 모자른 점이 많다고 느껴서 여기온거고, 난 내가 이정도 안다라고 뽐내러 온게 아니라 배우러 온 것이다. 답변경쟁을 하려 온게 아니라, 답변을 하는 과정을 통해 배우고, 커뮤니케이션 하는 과정을 통해 소프트스킬을 배우러 온 것 이다. 또, 여기는 개발경력이 없더라도 나보다 뛰어나신 분들이 충분히 많다. 내가 더 겸손한 자세로 배워야겠다.' 라는 생각을 했다.

가끔 나는 '경력'의 늪에 빠지곤한다. 내가 과거에 근무하던 체육계는 경력이 곧 능력이었다. 학교도 학년이 곧 능력이었고, 군대도 짬이 곧 능력이었다. 이렇게 경력이 곧 능력이 되는 업계에서 근무하다, 실력이 곧 능력이 되는 업계에 들어오니, 적응이 안된다. 입에 붙은 '내가 해봤는데~', '라떼는~' 이라는 단어는 말하면서도 스스로 수치스럽다. 2년차 개발자 ~ 라는 타이틀은 현재 내가 내세울만한 타이틀은 아닌 것 같다. 2년차에 걸맞는 능력이 없기에 배우러왔고, 다시 차근차근 능력을 쌓으러 왔다. 겸손하고 인정하자. 하지만, 내가 확실히 아는것에 대해서는 말할 수 있는 자신감은 유지하자. 단, 그것을 '경력'의 프레임을 가지고 얘기하진 말자.

[다짐]

경력직 이라는 마인드를 의식적으로 없애고 겸손하기.
'나는 배우러 온 것이다'라는 생각을 되새기기.
개발자로서의 소양을 쌓기.