CS
-
[컴퓨터 구조] 컴퓨터 핵심부품들(CPU, 메모리 등)의 역할과 작동원리CS 2023. 6. 13. 20:42
개요 JVM 동작원리 등을 더 수월하게 이해하고 컴퓨터의 근간에 대해 공부하며 문제 해결 능력을 키우기 등을 위해 컴퓨터 구조를 공부한다. 컴퓨터는 데이터와 명령어를 이해하고 처리해준다. 아래는 컴퓨터 구조 중 핵심부품들을 그림으로 나타낸 것이다. 부품별 설명 메인보드 부품들을 연결시켜준다. 시스템버스 핵심 부품들(CPU, 메모리, 입출력장치, 보조기억장치 등)이 서로 정보를 주고 받을 수 있게 해준다(통로역할). cf. 다양한 종류의 버스가 있으며, 시스템버스는 컴퓨터 핵심 부품을 연결하는 버스다. 메모리(RAM) 정보를 기억하는 역할로써 0과 1을 기억하는 장치다. ※ 보조기억장치 보다 비싸고 전원이 꺼지면 저장된 내용을 잃는다(휘발성 저장장치). ※ 초기 RAM은 작게 기억하지만 빠른 속도를 가졌다..
-
[알고리즘 + Python] 최단 경로 알고리즘 - 다익스트라(dijkstra), 플로이드 워셜(Floyd-Warshall)CS/알고리즘 2023. 2. 5. 22:07
해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘"을 보고 학습용으로 기록한 것입니다. 최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. cf. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현한다. 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 1. 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다..
-
[알고리즘 + Python] DP(Dymanic Programming, 다이나믹 프로그래밍)CS/알고리즘 2023. 2. 2. 21:27
해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍"을 보고 학습용으로 기록한 것입니다. DP 사용조건 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있다. 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결한다. DP 예시 대표적인 문제로는 피보나치 수열이 있다. (cf. 점화식: 인접항들의 관계식을 의미한다.) // 피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ... * 피보나치 수열의 점화식 재귀함수를 통해서 점화식을 소스코드로 구현할 수 있다. 프로그래밍에서는 이러한 수열..
-
[알고리즘 + Python] DFS(Depth-First Search, 깊이우선탐색) & BFS(Breadth-First Search, 너비우선탐색)CS/알고리즘 2023. 2. 2. 21:27
해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 3. DFS & BFS"를 보고 학습용으로 기록한 것입니다. Stack과 Queue 자료구조 1) Stack 파이썬에서 스택은 리스트 자료구조를 사용하면 된다. cf) stack[::-1] : 최상단 원소부터 출력 stack = [] stack.append(5) # 삽입 stack.append(2) stack.append(3) stack.append(7) stack.pop() # 제거 stack.append(1) stack.append(4) stack.pop() # 최상단 원소부터 출력 print(stack[::-1]) # [1, 3, 2, 5] # 최하단 원소부터 출력 print(stack) # [5, 2, 3, 1] 2) Queue 리..
-
[자료구조] 5. 해시(Hash) - HashMapCS/자료구조 2022. 10. 3. 22:33
해시 특징 1. 해시 테이블(Hash Table) Key(키)와 Value(데이터)가 매핑되는 데이터 구조이다. Key(with 해시함수)를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있다. 따라서 배열 또는 연결 리스트(Linked List)와 비교했을 때, 저장 및 탐색 속도가 획기적으로 빨라진다. ※ cf) 연결 리스트(Linked List)는 head부터 찾아나가야한다. 미리 해시 함수가 생성할 수 있는 주소에 대한 공간(Slot)을 할당한 후 Key에 따른 데이터 저장 및 탐색을 지원한다. Slot(슬롯): 해시 테이블에서 한 개의 데이터를 저장할 수 있는 공간을 뜻한다. 이미지 출처: https://www.javatpoint.com/hash-table 2. 해시 함수(Hash Functi..
-
[자료구조] 2-2 리스트(List) - Linked List, Doubly Linked ListCS/자료구조 2022. 10. 1. 19:00
자료구조도 Linked List 특징(feat. 장단점) 이미지 출처: https://code-lab1.tistory.com/2 Linked List는 연결 리스트라고도 한다. 1-1. 장점 - 미리 데이터 공간을 할당하지 않아도 된다. 따라서 데이터가 필요할 때 저장공간을 만들기 때문에 낭비적인 요소가 별로 없다고 볼수도 있다. cf) 배열은 미리 할당해야함. 1-2. 단점 - 하지만 연결을 위한 별도 데이터 공간, 즉 다음 데이터 주소를 넣는 공간(포인터)이 필요하다는 측면에서 바라보면, 저장공간의 효율성이 좋다고 볼 수는 없다. ※ cf) 데이터와 포인터를 합쳐서 노드라고 한다. 이미지 출처: https://wakestand.tistory.com/106 - 또한 위 이미지에서 볼 수 있듯, 배열과 ..
-
[자료구조] 4. 스택(Stack)CS/자료구조 2022. 9. 11. 16:07
Stack의 특징 LIFO(Last In First Out) 구조로 나중에 들어온 데이터가 먼저 나가는 구조를 갖는다(ex) 접시쌓기). push()와 pop()을 통해서 데이터를 넣고 꺼낸다. Stack은 일반적으로 미리 데이터 최대 개수를 정해야한다. 따라서 저장 공간의 낭비가 발생할 수 있다. => Stack의 size를 가변적으로 가져가도록 구현하여 해결할 수도 있다. Stack 선언과 메소드 - Stack strStack = new Stack(); - push(obj) - String.join("구분자", iterable obj) - pop() Stack 선언과 값 추가, 크기 확인, 값 확인, 값 출력(각각 push(), size(), toString(), String.join()) impor..
-
[자료구조] 3-1. 큐(Queue)CS/자료구조 2022. 9. 10. 16:33
자료구조도 이 글에서는 Queue에 대해서만 알아보고, 우선순위 큐(Priority Queue)는 다음에 알아보도록 하자. Queue의 특징 FIFO(First In First Out) 구조로 먼저 들어온 데이터가 먼저 나가는 구조를 갖는다(ex) 줄서기). 이는 스택(Stack)의 FILO(First In Last Out)와 반대되는 구조이다. Enqueue는 큐에 데이터를 넣는 기능을 뜻하고, Dequeue는 데이터를 꺼내는 기능을 뜻한다. Queue 선언과 메소드 Queue 클래스를 쓰기 위해선 LinkedList 클래스도 같이 사용해야한다. LinkedList는 다음에 알아보도록 하자. - Queue strQueue = new LinkedList(); - add(obj) / offer(obj) -..