[C++] Process와 thread
2022. 10. 5. 23:34
Development/C++
오늘은 thread에 대해 알아보도록 하겠다. 스레드(thread)란 ? 프로세스 내에서 실제로 작업을 수행하는 주체를 의미한다. 모든 프로세스에는 한 개 이상의 스레드가 존재하고, 작업을 수행한다. 일반적으로 한 프로그램은 하나의 스레드를 가지고 있지만, 프로그램 환경에 따라 두개 이상의 스레드를 가지는 프로세스를 멀티스레드 프로세스라고 한다. 프로세스(Process) 란? 간단하게 말하면 실행 중인 프로그램이라고 할 수 있다. 즉, 사용자가 작성한 프로그램이 운영체제에 의해 메모리 공간을 할당받아 실행 중인 것을 말한다. 프로세스는 프로그램에 사용되는 데이터와 메모리 등의 자원 그리고 스레드로 구성된다. 프로세스와 스레드의 차이 우선 가장 큰 차이점으로 메모리 공유여부에 대한 부분이 다르다. 프로세스..
[백준 11779번] - 최소비용 구하기 2(C/C++)
2022. 10. 5. 00:49
Problem Solving/백준
11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [문제 설명] [문제 풀이] 다익스트라 알고리즘 관련 문제이다. 만약, 다익스트라 알고리즘에 대해 잘 모른다면, 아래 포스트를 먼저 보고오는것이 좋다. [Algorithm] - Dijkstra(다익스트라) 알고리즘 이론 Dijkstra(다익스트라) 알고리즘이란, 그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘(최단경로 문제)이다. 처음 작성된 알고리즘은 시간복잡도 O(N^2)을 가지는데, mocha-bro.t..
멀티프로세싱, 멀티쓰레딩, 멀티플렉싱
2022. 10. 3. 23:35
Development/Network
운영체제 및 프로그래밍을 공부하다보면 자주 사용되는 멀티프로세싱, 멀티쓰레딩, 멀티플렉싱과 같은 단어와 각각의 장단점들에 대해 잘 정리되어있는 내용들을 모아봤다. 멀티플렉싱이란? 여러명이서 통신할때 하나의 채널만 가지고 통신하는 방식을 말한다. 멀티쓰레드, 멀티 프로세스가 여러 채널을 만들어 통신한다면 멀티플렉싱은 하나의 프로세스, 스레드를 가지고 여러 명의 통신을 연결시킨다. 여러명이 접속할 수 있는 서버를 만들기 위해 여러 IO모델들이 사용된다. 오늘은 대표적인 멀티플렉싱 방식의 IO 모델인 select에 대해 살펴보고자 한다. 1. select 동작 과정 서버는 여러 클라이언트의 접속을 받는다. 그 후 각 클라이언트의 이벤트(데이터 수신여부, 데이터 송신가능 여부, 오류 수신 여부 등)의 이벤트가 ..
[Algorithm] - Dijkstra(다익스트라) 알고리즘
2022. 10. 2. 04:52
Problem Solving/Algorithm
이론 Dijkstra(다익스트라) 알고리즘이란, 그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘(최단경로 문제)이다. 처음 작성된 알고리즘은 시간복잡도 O(N^2)을 가지는데, 이후 우선순위큐(=힙트리)를 이용한 개선 알고리즘이 나오면서 O(NlogN)으로 개선되었다. 다익스트라의 특징은 음의 가중치가 없다는 점이다. 따라서 현실세계에 적용할 수 있는 효율적인 알고리즘이라고 할 수 있다. 그래프의 방향은 상관없으나, 가중치가 하나라도 음수라면 다익스트라 알고리즘을 사용할 수 없다. 이때는 조건에따라 벨만-포드 알고리즘을 사용하여 최단거리를 구할 수 있다. 또한, 다익스트라 알고리즘은 하나의 노드로부터 최단 경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍..
[프로그래머스] - 배달(C/C++)
2022. 10. 2. 02:47
Problem Solving/프로그래머스
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다..
[Algorithm] - Kruskal's Algorithm(최소 스패닝 트리)
2022. 9. 13. 23:46
Problem Solving/Algorithm
이론 크러스컬 알고리즘은 Union-Find 알고리즘을 사용하기때문에 만약 Union-Find에 대해 잘 모른다면 [Algorithm] - Union-Find(Disjoint-set) 이론 여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다. 간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다 mocha-bro.tistory.com 위 포스트를 한번 읽고 오면 이해하는데 수월 할 수 있다. 크러스컬 알고리즘? 크루스칼 알고리즘?을 정리해보려고 한다. 위 알고리즘의 이론은 최소 비용으로 신장 부분 트리(Spanning SubTree)를 찾는 알고리즘이다. 아래 나무위키에 크러스컬 알고리즘의 단계 별 예제가 있어서 가져왔다. 간단하고 ..
[Algorithm] - Union-Find(Disjoint-set)
2022. 9. 13. 23:24
Problem Solving/Algorithm
이론 여러개의 집합이 존재 할때, 두개의 집합을 선택해서 같은 그래프에 속하는지 판단하는 알고리즘이다. 간단하게 이야기 하자면, 교집합이 있다면 한개의 집합으로 보게 하겠다는 의미이다. 예를들어, A,B 집합이 다음과 같이 있다고 했을때 A = {1,2} , B = {2,3} 2라는 교집합이 있으므로 {1,2,3} 한개의 집합으로 보겠다는 것이다. 이때 집합을 병합하는 부분이 Union, 집합에 속해있는지 확인하는부분이 Find로 볼 수 있다. 두개가 함께 사용되어 Union-Find라는 이름이 붙었다. Disjoint-Set이라고도 불린다. 이름만 다르고, 동일한 알고리즘으로 볼 수 있다. 구현 다음과 같이 노드들의 간선이 주어졌다고 예를들어 설명하겠다. {1,2}, {2,3}, {3,4}, {1,5}..
[프로그래머스] - 섬 연결하기(C/C++)
2022. 9. 13. 10:32
Problem Solving/프로그래머스
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입..
[Windows Socket] - Client
2022. 9. 8. 13:55
Development/Network
이번엔 Winsock을 사용하여 Clinet를 간단하게 만들어 볼 생각이다. 지난번 작성한 Server 코드에 비하면 굉장히 간단하다. Client 프로그램을 만드는 순서는 아래와 같다. Winsock을 초기화합니다. 소켓을 만듭니다. 서버에 연결합니다. 데이터를 보내고 받습니다. 연결 끊기를 선택합니다. Server를 만드는 부분에서 bind, listen, accept과 같은 부분들이 빠져있다. Client 소켓을 생성하고 연결 할 IP,Port등을 통해 연결을 시도하면 된다. 1,2,4,5번은 이 전 포스트와 동일하므로 생략하도록 하겠다. 서버에 연결합니다. 우선 연결할 Socket 하나를 생성한다. 접속 요청할 소켓의 정보(address family, IP, Port)를 SOCKADDR_IN 구조..
[Windows Socket] - Server
2022. 9. 8. 13:14
Development/Network
오늘은 지난 포스트에 이어서 Winsock을 사용하여 간단한 server를 만들어보려고 한다. 지난 포스트에서 서버는 아래와 같은 절차가 있다고 언급했다. Winsock을 초기화합니다. 소켓을 만듭니다. 소켓을 바인딩합니다. 클라이언트에 대한 소켓에서 수신 대기합니다. 클라이언트에서 연결을 수락합니다. 데이터를 수신하고 보냅니다. 연결 끊기를 선택합니다. 위와 같은 순서로 한번 만들어 보려고 한다. Winsock을 초기화합니다. 우선 헤더 파일 및 lib 파일과 연결한다. Winsock 초기화에 대한 부분은 저번 포스트에서 다뤘으니 넘어가도록 하겠다. #include #include #include #pragma comment(lib, "ws2_32.lib") int main() { WSADATA wsa..
[Windows Socket] - 시작하기
2022. 9. 8. 11:08
Development/Network
Windows Socket Programming Windows 환경에서 소켓프로그래밍을 공부해보려고 한다. 네트워크 소켓(network socket)은 컴퓨터 네트워크를 경유하는 프로세스 간 통신의 종착점이다. 오늘날 컴퓨터 간 통신의 대부분은 인터넷 프로토콜을 기반으로 하고 있으므로, 대부분의 네트워크 소켓은 인터넷 소켓이다. 네트워크 통신을 위한 프로그램들은 소켓을 생성하고, 이 소켓을 통해서 서로 데이터를 교환한다. 아래와 같은 요소들로 구성되어있다. 인터넷 프로토콜 (TCP, UDP, raw IP) 로컬 IP 주소 로컬 포트 원격 IP 주소 원격 포트 리눅스에서의 소켓 프로그래밍과 거의 동일하다. 하지만 몇가지 더 해줘야 하는것들이 있고, 함수명이 좀 다른 것들이 있다. 우선, 서버와 클라이언트를..
[백준 12865번] - 평범한 배낭(C/C++)
2022. 9. 3. 23:38
Problem Solving/백준
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [문제 설명] [문제 풀이] 다이나믹 프로그래밍 문제 중 유명한 유형인 Knapsack Problem(배낭 문제)이다. 물건들은 각각 무게(W)와 가치(V)를 가지고 있다. 배낭에 넣을수 있는 무게의 한계(K)가 정해져있고, 무게 한도 안에서 넣을수있는 물건들(N)의 가치합의 최댓값을 구하면 된다. 물건들을 처음부터 차례로 확인한다. 2차원 배열 dp를 선언하여 dp[물건 인덱스][무게]의 가치의 ..