[Data Structure] Hash Table(2) - Implementation
2024. 4. 29. 16:10
CS/Data Structure
Swift에서 HashTable을 활용한 자료구조에는 Set과 Dictionary가 존재한다.이 중 Key-Value 쌍으로 데이터를 저장하는 Dictionary를 구현해 보자. 해당 포스팅에선 Dictionary를 Chaing방법과 Open Addressing 2가지 방법으로 모두 구현해 볼 것이다.여기서는 구현에 관해서만 다룰 것이기 때문에, 해시 테이블 이론에 관련한 것들은 이전 포스팅을 참고 바란다.https://seokyoungg.tistory.com/92 [Data Structure] Hash Table(1) - Concept만약 다음과 같은 데이터가 있다고 가정해 보자. 이들을 저장하기 위해선, 품목을 키값으로 매핑해 개수를 저장해야 한다. 즉, 품목이 인덱스화 될 필요가 있다. 이처럼 k..
[Data Structure] Hash Table(1) - Concept
2024. 4. 20. 17:12
CS/Data Structure
만약 다음과 같은 데이터가 있다고 가정해 보자. 이들을 저장하기 위해선, 품목을 키값으로 매핑해 개수를 저장해야 한다. 즉, 품목이 인덱스화 될 필요가 있다. 이처럼 key-value를 매핑하는 것이 "해시 테이블(Hash Table) ADT"이다. 해시 테이블 ADT를 자료구조로 구현하기 위해선, key 값을 정수값으로 매핑할 필요가 있다. 이러한 Key값을 해시 테이블의 인덱스로 매핑하는 것이 "해시 함수"(Hash Function)이다. 이때, 해시 함수의 결과값을 해시, 해시 값, 해시 코드라 부른다. 즉, 해시 테이블(Hash Table) ADT를 자료구조로 구현하기 위해 필요한 것이 해시 함수이다. 해시 함수의 결과값인 해시(해시 값, 해시 코드)는 해시테이블의 인덱스가 된다. 이렇게 인덱스를..
[Data Structure] Priority Queue
2024. 4. 15. 14:42
CS/Data Structure
"우선순위 큐"(Priority Queue)는 다음과 같은 2개의 Main Operation을 명세하는 ADT이다.enqueue(push): 원소를 추가한다.dequeue(pop): 우선순위가 높은 원소를 제거한다. 지난 포스팅에서 다루었던 "큐"(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO의 형태라면, "우선순위 큐"(Priority Queue)는 먼저 들어온 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 ADT이다. 흔히들 "우선순위 큐는 Heap이다"라고 생각하는데, 이는 잘못된 오류이다. 우선순위 큐는 ADT일뿐 위에 말한 2개의 Operation만 제공하면 된다. 즉, 스택이 배열, 연결리스트 등으로 다양한 방법으로 구현할 수 있는 것처럼 우선순위 큐도 다양한 방법으로 구현..
[Data Structure] Queue
2024. 4. 13. 16:06
CS/Data Structure
"큐"(Queue)는 선형 자료구조로 2가지 Main Operation을 기본적으로 제공하는 ADT이다. enqueue(push) : 원소를 추가한다. dequeue(pop) : 가장 처음에 추가된 원소를 제거한다. 지난 포스팅에서 다루었던 스택은 프링글스 통과 같이 LIFO로 동작했다. 반면, 큐는 티켓팅을 위해 줄을 서는 것과 같이 가장 먼저 들어간 원소가 가장 먼저 제거되며, 이를 FIFO라 부른다. 큐 역시 위의 사진과 같이 원소의 삽입과 삭제되는 위치가 정해지기 때문에, Restricted Structure라고도 불린다. 이렇게 원소가 삽입되는 곳을 tail, rear, back이라 부르며, 원소가 삭제되는 곳을 head, front라 부른다. 사용 Computer Science에서 큐는 굉장히..
[Data Structure] Stack
2024. 4. 9. 14:28
CS/Data Structure
"스택"(Stack)은 말 그대로 "무언가를 쌓아 올린 것"을 의미한다.대표적으로 프링글스 통이 있다. 프링글스 통 안에는 과자가 쌓여있고, 최근에 들어간 과자가 가장 먼저 나오는 구조이다. 이러한 구조를 "스택"이다 부른다. "스택"은 선형 자료구조로 다음과 같은 2가지 Main Operation을 제공하는 ADT이다. push : 원소를 추가한다.pop : 가장 최근에 추가된 원소를 제거한다. ADT는 자료와 자료들의 연산에 대한 명세이다. 이를 구현한 것이 자료구조가 되며, 스택과 같이 대부분 ADT와 자료구조는 동일한 이름을 갖는다. 앞선, 프링글스 통을 다시 살펴보자! 프링글스 통은 입구 및 출구가 한개이기에, 가장 최근에 넣은 과자가 먼저 나올 수 있다. 즉, 스택도 다음과 같은 구조이기에..
[PS] BOJ 1019(책 페이지) - C++
2024. 4. 6. 21:05
CS/Algorithm
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 10의 자릿수가 변할 때마다, 1의 자리 0~9까지가 반복된다. 또한, 100의 자릿수가 변할 때마다, 0~99의 숫자가 반복된다. 즉, 각 자릿수마다 특정 패턴들이 반복된다. 각 자릿수 별로 등장하는 패턴들을 예시를 통해 살펴보자. N이 32698723이라고 가정하고, $10^6$의 자릿수에서의 숫자들의 등장 횟수를 살펴보자. 경우의 수는 다음과 같이 나누어진다. N의 $10^6$자릿수보다 작은 경우 N의 $10^6$자릿수보다 큰 경우 N의 $10^6$자릿수와 ..
[Data Structure] Array & Linked List(2) - Implementation
2024. 4. 5. 16:28
CS/Data Structure
이번 포스팅에선 List ADT 중 Linked List를 Swift를 통해 구현해 보자. 개념에 관해 보고 싶다면 이전 포스팅을 참고 바란다. 전체적인 구현은 여기에서 확인 할 수 있다. https://github.com/jungseokyoung-cloud/Data-Structure GitHub - jungseokyoung-cloud/Data-Structure: Data Structures implemented with Swift Data Structures implemented with Swift. Contribute to jungseokyoung-cloud/Data-Structure development by creating an account on GitHub. github.com Simple L..
[Data Structure] Array & Linked List(1) - Concept
2024. 3. 30. 16:57
CS/Data Structure
이번 포스팅에선 선형 자료구조의 배열과 연결 리스트에 대해서 알아보자. List(Sequence) ADT List 혹은 Sequence는 추상 자료형(Abstract Data Type)으로 Data의 중복을 허용하는 순서가 있는 Data의 모임이다. 추상 자료형은 기능만을 명세해 놓은 것이다. 이를 구현한 것이 자료구조가 된다. 이러한 List ADT는 다음과 같은 기능을 명세한다. 처음, 끝, 혹은 중간에 데이터를 추가 / 삭제하는 기능 데이터가 있는지를 체크하는 기능 모든 데이터에 접근할 수 있는 기능 이때 데이터를 쌍으로 저장하면 동적배열(Dynamic Array)이 각 데이터들을 포인터를 통해 연결하면 연결리스트가 된다. 배열 (Array) "배열"(Array)은 쌍으로 구성되며 메모리 상에서 연..
[Data Structure] 자료구조란?
2024. 3. 13. 17:51
CS/Data Structure
"자료구조"(Data Structure)란 데이터에 효율적인 접근을 위한 데이터의 구조, 관리, 저장을 말한다. 정확히 말하면 "자료구조"는 데이터의 모임으로, "데이터 간의 관계"와 "적용할 함수나 명령"을 의미한다. 예를 들어 자료구조 중 Queue를 생각해 보면, 데이터의 저장 및 삭제까지를 정의한다. 프로그래밍에서 적절한 자료구조는 효율적인 알고리즘을 수행할 수 있게 해준다. Queue 자료구조를 사용하면, BFS 알고리즘은 효율적으로 수행할 수 있다. 자료구조의 분류 자료구조는 크게 2가지로 분류된다. 원시 자료구조 (Primitive Data Structure) 복합 자료구조 (Non-Primitive Data Structure) 원시 자료구조 (Pritimitive Data Structure..
[Computer Network] Network Layer(3) - Unicast Routing
2024. 3. 2. 17:08
CS/Computer Network
"Network Layer"의 주된 서비스 중 하나는 Routing이며, "Routing"은 Source부터 Destination까지 최소 비용인 경로를 결정하는 작업을 의미한다. 이러한 Routing은 1:1 통신일 경우에는 "Unicast Routing" 1:N 통신일 경우에는 "Multicast Routing"으로 구분된다. 이번 포스팅에서는 Unicast Routing에 대해 알아보자. Hop-By-Hop Routing 다음과 같은 네트워크가 있다고 가정해 보자. 해당 네트워크에서 A부터 B까지 최소 비용 경로는 라우터 "u-x-y-z"를 거친다. 만약 Router가 경로상에 있는 모든 Router정보를 안다고 가정해 보자. 해당 예시에선 "u-x-y-z"로 짧지만, 인터넷 상에서 Router의 ..
[Computer Network] Network Layer(2) - IP Address
2024. 2. 12. 14:26
CS/Computer Network
하나의 LAN 내에서는 각 디바이스만 구별하면 되기에 Data Link계층의 MAC주소를 사용했다. 하지만, LAN간의 통신에서 이 MAC주소는 사용할 수 없다. MAC주소는 디바이스마다 고유하기에, 모든 LAN내의 디바이스의 MAC주소를 알아야 하는 문제점이 생기기 때문이다. 따라서,LAN 간의 연결을 Internet계층인 IP 프로토콜이 담당하게 되며, 이를 위해 사용되는 식별자가 IP 주소이다. 이러한 IP주소는 32bit 체계를 사용하며, 이를 IPv4라 부른다. IP Address Notation 일반적으로 IP주소를 표기하는 데 있어서는 크게 2가지 notation을 사용한다. Dotted Decimal Notaion Hexadecimal Notation IP Address Hierarchy ..
[Computer Network] Network Layer(1)
2024. 2. 4. 20:56
CS/Computer Network
지난 포스팅에서 Network의 기초적인 개념과 TCP/IP 프로토콜 계층에 대해서 살펴보았다. 오늘은 이 중 IP protocol을 중점적으로 Network Layer에 대해 알아보자. "Internet Layer"는 데이터를 신뢰성보다는 성능 중심(Best-Effort)으로 목적지까지 전달한다. 이러한 Internet Layer는 크게 2가지의 서비스를 제공한다. 패킷화 포워딩 & 라우팅 Packet Circuit Switching vs. Packet Switching 우선 Network에서 데이터를 보내는 방식에는 크게 2가지가 있다. Circuit Swithcing Packet Switching Circuit Switching "Circuit Switching"이란, Connection-Orie..