howudong의 등록된 링크

키자드에 등록된 총 428개의 포스트를 확인하실 수 있습니다.

Tistory

[운영체제] 동기화를 위한 모니터(Monitor) 개념 요약 정리

모니터를 사용하는 이유 세마포 또는 mutex 락을 이용하여 임계구역 문제를 해결할 때 문제점 → 프로그래머가 세마포를 잘못 사용할 시, 다양한 유형의 오류가 쉽게 발생할 수 있음 이러한 오류 처리를 위해 모니터 사용 전략 : 간단한 동기화 도구를 통합하여 고급 언어 구조물로 제공하는 것 → 모니터 모니터는 근본적인 고급 언어 구조물 중 하나 Java, C# 등의 많은 프로그래밍 언어들이 모니터의 개념을 편입시킴 모니터 사용법(Usage) ADT와 모니터 ADT(추상화된 데이터 형) : 데이터와 해당 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호 이때 함수의 구현은 ADT의 특정한 구현과는 독립적 모니터 형 : 모니터 내부에 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT 이때 모니..

원문보기 내부링크
Tistory

[운영체제] Mutex Lock과 스핀락(Spin lock), 세마포어(Semaphore)

Mutex Locks 만들어진 이유? 임계구역 문제에 대한 하드웨어 기반 해결책은 복잡하고, 응용프로그래머가 사용 불가능 → 임계구역 문제 해결을 간단하게 하기 위해 만들어진 소프트웨어 도구를 개발 Mutex Locks : 상위 수준 소프트웨어 도구 중 하나로, 가장 간단한 도구 임계 구역 보호를 통해 경쟁 조건 방지를 위해 mutex 락 사용 임계 구역에 들어갈 때 락을 획득하고, 빠져나올 때 락을 반환해야 한다. acquire() : 락 획득 release() : 락 반환 Mutex Lock의 구성 available이라는 boolean 변수를 가짐 → 이 변수 값이 락의 가용 여부를 표시 락이 사용 가능하면 acquire() 호출은 성공하고, 락은 사용 불가 상태가 됨 사용 불가 상태의 락을 획득하려..

원문보기 내부링크
Tistory

[C++ / Java] 프로그래머스 Level 2 - 단체사진 찍기

https://school.programmers.co.kr/learn/courses/30/lessons/1835?language=cpp [A, C, F, J, M, N, R, T] 8개의 알파벳을 나열하는 것을 베이스로 한다. 입력으로 있는 data의 모든 조건에 부합하여 나열할 수 있는 경우의 수가 총 몇 가지가 나오는지 구하는 문제 문제 핵심 및 풀이 해당 문제 풀이의 핵심은 조건의 개수 n이 최대 100개까지라는 점. 그리고 8개의 알파벳을 나열할 때 나올 수 있는 모든 경우의 수는 8! = 40320밖에 되지 않는다는 점이다. 그래서 일단 나올 수 있는 경우의 수는 백트래킹을 구하는 것이 적절하다. 그렇게 줄을 다 세우면, 그다음부터 data에 따라 필터링을 해주면 된다. 필터링 방법은 간단하다...

원문보기 내부링크
Tistory

[C++ / C# ] 프로그래머스 Level3 - 억억단을 외우자 ( 2가지 풀이)

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/138475 1억 x 1억 크기의 행렬이 존재하고, 그 정수 s~e 사이 범위에서 가장 많이 나오는 정수가 뭔지를 알아내는 문제 문제 핵심 및 풀이 제한 사항을 보면 1억 x 1억짜리 행렬은 아니더라도, 최댓값 e가 5,000,000까지 가능하기 때문에 O(n^2) 연산만 해도 바로 시간초과 그리고 O(N) 짜리 연산을 하더라도 모든 starts 값에 대해서 답을 구해준다면, starts의 최대 길이는 100,000이니까 10^5 * 10^6 이어서 역시 시간초과다. 결국 모든 starts의 범위에 대한 값을 미리 구해놓을 수밖에 없다. 즉, 메모라이징 기법을 이용하는 DP 문제라고 대놓고 ..

원문보기 내부링크
Tistory

[C#] SortedSet으로 우선순위 큐 쉽게 구현하기 ( + 다익스트라)

왜 필요할까? C#에서 우선순위큐(Prirority_Queue)는 .NET 7에 새로 생겼다. 이게 문제가 되는 이유는 대표적인 알고리즘 풀이 사이트(백준, 프로그래머스)가 .NET 7 하위 버전이다. 즉, C#으로 알고리즘을 풀 때 우선순위 큐를 사용할 수 없다는 소리다. SortedSet SortedSet에 대해 자세히 다루는 포스팅은 아니기 때문에 우선순위 큐 구현에 필요한 핵심만 말하겠다. SortedSet은 내부의 요소가 자동적으로 정렬된다. 이때 중복 요소는 허용되지 않는다. 원시타입(string,int) 같은 경우, 정렬 기준을 만들지 않으면 자동으로 오름차순으로 정렬되지만 컬렉션,배열 등은 무조건 IComparable 혹은 IComparer를 통해 정렬 기준을 만들어야한다. SortedSe..

원문보기 내부링크
Tistory

[C++ / C# ] 프로그래머스 Level 3 - 등산코스 정하기

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118669? 여러 출입구, 쉼터, 산봉우리로 왕복하는 코스 중에서 ntensity가 최소인 것을 찾는 문제. 문제 핵심 및 풀이 왕복? 같은 출입구에서 시작하여 산봉우리를 찍고 다시 돌아오는 것이다. 그리고 갔던 길을 다시 가도 된다. 그래서 말이 출입구 - 산봉우리의 왕복이지, 사실상 편도로 계산해도 된다. 왜냐하면 최소의 intensity를 찾았다면, 그 경로 그대로 다시 내려오면 되니까.. 예를 들어, 출입구가 1이고, 4번이 산봉우리라고 하자. 1번 출입구에서 4번 산봉우리까지 도착하는데 줄일 수 있는 intensity가 3이라고 하면 어떤 경로 (1 - a - b - 4) 이런 식..

원문보기 내부링크
Tistory

[C++ / C# ] 프로그래머스 Level 3 - 숫자 타자 대회

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/136797 입력으로 눌러야 하는 숫자가 순서대로 주어지고, 왼손과 오른손 엄지를 가지고 숫자를 눌러야 한다. 각 숫자를 누를 때마다 가중치라는 비용이 드는데 이는 위치에 숫자의 위치에 따라 달라진다. 조건은 아래와 같다. - 이동하지 않고 제자리에서 다시 누르는 것 → 가중치 1 - 상하좌우 인접한 숫자로 이동 → 가중치 1 - 대각선으로 인접한 숫자로 이동 → 가중치 1 - 같지 않고 인접하지 않은 숫자를 누를 때 → 위 규칙을 따라 가중치 합이 최소가 되는 경로 처음에 왼손은 4번, 오른손은 6번에서 시작한다. 이때, 나올 수 있는 가중치의 최소합을 구하는 문제 입력으로는 숫자만 ..

원문보기 내부링크
Tistory

[C++ / C# ] 프로그래머스 Level 3 - 풍선 터트리기

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/68646 일렬로 N개의 풍선이 나열되어 있다. 모든 풍선에는 서로 다른 숫자가 써져 있다. 인접한 풍선 2개를 선택해서 둘 중 하나를 터트리는 행동을 풍선이 최종적으로 1개 남을 때까지 반복한다. 이때, 풍선 2개 중 터트릴 풍선을 선택할 때, 두 풍선 중 번호가 더 작은 것을 터트리는 행동은 최대 1번밖에 할 수 없다. 즉, 횟수 제한이 없는 것은 두 풍선 중 번호가 더 큰 풍선을 터트리는 행동이다. 위의 상황에서 풍선의 번호가 주어질 때, 각 풍선이 최후까지 남을 수 있는지를 확인한다. 그리고 최후까지 남을 수 있는 풍선의 개수를 구한다. 문제 접근 단계 제한 사항에서 얻을 수 있..

원문보기 내부링크
Tistory

[C++ / C#] 프로그래머스 Level 3 - 양과 늑대

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/92343? 이진트리가 있는데, 각 노드에는 양(0) 또는 늑대(1)가 있다. 무조건 루트노드에서 출발하여 양을 획득해야 한다. 루트 노드는 항상 양이다. 획득하는 과정에서 양의 수가 항상 늑대 수보다 많음을 유지해야 한다. 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아올 때 모을 수 있는 최대 양의 수를 구하는 문제 문제 접근 단계 제한 사항 파악 제한 사항부터 보면 노드(info)는 최대 17개까지이다. 이에 따라, 항상 이진트리를 유지하기 때문에 간선(edges) 또한 100개가 넘어가지 않는다. 즉, 완전 탐색이 가능할 만큼 탐색할 범위가 작음을 알 수가 있다. 움직이는 ..

원문보기 내부링크
Tistory

'하노이의 탑' 알고리즘, 그림으로 쉽게 이해하기(with 재귀)

하노이의 탑(Tower of Hanoi) 문제란? 유례나 역사 같은 것은 다 생략하고, 문제의 조건 같은 본론부터 바로 말하겠다. 3개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기에 원판들이 존재한다. 맨 처음 시작할 때, 원판의 크기가 큰 것부터 1번 기둥에 모두 쌓는다. 맨 왼쪽 기둥부터 순서대로 1번, 2번, 3번 기둥이라고 한다. 문제에서 요구하는 것은 아래의 조건을 만족하면서, 1번 기둥에 쌓여있는 모든 원판들을 3번 기둥으로 옮기는 것이다. 조건 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. N개의 원판이 최소 경로로 이동할 때의 경로를 출력하라는 것이 문제에서 요구하는 것이다. 이 문제를 왜 알아야 할까? 중요한 것은 학습의 목적이다. 프로..

원문보기 내부링크
Tistory

[C++ / C#] 프로그래머스 Level 3 - 가장 긴 팰린드롬

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/12904? 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 뜻한다. 입력으로 문자열 s가 주어질 때, s의 부분 문자열 중에 가장 긴 팰린드롬의 길이를 구하는 문제 문제 접근 단계 제한사항부터 살펴보자. 문자열의 길이 s는 2,500 이하의 자연수이고, 알파벳 소문자로만 구성되어 있다. 팰린드롬이라는 좌우대칭 규칙성을 판단할 때는 보통 스택을 사용하는데, 각 자리마다 스택을 사용하여 넣었다 뺐..

원문보기 내부링크
Tistory

[C++] 백준 9252 - LCS 2

문제 이해 단계 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS는 두 수열이 주어졌을 때, 두 수열의 공통이 되는 부분 수열 중 가장 긴 것을 찾는 문제이다. 가장 긴 수열의 길이를 출력하고, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지일 경우엔 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄은 출력하지 않는다. 문제 접근 단계 LCS 길이 구하기 [C++] 백준 9251 ..

원문보기 내부링크
Tistory

[C++] 백준 15961 - 회전초밥

문제 이해 단계 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 회전 초밥의 개수 N, 회전 초밥의 종류 d, 연속해서 먹을 수 있는 개수 k, 쿠폰 번호 c가 들어온다. 여기서 회전 초밥은 원형으로 시계 방향으로 돌아가는데, 종류가 d개만큼 있다는 것을 의미한다. 시계 방향으로 돌아가는 회전 초밥을 연속해서 k개 먹을 때, 최대한 많은 종류를 먹는 것이 목표이다. 이때, 먹은 k개의 종류 중 쿠폰 ..

원문보기 내부링크
Tistory

[C++] 백준 7579 - 앱

문제 이해 단계 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net N개의 앱이 존재한다. N개의 앱에는 2가지 정보가 들어있는데, (사용 중인 메모리의 바이트 수, 비활성화했을 때의 비용) 2가지이다. M 바이트를 확보해야 하기 때문에, N개의 앱 중 몇 가지를 골라서 비활성화해야 한다. 이때 비활성화 했을 때의 비용을 최소화하여 M 바이트를 확보해야 한다. 최소 비용일 때를 출력하는 문제 문제 접근 단계 제한 사항 분석 앱의 개수(N)는 최대 100개..

원문보기 내부링크
Tistory

[C++] 백준 13460 - 구슬 탈출 2

문제 이해 단계 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net NxM 크기의 맵이 존재하고, 빨간 구슬과 파란 구슬이 존재한다. 맵의 테두리는 모두 벽으로 막혀있고, 하나의 구멍이 존재한다. 목표는 파란 구슬은 구멍은 남겨둔 채 빨간 구슬을 구멍을 통해 빼내는 것. 할 수 있는 동작은 상하좌우로 기울이는 것이다. 기울인다는 것은 해당 쪽에 벽에 닿을 때까지 쭉 흐른다는 것. 예를 들어, 오른쪽..

원문보기 내부링크
Tistory

[C/C++] 이진탐색 - lower_bound, upper_bound 구현

구현해 보는 이유 C++ 헤더 에 lower_bound와 upper_bound 함수가 있다. 근데 있는 거 두고 굳이 왜 직접 구현해 보는 걸까? 이유는 총 2가지이다. 1. 학습적인 목적(이진탐색 구현) 2. 이진 탐색 변형 이 목적으로 한번 구현해 본다. lower_bound와 upper_bound 메서드 lower_bound lower_bound는 찾고자 하는 값보다 크거나 같은 값이 처음 나타난 곳의 인덱스를 반환한다. 예를 들어서, {2,4,6,7,9}에서 lower_bound를 사용하여 2를 찾는다면 배열에서 2의 인덱스인 0을 반환한다. 또한 5를 찾는다면, 처음으로 5보다 큰 6의 인덱스인 2를 반환한다. upper_bound upper_bound는 찾고자 하는 값보다 큰 값이 처음 나타난..

원문보기 내부링크
Tistory

[C++] 백준 12015 - 가장 긴 증가하는 부분 수열 2

문제 이해 단계 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20 30,50}이고, 길이는 4이다. 문제 접근 단계 특이점 알아내기 가장 긴 ~ 부분 수열 시리즈 문제 항상 비슷하면서 풀이가 다른 게 해당 시리즈 특징이다. 일단 수열..

원문보기 내부링크
Tistory

[운영체제] 프로세스 동기화를 위한 하드웨어 지원

임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어를 제시 메모리 장벽(Memory Barriers) 메모리 모델 컴퓨터 아키텍처가 응용프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식 일반적으로 두 가지 범주 중 하나에 속함 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음 메모리 모델은 프로세서 유형에 따라 다름 → 커널 개발자는 공유 메모리 다중 처리기에서 메모리 변경의 가시성에 대한 가정 불가 → 이러한 문제를 해결하기 위해 메모리 장벽을 사용 메모리 장벽 : 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어 이를 통해 다른 프로세서에서..

원문보기 내부링크
Tistory

[운영체제] 프로세스 임계구역(Critical Section)문제와 고전적 해결안

동기화 도구들이 왜 필요할까? 협력적 프로세스가 데이터를 공유하는 방법 협력적 프로세스 : 시스템 내에 실행 중인 다른 프로세스에게 영향을 주거나 받는 프로세스 논리 주소 공간(코드, 데이터)을 직접 공유, 공유 메모리, 메시지 전달 → 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있음 데이터의 일관성을 유지하기 위해 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장 프로세스가 병행 또는 병렬로 실행될 때 공유하는 데이터의 무결성에 문제를 일으킴 문제가 발생하는 예시 static int count = 0; // 전역 변수 // 스레드 t1은 count를 1씩 더함 Task t1 = new Task(() => { for (int i = 0; i < 10000; i++) cou..

원문보기 내부링크
Tistory

[C++] 백준 12100 - 2048(Easy) 큐를 이용한 풀이

문제 이해 단계 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048이라는 게임이 존재한다. 이 게임 상하좌우 이동 중 하나를 고르는데, 한번 이동할 때 모든 블록이 해당 방향으로 벽이나 다른 블록에 부딪힐 때까지 움직인다. 이때 같은 값을 가지는 두 블록이 충돌하면 두 블록은 하나로 합쳐지면서 값도 하나로 합쳐진다. 한 번 이동할 때 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다. 이러한 게임에서, Nx..

원문보기 내부링크
Tistory

[C++] 백준 9328 - 열쇠

문제 이해 단계 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 높이 h와 너비 w를 가진 2차원 맵이 존재한다. 여기서 원하는 것은 문서를 최대한 많이 획득하는 것이다. '. ' : 빈 공간 ' * ' : 벽 ' $ ' : 문서 알파벳 대문자 : 잠겨 있는 문 알파벳 소문자 : 열쇠 해당 문자의 대문자에 해당하는 문을 열 수 있음 처음에는 빌딩 밖에 있고, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 그리고 같은 열쇠를 여러 번 사..

원문보기 내부링크
Tistory

[C++] 백준 10942 - 팰린드롬?

문제 이해 단계 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬은 좌우가 대칭되는 숫자로 이루어진 수열을 뜻한다. 예를 들어 (1,2,3,2,1), (1,3,1) (3) 등이 해당된다. N개의 수열이 주어지고, 총 M개의 (S, E) 쌍이 들어온다. 이는 S번호부터 E번호까지로 이루어진 수열이 팰린드롬인지를 판단하는 것이다. 팰린드롬이면 1, 그렇지 않으면 0을 출력한다. 문제 접근 단계 일단 제한사항부터 살펴보자. 수열의 크기 N은 최대 2,000까지이다. 정수는 최대 1..

원문보기 내부링크
Tistory

[C++] 백준 11049 - 행렬 곱셈 순서

문제 이해 단계 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 행렬 N개를 곱하는데 곱하는 순서에 따라 값이 달라진다. 행렬 N의 크기가 주어졌을 때 곱셈 연산 횟수의 최솟값을 구하는 문제 곱셈 연산을 하는 방법은 크기가 NxM인 행렬 A와 MxK인 행렬 B가 있을 때 AxB = N x M x K를 크기로 계산한 후 행렬은 N x K가 된다. 입력은 무조건 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다. 문제 접근 단계 제..

원문보기 내부링크
Tistory

[C++] 백준 17387 - 선분 교차 2

문제 이해 단계 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2차원 좌표 평면 위의 2개의 선분 L1과 L2가 주어진다. 두 선분이 교차하는지 아닌지를 판단하는 문제. 교차하면 1, 그렇지 않으면 0을 출력한다. 입력으로 L1의 양 끝 좌표(x1, y1) (x2, y2) L2의 양 끝 좌표 (x3, y3) (x4, y4)가 들어온다. 문제 접근 단계 문제 조건에서 시간제한이 0.25초로 상당히 짧은 것을 볼 수 있다. 그리고 두 좌표를 연결하는 선분 L1, L2이기 때문에 일차함수라는 것을 알 수 있..

원문보기 내부링크
Tistory

[C++] 백준 2252 - 줄 세우기

문제 이해 단계 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 접근 단계 1번부터 ~N번까지 N명의 학생들을 키 순서대로 줄을 세운다. 입력을 키를 비교한 두 학생의 번호 A, B가 M개 들어온다. 이는 A학생 뒤에 B학생이 서야 한다는 의미이다. 학생들을 앞에서부터 줄을 세운 결과를 출력하는데, 답이 여러 가지인 경우에는 아무거나 하나 골라서 출력한다. 문제 구현 단계 일단 제한사항부터 살펴보..

원문보기 내부링크
Tistory

[C++] 백준 2473 - 세 용액

문제 이해 단계 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 정수로 되어있는 용액이 N개가 주어진다. 이 중에서 3개를 골라 3개의 합이 0에 가장 가까운 경우를 만들 때, 그때의 세 용액을 찾아서 오름차순으로 출력하는 것이 문제이다. 문제 접근 단계 문제는 상당히 간단한데, 일단 수의 범위랑 제한사항부터 살펴보자. 산성 용액과 알칼리 용액으로 구분해 놨지만, 사실상 용액의 범위는 -1,000,000,000 ~ 1,00..

원문보기 내부링크
Tistory

[C#] 소켓(Socket) 서버(Server) & 클라이언트(Client) 통신 간단한 구현

서버 DNS 및 Socket 연결 string host = Dns.GetHostName(); IPHostEntry ipHost = Dns.GetHostEntry(host); IPAddress address = ipHost.AddressList[0]; IPEndPoint ipEndPoint = new IPEndPoint(address, 7777); // 최종주소 Socket socket = new Socket(ipEndPoint.AddressFamily, SocketType.Stream, ProtocolType.Tcp); socket.Connect(ipEndPoint); // 해당 ip주소로 연결 요청 Console.WriteLine($"Connect To {socket.RemoteEndPoint.ToSt..

원문보기 내부링크
Tistory

[C++] 백준 1005 - ACM Craft

문제 이해 단계 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net N개의 건물이 있고, 각 건물마다 먼저 지어져야 하는 건설 순서가 K개 존재한다. 목표로 지어야 할 건물이 있을 때, 해당 건물을 짓는데 걸리는 최소 시간을 알아내는 문제 문제 접근 단계 일단 제한사항부터 살펴보자. 테스트 케이스 T의 개수는 명시되어있지 않다. 그리고 건물의 개수 N은 최대 1,000개 건설 순서 K의 개수와 최대 시간 소요시간은 100,000까지이다. 여기..

원문보기 내부링크
Tistory

[C++] 백준 2096 - 내려가기

문제 이해 단계 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net N x 3 짜리 맵이 존재한다. 각 칸에는 0 ~ 9 숫자가 적혀있다. 가장 윗 칸에서 한 칸씩 내려오는데, 내려올 수 있는 방향은 바로 아래 또는 대각 방향밖에 없다. 가장 위에서 아래로 이동할 때 얻을 수 있는 최대 점수와 최수를 구하는 문제 문제 접근 단계 예제 입력을 통해 한번 유형을 찾아보려고 해 보자. 만약 내가 마지막 층(N)행의 2번째 칸인 9를 선택했다고 해보자. 이 입력에서 해..

원문보기 내부링크
Tistory

[C++] 백준 11779 - 최소비용 구하기 2

문제 이해 단계 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net n개의 도시와 m개의 버스가 존재한다. 버스는 A도시에서 출발하여 B도시에 도착하는 정보로 주어진다. 그리고 각 버스마다 드는 비용이 존재한다. 또한 입력으로 출발지와 도착지가 주어질 때, 출발지에서 도착지까지 가는데 드는 최소 비용과 경로를 출력하는 것 문제 접근 단계 일단 문제 조건부터 살펴보자. 도시의 개수 n은 최대 1,000 간선의 개수(버..

원문보기 내부링크
Tistory

[C++] 백준 2448 - 별 찍기 11

문제 이해 단계 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net N = 24 일 때의 출력이다. 예제를 보고 규칙을 유추하고 별을 찍는 문제 입력 N은 무조건 3 * 2^k로 들어온다. 여기서 k의 범위는 0≤k≤10이다. 문제 접근 단계 별 찍기 시리즈 문제이다. 때문에 구현문제인 것 같은데, 어떤 식으로 구현해야 할까? k의 범위가 0부터 10까지니까 순서대로 해봤다. 이 이상은 그림이 너무 커질 것 같아서 k = 2 일 때까지만 그려보도록 하겠다. 이렇게 k가 1씩 커져갈 때의 규칙을 보면 ..

원문보기 내부링크
Tistory

[운영체제] CPU 스케줄링 알고리즘 평가 방법 정리

알고리즘의 평가 특정 시스템을 위한 CPU 스케줄링 알고리즘은 어떻게 선택하는가? 알고리즘을 선택하는 데 사용할 기준을 정의 알고리즘을 선택하기 위해 매개변수들의 상대적인 중요성을 반드시 정의해야 한다. 기준은 종종 CPU 이용률, 응답시간 또는 처리량에 의해 정의된다. 기준은 아래와 같은 대책을 포함할 수도 있음 최대 응답 시간은 300ms라는 제약 조건에서 CPU 이용률을 극대화한다. 총 처리 시간이 전체 실행 시간에 평균적으로 선형 비례가 되도록 처리량을 극대화한다. 선택 기준의 정의되면, 여러 가지 알고리즘들을 평가하기를 원한다. → 아래에서 사용할 수 있는 여러 평가 방법들을 기술 결정론적 모델링 분석적 평가(analytic evaluation) 평가 방법의 중요한 부류 중 하나 주어진 작업 부..

원문보기 내부링크
Tistory

[운영체제] 실시간 CPU 스케줄링 개념 및 방식

실시간 CPU 스케줄링 실시간 CPU 스케줄링은 연성(soft) 실시간 시스템과 경성(hard) 실시간으로 구분 연성 실시간 시스템 중요한 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다. 오직 중요 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진다는 것만 보장 경성 실시간 시스템 태스크는 반드시 마감시간까지 서비스를 받아야 한다. → 더 엄격한 요구 조건을 만족해야 함 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 받지 않는 것과 같다. 지연시간 최소화(Minimizing Latency) 실시간 시스템의 이벤트-중심 특성 시스템은 일반적으로 실시간으로 발생하는 이벤트를 기다린다. 이벤트가 발생하면 시스템은 가능한 한 빨리 그에 응답하고 그에 맞는 동작을 수행해야 한다...

원문보기 내부링크
Tistory

[운영체제] 다중 처리기에서의 CPU 스케줄링

다중 처리기 스케줄링 여러 개의 CPU가 사용 가능 → 여러 스레드가 병렬로 실행 가능 → 부하 공유(load sharing) 가능 스케줄링 문제는 그에 상응하여 더욱 복잡해짐 다중 처리기란? 여러 개의 물리적 프로세서를 제공하는 시스템 각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있음 최신 컴퓨팅 시스템에서의 다중 처리기는 아래의 아키텍처들을 사용 가능 다중 코어 CPU 다중 스레드 코어 NUMA 시스템 이기종 다중 처리 다중 처리기 스케줄링에 대한 접근 방법 다중 처리기 시스템의 CPU 스케줄링에 관한 해결 방법 비대칭 다중 처리(asymmetric multiprocessing) 마스터 서버라는 하나의 처리기가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급 다른 처리기들은 사용..

원문보기 내부링크
Tistory

[C++] 백준 13172 - ∑

문제 이해 단계 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 문제가 거의 비문학 지문이다. 여기서 문제 풀이에 필요한 정보만 뽑아보자. 1. 각 주사위에서 얻을 수 있는 기댓값은 a * b^(-1) modX를 계산해야 한다. 여기서 a는 모든 면에 적힌 숫자의 합이고, b는 주사위 면에 개수이다. 2.b^(-1)는 b의 모듈러 곱셈에 대한 역원인데, 구하는 방법은 b^(X-2) = b^(-1) modX이다. 3. 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 얻기 위해서는 각 ..

원문보기 내부링크
Tistory

[C++] 백준 12851 - 숨바꼭질 2

문제 이해 단계 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net X좌표로만 이루어진 맵이 존재한다. 출발점 N과 도착점 K가 입력으로 들어온다. 출발점 N에서 할 수 있는 움직임은 총 3개이다. 1. X+1 2. X-1 3. X*2 3개의 움직임을 적절히 조합해서 도착점 K까지 갈 수 있는 가장 빠른 시간을 구하고, 가장 빠른 시간으로 갈 수 있는 경우의 수를 출력하는 문제 문제 접근 단계 숨바꼭질 시리즈 ..

원문보기 내부링크
Tistory

[C++] 백준 11054 - 가장 긴 바이토닉 부분 수열

문제 이해 단계 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 수열이란 어떤 수를 A라고 했을 때, a < b < c < A > d > e > f.. 이런 식으로 이루어져야 한다. 수열 A가 입력으로 들어올 때 그 수열의 부분이 바이토닉 수열이면서, 가장 긴 수열의 길이를 구하여 그 길이를 출력해라. 문제 접근 단계 가장 긴 ~~ 수열 시리즈 문제이다. 일단 제한사항부터 살펴보면, 수열의 길이는 최대 1000까지이다. 만약 시간복잡도가 O(n^2)까지 ..

원문보기 내부링크
Tistory

[C++] 백준 9935 - 문자열 폭발

문제 이해 단계 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 첫 번째 줄에 문장이 주어지고, 두 번째 줄에 폭발 문자열이라는 특정 키워드가 주어진다. 문장에서 폭발 키워드가 있으면 그 부분을 지운다. 그리고 문장을 이어 붙인다. 문장을 이어 붙였을 때 또 키워드가 완성된다면 그 부분을 지운다. 이런 식으로 모든 폭발키워드를 지운 후, 남은 문장을 출력한다. 문제 접근 단계 제한사항부터 보자. 문장의 길이는 최대 1,000,00..

원문보기 내부링크
Tistory

[네트워크/Network] 무선 랜과 SSID의 구조 정리

무선 랜의 구조 무선 랜이란? 무선 랜은 케이블을 사용하지 않고 전파를 이용하여 무선으로 컴퓨터를 연결 단점 유선보다 속도가 불안정하고 전파가 약하면 연결이 잘 안 됨 유선랜에 비해 통신 내용이 해킹될 위험이 높다 → 암호화나 인증 설정이 필요 무선 랜 구성 무선 액세스 포인트(WAP)와 무선 클라이언트(컴퓨터나 스마트폰)로 구성 무선 공유기에 무선 액세스 포인트 기능이 포함 컴퓨터가 무선 액세스 포인터와 통신하기 위해선 무선 랜 칩과 무선 랩 어댑터가 필요 최근에 나온 컴퓨터는 대부분 무선 랜 칩을 내장하고 있다. 무선 랜 어댑터 USB 메모리 방식 어댑터 컴퓨터 카드 방식 어댑터 인프라스트럭처 방식과 애드혹 방식이란? 인프라스트럭처(infrastructure) 방식 무선 액세스 포인터를 통해 통신하는..

원문보기 내부링크
Tistory

[C++] 백준 1504 - 특정한 최단 경로

문제 이해 단계 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 입력으로 정점의 개수 N과 간선의 개수 E가 주어진다. 여기서 간선은 양방향 그래프이다. 정점 1에서 정점 N까지 최단경로로 움직여야 하는데, 무조건 타깃으로 설정한 정점 A와 정점 B를 방문해야 한다. 여기서는 한번 이동했던 간선도 다시 이동하는 것을 허락한다. 이러한 조건일 때 두 정점을 반드시 거치면서 최단 경로로 이동할 때의 값을..

원문보기 내부링크
Tistory

[C++] 백준 11444 - 피보나치 수 6 (행렬 풀이 X)

문제 이해 단계 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수열이 존재한다. n이 입력으로 들어올 때, n번째 수열의 값을 구하는 것이 문제. 문제 접근 단계 이 문제가 골드 2인 데는 제한사항 때문이다. 입력으로 들어올 수 있는 n이 10^18까지 가능하다. 엄청나게 크다. int 자료형으로는 절대 받을 수 없고 가장 큰 자료형인 long long int를 써야지만 받을 수 있다. 기존에 풀던 DP방식으로 문제를 풀면 시간 복잡도가 O(n)이 나온다. 이는 결국 1초가 넘어 시간초과가 나오기 때문에 다른 ..

원문보기 내부링크
Tistory

[운영체제] CPU 스케줄링 알고리즘과 스레드 스케줄링

스케줄링 알고리즘 CPU 스케줄링은 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU 코어를 할당할 것인지를 결정 여러 가지 다른 CPU 스케줄링 알고리즘이 존재 여기서의 스케줄링 알고리즘은 처리 코어가 하나뿐이라고 가정하고 설명 → 즉 한 번의 하나의 프로세스만 실행할 수 있다는 뜻 선입 선처리 스케줄링(FCFS) 방식 : CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 가장 간단한 CPU 스케줄링 알고리즘 코드 작성과 이해가 쉽다. 선입 선처리 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리 가능 프로세스가 준비 큐에 진입하면, 이 프로세스의 프로세스 제어블록(PCB)을 큐의 끝에 연결 CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당 해당 프로세스(실행 상태의 프..

원문보기 내부링크
Tistory

[C++] 백준 1022 - 소용돌이 예쁘게 출력하기

문제 이해 단계 https://www.acmicpc.net/problem/1022 반시계 방향으로 돌아가는 소용돌이를 구현해야 한다. 특이한 점은 음수 좌표까지 존재하고 이미 그림 상의 좌표는 지정해 놨고 위치도 이미 정해져 있다는 것이다. 우리가 해야 할 것은, 가장 왼쪽 위 칸(r1, c1)과 가장 오른쪽 아래 칸(r2, c2) 사이에 있는 사각형 영역을 출력하는 것이다. 출력을 할 때는 왼쪽에 공백을 넣어 오른쪽에 공백을 넣어 출력해야 한다 문제 접근 단계 해당 문제에서 고려해야 할 점이 많다. 반시계로 도는 소용돌이 구현 이러나저러나 결국에는 반시계로 도는 소용돌이를 구현해야 해당 문제를 풀 수 있다. 위에서 정해준 (0,0) 좌표에서 시작하여 반시계방향으로 도는 소용돌이를 만드는 방법을 생각해 ..

원문보기 내부링크
Tistory

[C++] 백준 1629 - 곱셈

문제 이해 단계 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 입력으로 A, B, C가 들어온다. 자연수 A를 B번 곱하고, C로 나눈 나머지를 출력해라. 문제 접근 단계 상당히 간단한 문제로 보인다. 하지만 그렇지 않다. 여기에는 2가지의 문제점이 존재한다. 첫 번째는, 수의 범위이다. 제한사항을 보면 입력이 2,147,483,647까지다. 입력부터 20억이 넘어가기 때문에 20억^20억 long long int 자료형을 아득히 넘어간다. 그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다. 자료형을 넘..

원문보기 내부링크
Tistory

[C++] 백준 2263 - 트리의 순회

문제 이해 단계 https://www.acmicpc.net/problem/2263 이진트리의 정점이 1~n까지의 번호가 중복 없이 매겨져 있다. 이진트리의 중위 순회와 후위 순회가 입력으로 주어질 때, 전위 순회를 출력하는 문제 문제 접근 단계 이 문제를 풀기 위해서는 기초적으로 이진트리의 개념과 전위, 중위, 후위 순회의 개념과 특성을 미리 알고 있어야 한다. 전위 순회 : 루트 → 왼쪽 → 오른쪽 중위 순회 : 왼쪽 → 루트 → 오른쪽 후위 순회 : 왼쪽 → 오른쪽 → 루트 그림을 보면서 하는 것이 가장 빠르다. 해당 그래프로 중위 순회와 후위 순회를 돌려보면, 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 이 된다. 우리는 ..

원문보기 내부링크
Tistory

[네트워크/Network] 응용계층 역할 및 정리(HTTP,DNS,메일서버)

여기서의 응용계층은 5 계층의 세션 계층과 6 계층의 표현 계층을 포함하는 것을 생각 응용 계층의 역할 애플리케이션(응용 계층에서 동작)은 클라이언트와 서버로 나눌 수 있음 클라이언트 : 서비스를 요청하는 측(사용자 측) 서버 : 서비스를 제공하는 측 사용자 측의 요청을 전달하기 위해 통신 대상이 이해할 수 있는 메시지로 변환하고 전송 계층에 전달하는 역할 클라이언트 애플리케이션과 서버 애플리케이션이 통신하기 위해선 응용 계층의 프로토콜이 필요 응용 계층에서 사용하는 대표적인 프로토콜 HTTP - 웹사이트 접속 FTP - 파일 전송 SMTP - 메일 송신 POP3 - 메일 수신 DNS - 이름 해석 이름 해석 : 네트워크에서 컴퓨터나 네트워크 장비 이름으로 IP 주소를 알아내는 것 응용 계층은 각각의 애..

원문보기 내부링크
Tistory

[네트워크/Network] 전송계층의 역할과 TCP 분석 ( + UDP)

전송 계층의 역할 물리 계층, 데이터 링크 계층, 네트워크 계층만 있으면 목적지에 데이터를 보낼 수 있음 → 하지만 데이터 손상 또는 유실 시 이 계층들에서는 아무것도 못함 → 전송 계층의 존재 이유 목적지에 신뢰할 수 있는 데이터를 전달하기 위해 필요 전송 계층의 2가지 기능 오류를 점검하는 기능 오류가 발생하면 데이터를 재전송하도록 요청 데이터가 제대로 도착했는지 확인 cf. 네트워크 계층 → 목적지까지 데이터를 전달하는 것 전송된 데이터의 목적지가 어떤 애플리케이션인지 식별하는 기능 컴퓨터가 데이터를 받아도 어떤 애플리케이션에 전달해야 하는지 모르면 안 됨 예 : 홈페이지용 데이터인데 메일 프로그램에 전달하면 안 됨 연결혈 통신과 비연결형 통신 전송 계층의 특징 → 신뢰성/정확성과 효율성 신뢰성/정..

원문보기 내부링크
Tistory

[C#] 하드웨어 최적화 - 메모리 베리어(Memory Barrier)

사용하는 이유 CPU가 코드 재배치 public class Program { static int x = 0; static int y = 0; static int r1 = 0; static int r2 = 0; static void Thread1() { y = 1; r1 = x; } static void Thread2() { x = 1; r2 = y; } static void Main(string[] args) { while (true) { x = y = r1 =r2 = 0; Task task1 = new Task(Thread1); Task task2 = new Task(Thread2); task1.Start(); task2.Start(); Task.WaitAll(task1, task2); // 두 쓰레드..

원문보기 내부링크
Tistory

[C++] 백준 22861 : 폴더 정리(large)

문제 이해 단계 https://www.acmicpc.net/problem/22861 main 폴더 안에 있는 폴더의 총 개수 N과 파일의 총 개수 M이 주어진다. 그리고 폴더를 옮기는 횟수 K가 주어진다. 폴더를 옮긴다는 것은 폴더 A에 있던 하위 폴더와 파일들을 모두 폴더 B로 옮긴다는 것 그리고 마지막에 쿼리 Q가 주어지고, 그 쿼리에 맞는 파일의 종류가 몇 개인지, 그리고 파일의 수가 몇 개인지 출력하는 문제 사실 문제가 상당히 길기 때문에 링크를 타고 들어가서 문제를 읽고 오는 편이 낫다. 문제 접근 단계 입력으로 들어오는 것이 많다. 그렇기 때문에 더더욱 제한사항부터 살펴봐야 한다. 폴더(N)와 파일(M)의 개수는 최대 1,000개까지 가능하다. 파일을 옮기는 횟수(K)도 최대 1,000회까지 ..

원문보기 내부링크
Tistory

[C++] 백준 9663 - N-Queen

문제 이해 단계 https://www.acmicpc.net/problem/9663 NxN짜리 체스판에 N개의 퀸을 서로 공격하지 못하게 둔다. N이 주어졌을 때 이 경우의 수를 구하는 문제 문제 접근 단계 퀸이 움직일 수 있는 경로는 위와 같다. 퀸을 정가운데 놨을 때, 노란색 영역에는 퀸을 두면 안 된다. 제한사항부터 알아보면, N은 최대 14까지 가능하다. 이 말은 맵은 14x14까지, 체스 말은 14개까지 가능하다는 것이다. N이 상당히 작기 때문에 완전탐색이 가능할 것 같다. N개의 퀸을 체스판에 두는 모든 경우의 수를 구해야 하기 때문에 퀸을 모든 곳에 둬서 판단하는 방법밖에 없다. 그런데 일반적인 백트래킹으로 이를 확인하기에는 최대 14^14로 대략 100억이 넘어가기 때문에 제한시간 10초를..

원문보기 내부링크
Tistory

[C++] 백준 1167 - 트리의 지름

문제 이해 단계 https://www.acmicpc.net/problem/1167 입력으로 트리의 정점 개수 V와 간선의 정보가 주어진다. 트리의 간선에는 가중치가 존재한다. 임의의 두 정점 사이의 거리 중 가장 긴 것의 길이를 출력하는 문제 문제 접근 단계 문제 조건부터 살펴보면, 정점의 개수가 최대 100,000개다. 그렇다면 간선의 개수는 훨씬 더 많이 가능하다는 소리이다. 모든 정점을 일일이 하나씩 다 살펴보기에는 무리이다. 한 정점을 특정하여 찾는 방법밖에 없는 것 같다. 두 정점 사이의 길이가 가장 길어지려면? 트리에서 두 정점의 길이가 가장 길어지려면 어떻게 해야 할까? 당연히 한쪽 끝노드(리프 노드)에서 끝노드로 가는 것이 길이가 가장 길어질 것이다. 즉 우리가 우선적으로 찾아야 할 것은 ..

원문보기 내부링크
Tistory

[운영체제] 쓰레딩 관련 문제(신호 처리,LWP,취소,TLS 등) 정리

Fork() 및 Exec() 시스템 콜 다중 스레드 프로그램에서는 fork()와 exec()의 의미가 달라질 수 있다. fork()에 대한 질문 - 한 프로그램의 스레드가 fork()를 호출했을 때 새로운 프로세스는 모든 스레드를 복제해야 하는가? 한 개의 스레드만 가지는 프로세스여야 하는가? 몇몇 UNIX 기종은 두 가지 버전의 fork()를 다 제공 두 버전 중 어느 쪽을 택할 것인지는 응용프로그램에 달려 있음 exec() 시스템 콜을 부를 때 exec()의 매개변수로 지정된 프로그램이 모든 스레드를 포함한 전체 프로세스를 대체 fork()를 부르자마자 다시 exec를 부르면 모든 스레드를 복제해서 만들어주는 것은 불필요 ← exec에서 지정한 프로그램이 곧 모든 것을 다시 대체할 것이기 때문 이 경..

원문보기 내부링크
Tistory

[C++] 백준 2638 - 치즈

문제 이해 단계 https://www.acmicpc.net/problem/2638 NxM 크기의 맵에 1로 표기된 치즈가 있다. 치즈는 외부 공기와 두 번 이상 접촉하면 녹는다. 겉에서부터 치즈가 녹아내릴 때, 모든 치즈가 녹아내리는 데 걸리는 시간을 구하는 문제 문제 접근 단계 문제의 조건부터 살펴보자. 맵의 크기는 최대 100x100까지 가능하다. 맵의 크기는 그렇게 크지 않아서, 탐색을 하기에는 무리가 없을 것 같다. 문제의 유형 문제의 유형을 추측해 볼 때, 2차원 맵이 주어지고, 치즈가 없어지는 조건이 네 면 중 2 변이 접촉해야 하는 것이라고 했다. 이를 그림에서 살펴보면, 1이 없어지기 위해서는 겉에 있는 0과 2개 이상 인접해야 한다. 이를 쉽게 알아내기 위해서는 너비우선탐색(BFS)으로 ..

원문보기 내부링크
Tistory

[C++] 백준 1043 - 거짓말

문제 이해 단계 https://www.acmicpc.net/problem/1043 사람 수 N과 파티의 수 M이 주어진다. 그다음줄에는 진실을 아는 사람의 번호가 주어지는데, 지민이는 모든 파티를 참석하면서 거짓말을 쳐야 한다. 하지만 진실을 아는 사람이 있는 파티에서는 무조건 진실을 말해야 한다. 진실을 들은 사람이 거짓말을 듣거나, 거짓말을 들은 사람이 진실을 들으면 이는 실패한 것이다. 해당 조건에서 지민이가 거짓말을 칠 수 있는 파티의 최대 수를 구하는 문제 문제 접근 단계 문제의 제한조건부터 살펴보자. 사람의 수 N과 파티의 수 M이 모두 50까지 가능하다. 상당히 작은 숫자라서, 완전 탐색이나 원하는 대로 풀이가 가능할 것 같다. 문제의 특징 이 문제의 특징적인 점은, 옳고 그름을 판단하기 위..

원문보기 내부링크
Tistory

[운영체제] 암묵적 스레딩(implicit Threading) 개념 정리

암묵적 스레딩 암묵적 스레딩(implicit Threading) 스레딩의 생성과 관리 책임을 앱 개발자로부터 컴파일러와 실행시간 라이브러리에게 넘기는 것 앱 설계의 어려움을 극복하고 병행 및 병렬 앱 설계를 도와주는 방법 응용 프로그램 개발자가 병렬로 실행할 수 있는 스레드가 아닌 작업을 식별해야 함 작업은 일반적인 함수로 작성 런타임 라이브러리는 다대다 모델을 사용하여 별도의 스레드에 매핑 암묵적 스레딩 장점 개발자는 병렬 작업만 식별하면 된다. 라이브러리는 스레드 생성 및 관리에 대한 특정 세부사항을 결정 스레드 풀 다중 스레드 서버는 아직 여러 문제를 지님 스레드를 생성하는데 소요되는 시간 생성된 스레드가 단기 작업(곧 폐기될 스레드)이라면 더 문제가 됨 모든 요청마다 새 스레드를 만든다면, 동시 ..

원문보기 내부링크
Tistory

[C#] 쓰레드(Thread)와 쓰레드 풀(Thread Pool) 다루기( + Task)

Thread Thread 생성 using System; using System.Threading; // 추가해줘야 사용 가능 namespace ServerCore { public class Program { // 사용할 함수(쓰레드) static void MainThread() { Console.WriteLine("Create Thread"); } static void Main(string[] args) { //Thread 이름 = new Thread(함수 이름); Thread thread = new Thread(MainThread); thread.Start(); } } } using System.Threading을 추가해 줘야 사용이 가능하다. thread.Start()를 해야 만들어둔 thread가 ..

원문보기 내부링크
Tistory

[C++] 백준 1238 - 파티

문제 이해 단계 https://www.acmicpc.net/problem/1238 N개의 마을에 연결된 M개의 단방향 도로가 존재한다. 각 도로에는 오고 가는 시간(비용)이 존재한다. N개의 마을 중 특정 마을 X로 왕복해야 하는데, 어느 마을에서 출발하는 것이 가장 시간이 오래 걸리는가? 그때의 소요 시간을 구하는 출력하는 문제 문제 접근 단계 문제 유형 유추 N개의 마을에 연결된 M개의 단방향 도로라는 말을 읽자마자 바로 그래프 탐색이 떠올랐다. 마을을 정점으로 치환하고, 단방향 도로를 단방향 간선으로 본다. 그리고 걸리는 시간을 각 간선의 가중치로 보면 완벽한 그래프 탐색 문제이다. 로직 어쨌든 이 학생들은 무조건 최단 거리로 오고 간다고 했다. 그래프 탐색에서 최단거리라고 하면 생각나는 것이 크루..

원문보기 내부링크
Tistory

[C++] 백준 13905 - 세부

문제 이해 단계 https://www.acmicpc.net/problem/13905 섬 위에 N개의 집과 M개의 다리가 존재한다. 그리고 각 다리에는 무게 제한 K가 걸려있다. 입력으로 출발지와 목적지가 주어지는데, 혜빈이는 최대한 많은 금빼빼로를 들고 목적지까지 도착해야 한다. 각 다리에서 무게제한까지만 빼빼로를 들 수 있을 때 최대 몇 개까지 빼빼로를 옮길 수 있는가? 문제 접근 단계 제한사항부터 살펴보자. 존재하는 집의 수(N)는 100,000개, 다리의 수(M)는 300,000이다. 최대 10^5 * 10^5 = 10^10으로 완전탐색으로 하면 시간초과가 뜬다. 따라서 하나하나 비교하는 것은 안되고, 다른 방법이 필요하다. 그래프 탐색 결국엔 집과 집을 연결하는 것이 다리고, 그 다리에는 무게라는..

원문보기 내부링크
Tistory

[C++] 백준 21941 - 문자열 제거

문제 이해 단계 https://www.acmicpc.net/problem/21941 소문자 문장 S가 주어지고, 문자열 리스트들이 주어진다. 각 문자열 리스트들은 각자 점수를 가지고 있다. 문장 S에서 모든 문자들을 지워야 하는데 아래 2가지 연산만 할 수 있다. 1. 문자열 리스트에 존재한다면 해당 부분을 지우고 그 문자열만큼의 점수를 얻는다. 2. 문자 하나를 지우고 1점을 얻는다. 해당 연산을 통해 모든 문자를 지울 때 얻을 수 있는 최댓값을 구하는 문제 문제 접근 단계 범위 파악 문제 조건부터 살펴보자. 문장 S는 최대 1000개까지, 문자열 리스트는 100개, 그리고 점수는 개당 10,000점까지 가능하다. 만약 문장의 길이가 1000이고, 문자열이 하나로 구성된, 개당 10,000점짜리가 10..

원문보기 내부링크
Tistory

[C++] 백준 17141 - 연구소 2

문제 이해 단계 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net NxN 크기의 맵에 M개의 바이러스를 놓으려고 한다. 바이러스는 맵에 ' 2 '라고 표시되어 있는 곳에 밖에 놓지 못한다. 바이러스는 1초당 상하좌우로 인접한 모든 빈칸(1이라고 적힌 칸을 제외)한 칸으로 퍼진다. M개의 바이러스를 배치하여 최소한의 시간으로 모든 맵에 바이러스를 퍼뜨릴 때, 이 최소 시간은? 만약 모든 맵에 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다. 문제 접근 단계 문..

원문보기 내부링크
Tistory

[C++] 백준 16562 - 친구비

문제 이해 단계 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net N명이 학생이 있고 그 학생들 사이에 M개의 친구 관계가 존재한다. 그리고 각각의 학생마다 친구비가 존재하는데, 친구 관계인 친구였다면 그중 하나에게만 지불하면 된다. 해당 조건으로 K원을 가지고 있을 때, N명 학생과 모두 친구를 맺을 수 있는 최소 비용을 구하시오. 만약 구할 수 없으면 "Oh no"를 출력한다..

원문보기 내부링크
Tistory

[C++] 백준 1719 - 택배 ( 다익스트라 풀이 )

문제 이해 단계 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net n개의 정점과 m개의 간선이 존재한다. 그리고 간선 사이에는 가중치가 존재한다. 모든 정점에서 다른 정점으로의 경로표를 만들어야 한다. 한 정점에서 다른 정점으로 최단경로로 움직일 때, 거쳐야 하는 다른 정점을 경로표에 적어 넣는다. 그리고 경로표 전체를 출력하는 것이 해당 문제이다. 문제 접근 단계 로직 유추 문제를 보면 바로 정점과 간선이 있는 그래프를 준다. 이 점을 보니 바로 그래프..

원문보기 내부링크
Tistory

[C++] 백준 1726 - 로봇

문제 이해 단계 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net MxN짜리 맵에 입력으로 출발 좌표와 목적 좌표가 주어진다. 출발지에서 로봇이 출발하는데 로봇이 할 수 있는 행동은 아래의 2가지이다. 로봇을 목적지에 도착시키고, 원하는 방향을 바라보게 하는데 걸리는 최소 명령 횟수를 구하는 문제 문제 접근 단계 맵의 크기는 최대 100 x 100 까지만 가능하다. 그렇게 크지는 않다. 탐색으로 인한 시간초과는 그렇게 신경 쓰지 않아도 되는 걸로 보인다. ..

원문보기 내부링크
Tistory

[C#] Nullable(널러블)이란? + 사용법

Nullable이란? Nullable은 Null + able의 합성어로 C#에서 제공하는 새로운 문법이다. Nullable은 변수형 타입을 의미하는데, 변수형을 Nullable로 만들면 값으로 Null을 가지지 못하는 변수형도 Null 값을 가질 수 있다. 사용 방법 ? 키워드 사용 방법은 간단하다. public static void Main(string[] args) { //선언하는 방법 int? ex1 = null; bool? ex2 = null; float? ex3 = 3f; // 값 수정 ex1 = 3; ex2 = true; ex3 = 4.0f; // 값 대입 int a = ex1.Value; //값 호출하는 방법 Console.WriteLine($"ex1 :{ex1.Value}"); Consol..

원문보기 내부링크
Tistory

[C++] 백준 16432 - 떡장수와 호랑이

문제 이해 단계 https://www.acmicpc.net/problem/16432 호랑이에게 N일 동안 떡을 줘야 한다. 떡을 줄 때 이틀 연속해서 같은 번호의 떡을 주어선 안된다. 떡의 종류는 1~9번까지 총 9개가 존재한다. 입력으로 N일이 들어오고, 그다음 줄부터 i번째 날의 가져갈 떡의 수 m과 떡의 종류가 주어진다. 호랑이에게 떡을 줄 수 있는 경우엔 여러 가지 경우의 수 중 하나를 출력하고, 그렇지 않은 경우엔 -1을 출력한다. 문제 접근 단계 제한사항부터 살펴보면, N(일)의 최대는 1,000이다. 떡의 종류는 최대 9개까지 가능하다. 아이디어 처음에는 당연히 연속되는 경우를 제외하고, 모든 종류를 하나씩 살펴보는 백트래킹 방식을 사용하려고 했는데 이 방식은 8^1,000이 되기 때문에 시..

원문보기 내부링크
Tistory

[C#] 델리게이트(Delegate)와 이벤트(Event)의 필요성 및 사용법

델리게이트(Delegate) - 대리자 용도 델리게이트를 사용하면 함수 자체를 인자로 넘겨준 후, 그 함수를 호출하여 사용할 수 있다. public class EmptyClass { static void Receive(/* 함수를 인자(매개변수)로 넘겨받음*/) { // 인자로 넘겨받은 함수 실행 } public static void Main(string[] args) { Receive(/* 매개변수로 넘기길 원하는 함수 */); } } Receive 함수의 매개변수로 특정 함수가 들어간 뒤, 이를 Receive 함수에서 호출할 수 있다는 것이다. 델리게이트 필요성 근데 이런 짓을 왜 하는 것일까? 그냥 Receive 함수 안에 실행하려는 함수를 넣거나, 코드를 넣으면 안 되나?? 유니티 개발 환경에서 ..

원문보기 내부링크
Tistory

[C#] 얕은(Shallow) 복사와 깊은(Deep) 복사 이해하기

지난 포스팅에서 이어서 설명한다고 했던 깊은 복사에 대해 다루려고 한다. 깊은 복사에 대해 이야기하면 필연적으로 얕은 복사와 함께 이야기하는데, 얕은 복사와 깊은 복사를 비교해 보며 알아보자. 정의 정의적인 부분부터 살펴보자. 얕은 복사 복사하려는 원본에 대한 새로운 객체(복사본)를 생성하는데, 이 객체는 원본 객체를 참조한다. 즉, 생성된 복사본은 원본 객체가 가리키는 주소와 같은 곳을 가리키게 된다. 그렇기 때문에 복사본은 원본 객체에 종속적이다. 이는 주소에 의한 참조랑 비슷한 의미로 생각해도 된다. 깊은 복사 얕은 복사와 같이 원본에 대한 복사본을 생성하는데, 인스턴스화할 수 있는 모든 요소(내부의 클래스 변수, 메서드, 인스턴스 값 등)를 모조리 복사한다. 그렇게 하여 원본 객체로부터 완전히 독..

원문보기 내부링크
Tistory

[C++] 백준 1823 - 수확

문제 이해 단계 https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 일렬로 나열되어 있는 정수가 1 ~ N까지 존재한다. 이 숫자들을 얻기 위해서는 양끝부터 얻어야 한다. 숫자를 얻었을 때 이익은 다음과 같다. 이익 = 숫자*(고른 순서) 해당 조건과 같을 때 얻을 수 있는 가장 최대의 이익을 구하는 문제 문제 접근 단계 벼의 개수는 최대 2,000개까지, 그리고 정수는 최대 1,000까지 가능하다. 일단 정수를 양쪽 끝에서부터 얻을 수 있기 때문에 왼쪽과 오른쪽을 분리해서 생각하긴..

원문보기 내부링크
Tistory

[C#] 매개변수로써의 구조체와 클래스의 차이

매개변수로의 구조체와 클래스 사용 얕은 복사와 깊은 복사에 대해 알기 전에 구조체와 클래스에 대해 이야기해보려고 한다. // 클래스 Test_c class Test_c { public int a; public int b; } // 구조체 Test_s struct Test_s { public int a; public int b; }; 둘 다 int형 변수 a, b를 담고 있는 변수형이다. 기능으로는 큰 차이가 없어 보인다. 그럼 이렇게 변수를 한 곳에 모아두는 것으로만 사용할 때는 사실 큰 차이가 없는 것일까? 다른 계산 결과가 나오는 예시 코드 그렇지 않다. 아래의 예시를 보자. using System; namespace CSharp_Test { class Test_c { public int a; } s..

원문보기 내부링크
Tistory

[C++] 백준 1865 - 웜홀

문제 이해 단계 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net N개의 지점과 그 지점 사이에는 M개의 도로와 W개의 웜홀이 존재한다. 여기서 도로는 양방향이고 웜홀은 단방향이다. 도로와 웜홀의 정보는 공통적으로 (시작 지점, 도착 지점, 가는 시간)으로 들어온다. 웜홀은 시작했을 때보다 도착했을 때 시간이 거꾸로 가게 된다. 한 지점에서 출발하여 다시 출발했던 지점을 돌아올 때, 출발했을 때보다 시간이 돌아가있는 것이 가능한가?를..

원문보기 내부링크
Tistory

[C++] 백준 1937 - 욕심쟁이 판다

문제 이해 단계 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net NxN 크기의 맵에 대나무가 각 칸에 존재한다. 대나무는 정수값이다. 판다가 이걸 먹는데, 먹고 난 이후에는 상하좌우로 움직인다. 판다는 움직일 때, 먹은 그 칸의 대나무보다 많은 칸으로밖에 이동하지 못한다. 맨 처음 판다를 놓을 수 있는 칸을 정할 수 있을 때, 판다가 최대한 많이 움직일 수 있는 칸의 수를 구하는 문제 문제 접근 단계 일단 맵의 크기는 최대 500x5..

원문보기 내부링크
Tistory

[C++] 백준 20924 - 트리의 기둥과 가지

문제 이해 단계 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 노드의 개수 N과 루트 번호 R이 들어온다. 그리고 N-1개의 노드 정보가 주어지는데, (a, b, c) -> a번 노드와 b번 노드가 연결되어 있는데 길이는 c이다. 그리고 기가 노드라는 것이 존재하는데, 이는 루트노드에서 시작했을 때 최초로 자식 노드가 2개 이상인..

원문보기 내부링크
Tistory

[운영체제] 다중 쓰레드 모델(Multi-Thread Model) 종류

다중 스레드 모델(MultiThreading Model) 수준 차이에 따른 스레드 지원 사용자 스레드(user threads) : 사용자 수준에서 지원하는 스레드 커널 위에서 지원되고 커널의 지원 없이 관리 커널 스레드(ker-nel threads) : 커널 수준에서 제공되는 스레드 커널 스레드는 운영체제에 의해 직접 지원되고 관리 거의 모든 현대 운영체제들은 커널 스레드를 지원 궁극적으로 사용자 스레드와 커널 스레드에는 어떤 연관 관계가 존재해야 함. 다대일 모델(Many-to-One Model) 많은 사용자 수준 스레드가 하나의 커널 스레드를 사상함 장점 스레드 관리는 사용자 공간의 스레드 라이브러리에 의해 행해짐 → 효율적 단점 한 스레드가 봉쇄형 시스템 콜할 경우, 전체 프로세스가 봉쇄 한 번에 ..

원문보기 내부링크
Tistory

[C++] 백준 21940 - 가운데에서 만나기 (다익스트라 알고리즘 풀이)

문제 이해 단계 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 정점과 간선 정보가 주어진다. 각 간선은 단방향으로 주어지고, 간선에는 시간이라는 가중치가 존재한다. 여기서 선택해야 하는 것은 왕복 시간(목적지로 갔다가 다시 돌아오는데 드는 시간)이 가장 많이 드는 사람의 시간을 최소화하는 도시를 선택하는 것이다. 도시의 개수 N과 간선의 개수 M, 그리고 사람 수 K와 각 사람이 사는 도시 정보가 주어진다. 왕복 시간이 가장 많이 드는 사람의 시간을 최소화하는 도시를 출력하고, 만약 여러 개..

원문보기 내부링크
Tistory

[C++] 백준 13019 - A를 B로

문제 이해 단계 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 대문자 알파벳으로 이루어진 문자열 A와 B가 입력으로 들어온다. 문자열 A를 B로 바꾸는 것이 목표. 할 수 있는 연산은 알파벳 하나를 골라 가장 앞으로 보내는 것이다. 이때 최소 몇 번 만에 만들 수 있는지 구하는 문제 문제 접근 단계 일단 입력으로 들어오는 문자열의 길이가 50이 넘지 않는다. 따라서 시간초과는 크게 신경 쓰지 않아도 될 것 같다. 연산에서 중간에 있는 문자를 골라도 상관이 없다. 하지만 무조건 가장 앞으로 보내..

원문보기 내부링크
Tistory

[C++] 백준 22945 - 팀 빌딩

문제 이해 단계 https://www.acmicpc.net/problem/22945 22945번: 팀 빌딩 능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같 www.acmicpc.net 능력치가 다 다른 N명이 입력으로 들어온다. 이 중에서 2명을 뽑아서 값을 만들 때, 값을 구하는 공식은 아래와 같다. (A와 B 사이에 존재하는 다른 사람 수)*min(A, B) 이러한 조건일 때 나올 수 있는 값의 최대치를 구하는 문제 문제 접근 단계 문제풀이를 위해 조건부터 살펴보자. 들어올 수 있는 사람 N은 최대 100,000까지 가능하고, 능력치는 10,000까지 ..

원문보기 내부링크
Tistory

[Unity 3D/VR] XR Interaction Toolkit 커스텀 컨트롤러 모델링

XR Origin → LeftHand Controller 하위 오브젝트로 큐브, 구 등 원하는 대로 배치하여 커스텀 게임 실행 시 자동으로 모델링 되도록 하기 프리팹화 만들어둔 모델을 프로젝트 창으로 드래그하여 프리팹화함 기존에 Hierarchy에 있던 Model들은 삭제 LeftHand Controller와 rightHand Controller에 있던 Model Prefab에 프리팹을 넣음 연결된 프리팹을 자동으로 게임 오브젝트로 만들어서 배치해 줌 결과 1 게임 실행 시 자동으로 커스텀했던 모델이 XR Origin과 붙어서 나오는 것을 확인 가능 결과 2 VR 움직임이 잘 된다.

원문보기 내부링크
Tistory

[C++] 백준 6068 - 시간 관리하기

문제 이해 단계 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1 N; vector v(N); // 일을 담을 벡터 int avail = 0; for(int i = 0; i < N; i++){ int v1, v2; cin >> v1 >> v2; v[i] = {v1,v2}; avail = max(avail,v2-v1); // 필요하는 최소 시간이 가장 많은 걸 시작 시간으로 둚 } sort(v.begin(),v.end(),compare); // 정렬 // 0 이상일때까진 반복 while(avail >= 0){ int cnt = avail; // cnt -> 현재 시간 ..

원문보기 내부링크
Tistory

[운영체제] 스레드(Thread)의 기본 개념과 다중 코어 프로그래밍

스레드(Thread) 개요 스레드(Thread) : CPU 이용의 기본 단위 구성 → 스레드 ID + 프로그램 카운터(PC) + 레지스터 집합 + 스택 같은 프로세스에 속한 다른 스레드와 운영체제 자원들을 공유 운영체제 자원들 → 코드, 데이터 섹션, 열린 파일이나 신호 같은 것 2가지의 스레드 단일 스레드 프로세스 : 전통적인 프로세스로, 하나의 제어 스레드를 가지고 있다. 한 번에 하나의 작업만 수행할 수 있음 다중 스레드 프로세스 : 하나의 프로세스가 다수의 제어 스레드를 가지고 있음 동시에 하나 이상의 작업을 수행할 수 있다. 동기(Motivation) 현대의 거의 모든 소프트웨어 응용들은 다중 스레드를 이용한다. 하나의 응용은 몇 개의 실행 흐름을 가진 독립적인 프로세스로 구현된다. 예 워드에서..

원문보기 내부링크
Tistory

[C++] 백준 10282 - 해킹

문제 이해 단계 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net A가 B에 의존하면, B가 감염됐을 때 A도 감염된다. 이를 의존이라고 한다. 입력으로 테스트 케이스, 컴퓨터 개수 n, 의존성 관계 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다. 의존성 관계 정보는 (a, b, s)로 주어지는데, 이는 컴퓨터 a가 컴퓨터 b를 의존하고, b가 감염된 후 s초 후 컴퓨터 a도 감염된다는 뜻이다. 해당 조건일 때 출력으로 컴퓨터 수, 마지막 컴퓨터가..

원문보기 내부링크
Tistory

[C++] 백준 1477 - 휴게소 세우기

문제 이해 단계 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 입력으로 가지고 있는 휴게소 N과 만들어야 할 휴게소 M, 그리고 고속도로 길이 L이 주어진다. 휴게소를 M개를 더 지어 휴게소 사이의 거리를 최소화하려고 한다. 고속도로 끝과 중복된 곳에 배치하는 것은 금지한다. 휴게소들 사이의 거리가 최소가 되도록 이상적으로 배치했을 때, 그중 구간의 길이가 가장 긴 것을 출력하는 문제. 문제 접근 단계 문제가 말을 어렵게 써놔서 이해하는 게 한참 걸렸다. 이 문제의..

원문보기 내부링크
Tistory

[Unity 3D/VR] XR Interaction Toolkit으로 HMD 생성 및 시뮬레이터로 사용

HMD 새로운 Scene 생성 File → New Scene → Standard(URP) 선택 저장 장소는 Scenes 폴더 안에 적당한 이름으로 저장 XR Origin 게임 오브젝트 생성 Hierarchy 창에서 우클릭 → XR → XR Origin(VR)을 클릭 XR Origin(VR) 게임 오브젝트는 뭘까? HMD나 컨트롤러 등 연동된 장비의 기준이 되는 오브젝트 VR/AR 세상의 중심이나, 헤드셋 기준 높이 등을 설정할 때 사용 일반적으로 HMD와 연동된 메인 카메라 게임 오브젝트와 양손 컨트롤러와 연동된 게임 오브젝트 등을 자식으로 배치 자동적으로 메인 카메라가 XR Origin 게임 오브젝트의 자식 오브젝트로 들어감 XR Interaction Mananger라는 게임 오브젝트도 함께 생성 Ma..

원문보기 내부링크
Tistory

[Unity 3D/VR] XR Interaction Toolkit 소개 및 프로젝트 세팅

해당 학습은 VR기기가 없어도 시뮬레이터를 통해 게임 제작 및 테스트가 가능합니다. 때문에 VR 기기가 없어도 학습이 가능함을 알려드립니다. 개요 XR Interaction ToolKit이란? Unity에서 제작한 Unity XR 기반의 플러그인 유니티의 공식 플러그인 → 지원 및 업데이트가 보장될 것이라는 장점 모든 VR 플러그인 중 수명이 가장 김 VR의 일반적인 기능을 스크립트 없이 편하게 구현할 수 있음 Teleportation이나 Interaction 등 스크립트 작성량이 가장 적음 유니티에서 지원하는 다양한 VR장비들을 모바일과 PC에 손쉽게 연동 가능 PC/Mobile VR 장비에 모두 대응 가능 AR Foundation을 연동하면 AR 콘텐츠 제작해도 활용 가능 XR Interaction ..

원문보기 내부링크
Tistory

[C++] 백준 14267 - 회사 문화 1

문제 이해 단계 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 입력으로 직원수 n과 칭찬의 횟수 m이 주어진다. 그리고 직원은 1번부터 n번까지 번호가 매겨져 있다. 해당 문제에서 칭찬은 상사가 직속 부하를 칭찬하면 그 부하가 부하를, 또 그 부하를 연쇄적으로 칭찬하는 내리 칭찬 형식이다. 칭찬에는 각각의 수치가 존재한다. 두 번째 입력으로는 n개의 직속 상사와 부하관계가 주어진다. 직속 상사의 번호는 항상 자신의 번호보다 작다. 그리고 3..

원문보기 내부링크
Tistory

[C++] 백준 14226 - 이모티콘

문제 이해 단계 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 입력으로 S가 주어지고, S개의 이모티콘을 만드는 게 목표이다. 다음의 3가지 연산만을 사용하여 S개의 이모티콘을 만들어야 한다. 기본적으로 이모티콘 1개는 입력되어 있다. 모든 연산은 1초씩 걸리고, 클립보드에 복사하면 이전에 있던 내용은 없어지고 덮어쓰기 된다. 해당 조건일 때 이모티콘 S개를 만들기 위해 필요한 시간의 최솟값을 구하는 문제 문제 접근 단계 입력으로 주어지는 S는..

원문보기 내부링크
Tistory

[운영체제] 파이프(Pipe)와 클라이언트 서버 환경에서의 통신

파이프 파이프는 두 프로세스가 통신할 수 있게 하는 전달자로서 동작 초기 UNIX 시스템에서 제공하는 IPC 기법의 하나 파이프는 프로세스 간에 통신하는 간단한 방법이지만, 통신할 때 여러 제약이 발생 파이프 구현을 위해 고려해야 할 점 파이프가 단방향 또는 양방향 통신을 허용하는가? 양방향 통신이 허용된다면 → 반이중 방식인가, 전이중 방식인가? 반이중 방식 : 한 순간에 한 방향 전송만 가능 전이중 방식 : 동시에 양방향 데이터 전송 가능 통신하는 두 프로세스 간에 부모-자식과 같은 특정 관계가 존재해야 하는가? 파이프는 네트워크를 통해 통신이 가능한가, 아니면 동일 기계 안에 있는 두 프로세스끼리만 가능? 일반 파이프 일반 파이프는 생산자-소비자 형태로, 두 프로세스 간의 통신을 허용 생산자는 쓰기..

원문보기 내부링크
Tistory

[C++] 백준 7682 - 틱택토

문제 이해 단계 https://www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net 3x3 게임판에 O와 X 두 가지를 가지고 게임을 한다. 무조건 X를 먼저 두는 것을 시작으로 X와 O를 번갈아가면서 둔다. 게임에서 이기는 조건은 X나 O가 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하는 것이다. 이를 틱택토라고 부르겠다. 틱택토를 성공하는 순간 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다. 입력으로는 게임판의 최종상태가 주어지는..

원문보기 내부링크
Tistory

[C++] 백준 3151 - 합이 0

문제 이해 단계 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net N개의 입력이 일렬로 들어온다. 입력은 정수로 들어오는데, 숫자가 -10,000 ~ 10,000 사이로 들어온다. 숫자 3개를 골라서 합이 0이 되는 경우가 몇 가지가 나오는지 찾는 문제. 숫자가 같아도 위치가 다르면 다른 경우의 수로 취급한다. 문제 접근 단계 제한사항부터 살펴보면 N개의 입력은 최대 10,000개까지 들어올 수 있다. 숫자가 3개를 골라야 하기 때문에 10000 C3..

원문보기 내부링크
Tistory

[Unity 3D] 메가 번들 기간 한정 할인 안내 ( ~ 4월 27일)

* 이 글은 어필리에이트 링크를 포함하고 있습니다. 링크를 클릭하셔서 추천하는 에셋을 구매하시면 어필리에이트에게 수익이 발생합니다. 링크를 클릭만 하는 것으로는 수익이 발생하지 않지만, 프로젝트의 개발과 우수한 에셋의 추천에 큰 도움이 됩니다. 안녕하세요! 여태까지 CS/ 알고리즘 관련 글만 써오다가 이렇게 정보 관련 글로 찾아뵙는 건 처음이네요. 다름이 아니라, 이번에 유니티에서 한국 시간 2023년4월 6일 오전 12시부터 4월 27일 오전 12시까지 메가번들을 할인 판매한다고 해서 알려드리러 왔습니다! 이번에 판매하는 메가 번들의 테마는 시간 여행(Time Travel) 입니다! 사실 테마는 우리에게 중요한 게 아니죠! 이게 어떤 패키지로 구성되어 있고, 얼마나 세일하는지가 중요하겠죠? 완성도 높은..

원문보기 내부링크
Tistory

[C++] 백준 16987 - 계란으로 계란치기

문제 이해 단계 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net N개의 계란이 존재하고, 각 계란에는 (내구도, 무게) 정보가 쌍으로 주어진다. 그리고 두 계란이 부딪힐 때 서로의 무게만큼 내구도가 깎여나간다. 내구도가 0 이하가 되면 계란이 깨지는 것으로 간주한다. 그리고 계란을 깨는 과정은 아래와 같이 한다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 ..

원문보기 내부링크
Tistory

[운영체제] 프로세스 간 통신 개념 및 기법 정리

프로세스 간 통신 운영체제 내에서 실행되는 병행 프로세스들은 독립적이거나 협력적인 프로세스 일 수 있다. 독립적 : 실행 중인 다른 프로세스들과 데이터를 공유하지 않는 프로세스 협력적 : 실행 중인 다른 프로세스들과 영향을 주고받는 프로세스 프로세스 협력을 허용하는 환경을 제공하는 이유 정보 공유 여러 응용 프로그램이 동일한 정보(복사, 붙여 넣기 등)를 원할수도 있음 → 그러한 정보를 병행적으로 접근할 수 있는 환경을 제공해야 함 계산 가속화 특정 태스크를 빨리 실행하고자 함 → 태스크를 서브태스크로 나누어 이를 다른 서브태스크들과 병렬로 실행하면 됨 가속화는 복수 개의 처리 코어를 가진 경우에만 가능 모듈성 시스템 기능을 별도의 프로세스 또는 스레드로 나누어, 모듈식 형태로 시스템을 구성할 수도 있음..

원문보기 내부링크
Tistory

[C++] 백준 21939 - 문제 추천 시스템 Version 1

문제 이해 단계 https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제가 N개 주어지는데 (문제의 번호, 난이도)의 쌍으로 이루어진다. 이후 명령어 M개가 들어오는데 각 명령어는 아래와 같다. 해당 조건일 때 recommend x로 나오는 출력을 그대로 구현해라는 문제 문제 접근 단계 문제 제한 사항부터 살펴보자. 문제의 개수 N은 최대 100,000개까지, 명령어 M의 개수는 10,000개이다. 최대 100,000..

원문보기 내부링크
Tistory

[C++] 백준 17070 - 파이프 옮기기 1

문제 이해 단계 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net NxN짜리 격자판이 존재한다. 그리고 중간에 벽(1)이 존재한다 그리고 2칸을 차지하는 파이프가 존재하는데, 무조건 (1,1)과 (1,2)에서 시작한다. 목표는 파이프가 벽에 부딪히지 않고, (N, N)까지 이동하는 것이다. 파이프는 회전이 가능한데, 움직이면서 회전이 가능하다. 회전은 한 번에 45도씩만 가능하다. 움직이는 방향은 →↓으로만 움직일 수 ..

원문보기 내부링크
Tistory

[네트워크/Network] 네트워크 계층의 역할과 및 IP 구조

네트워크 계층의 역할 네트워크 간의 연결 구조 네트워크 계층 역할 : 네트워크 간의 통신을 가능하게 하는 것 서로 다른 네트워크에 있는 컴퓨터로 데이터 전송이 가능해짐 데이터 링크 계층 → 같은 네트워크에 있는 컴퓨터로만 데이터 전송 가능 라우터 다른 네트워크로 데이터를 전송하기 위해 필요한 네트워크 장비 거리에 관계없이 데이터를 보낼 수 있음 해당 목적지까지 어떤 경로로 가는 것이 좋은지 알려주는 기능 데이터를 보내려는 곳의 주소(목적지)를 알아야 함 → IP주소를 알아야 함 IP 주소 : 어떤 네트워크의 어떤 컴퓨터인지를 구분할 수 있도록 하는 주소 IP주소가 있으면 다른 네트워크에 있는 목적지를 지정 가능 라우팅 테이블에 경로 정보를 등록하고 관리 라우팅 : 목적지 IP주소까지 어떤 경로로 데이터를..

원문보기 내부링크
Tistory

[C++] 백준 17073 - 나무 위의 빗물

문제 이해 단계 https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net N개의 노드와 고인 물의 양 W가 주어진다. 루트 노드는 항상 1번으로 고정이다. 모든 노드는 루트 노드인 1번 노드의 자식 노드이다. 1번 노드로부터 물이 떨어지는데, 떨어지는 규칙은 다음과 같다. 1. 물을 가지고 있을 경우, 자식 노드가 있다면 자식 노드 중 하나를 골라 물을 1 준다. (자식 노드가 여러 개라면 동일한 확률로 하나를 ..

원문보기 내부링크
Tistory

[네트워크/Network] 데이터 링크 계층 역할과 이더넷

데이터 링크 계층의 역할과 이더넷 랜에서 데이터를 주고받으려면 데이터 링크 계층의 기술이 필요 이더넷 이더넷(Ethernet) : 데이터 링크 계층 규칙 중 일반적으로 가장 많이 사용되는 규칙 데이터 링크 계층 규칙 : 네트워크 장비 간에 신호를 주고받는 규칙 이더넷은 랜에서 적용되는 규칙을 뜻함 → 허브와 같은 장비에 연결된 컴퓨터와 데이터를 주고받을 때 사용 특정 컴퓨터에만 데이터를 보내기 위해, 보내려는 데이터에 목적지 정보를 추가 → 목적지 이외의 컴퓨터는 데이터를 받더라도 무시하게 됨 여러 컴퓨터가 동시에 데이터를 전송해도 충돌하지 않는 구조로 되어있음 → 데이터를 보내는 시점을 늦춤(CSMA/CD) CSMA/CD 반송파 감지 다중 접속 및 충돌 탐지의 약어 아래의 규칙들 덕분에 충돌이 일어나지..

원문보기 내부링크
Tistory

[네트워크/Network] 물리 계층의 역할 & 랜 케이블과 허브

물리 계층의 역할과 랜 카드의 구조 데이터와 전기신호 아날로그 신호 : 물결 모양의 전기 신호 전화 회선, 라디오 방송에 사용되는 신호 디지털 신호 : 막대 모양이랑 비슷 데이터가 전송되는 과정 송신 측에서 전송하는 비트열 데이터는 전기 신호로 변환되어 네트워크를 통해 수신 측에 도착 비트열 데이터 : 0과 1로 이루어져 있는 데이터 수신 측에서는 전기 신호를 비트열 데이터로 복원 전기 신호 변환은 물리 계층(1 계층)에서 일어나는 과정 물리 계층 컴퓨터와 네트워크 장비를 연결하고, 컴퓨터와 네트워크 장비 간에 전송되는 데이터를 전기 신호로 변환하는 계층 데이터가 전기신호로 변환되는 방법(랜카드) 랜 카드를 통해 네트워크에서 데이터를 주고받음 0과 1의 정보가 랜카드로 전송되고, 랜 카드는 0과 1을 전..

원문보기 내부링크
Tistory

[운영체제] 프로세스 생성과 종료 개념 정리

프로세스에 대한 연산 대부분 시스템 내의 프로세스들은 병행 실행될 수 있으며, 동적으로 생성되고, 제거되어야 한다. → 운영체제는 프로세스 생성 및 종료를 위한 기법을 제공해야 한다. 프로세스 생성 프로세스는 여러 개의 새로운 프로세스를 새로운 프로세스를 생성할 수 있다. 부모 프로세스 : 프로세스를 생성하는 프로세스 자식 프로세스 : 생성된 새로운 프로세스 자식 프로세스는 또다시 다른 프로세스를 생성할 수 있다. 부모와 자식 프로세스가 이어져 트리를 형성한다. 프로세스 식별자 프로세스 식별자(pid) : 프로세스를 구분하는 데 사용하는 식별자 해당 식별자는 보통 정수 UNIX, Linux 및 Windows와 같은 대부분의 현대 운영체제들이 사용 pid는 시스템의 각 프로세스에 고유한 값을 가지도록 할당..

원문보기 내부링크
Tistory

[C++] 백준 19539 - 사과나무

문제 이해 단계 https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 일렬로 1부터 N번까지 나무가 존재하는데, 나무의 초기 높이는 모두 0이다. 그리고 나무를 1 성장시킬 수 있는 물뿌리개와, 나무를 2 성장시킬 수 있는 물뿌리개 2개가 존재한다. 두 물뿌리개는 무조건 동시에 뿌려야 하고, 한 나무에 몰아서 줘서 3을 성장시킬 수 있다. N개의 정수가 주어졌을 때, 해당 물뿌리개들로 해당 높이 배치를 만들 수 있는지 판단하는 문제 문제 접근 단계 문제의 조건부터 살펴보면, 나무의 개수는 최대..

원문보기 내부링크
Tistory

[운영체제] 프로세스 스케줄링 개념 정리

프로세스 스케줄링 다중 프로그래밍 목적 CPU 이용을 최대화하기 위해 항상 어떤 프로세스를 실행하는 것 시분할의 목적 프로세스들 사이에서 CPU 코어를 계속 교체하는 것 ← 각 프로그램이 실행되는 동안 사용자가 상호작용 할 수 있도록 하기 위해 시분할과 다중 프로그래밍의 목적을 달성하기 위해 프로세스 스케줄러가 존재 프로세스 스케줄러 : 코어에서 실행 가능한 프로세스 중 하나를 선택 각 CPU 코어는 한 번에 하나의 프로세스만 실행 가능 → 코어보다 많은 프로세스가 있는 경우, 초과 프로세스는 코어가 사용 가능해지고, 다시 스케줄 될 때까지 대기 현재 메모리에 있는 프로세스 수를 다중 프로그래밍 정도라고 함 프로세스는 대부분 2가지로 나눌 수 있음 I/O 바운드 프로세스 : 계산에 소비하는 것보다 I/O..

원문보기 내부링크
1 2 3 4 5