CS
[BaekJoon] 백준 15650번 N과 M (2)
[BaekJoon] 백준 15650번 N과 M (2) 문제: www.acmicpc.net/problem/15650 내코드 15649번 N과 M (1)과 거의 동일하지만 오름차순으로 출력해야 한다는 것이 달랐다. 즉, (1)번 문제는 (1 2), (2 1)이 다른 배열로 처리되었지만 (2)번 문제에서는 둘중 오름차순인 (1 2)만출력해야 된다는 것 [1, 3]과 같은 리스트가 있을 때, 다음 숫자를 정하는 과정에서 새로운 수가 3보다 작으면 pass하는 방식으로 처리해줬다. # BaekJoon 15649.py N과 M(2) # 백트래킹 문제: 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 n, m = map(int, input().split()) vis..
[BaekJoon] 백준 15649번 N과 M(1)
[BaekJoon] 백준 15649번 N과 M(1) 문제: www.acmicpc.net/problem/15649 내코드 백트래킹 문제: 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 백트래킹 문제를 처음 풀어보는 것이기도 했고, 구현 과정이 상당히 어려웠다. 리스트에 값을 하나씩 넣어주면서 풀어주는 문제 만약 1-4의 수가 있고, 2자리 수열을 만들어줘야 한다고 가정해보자. [1, x] -> [1, 2] -> [1, 3] -> [1, 4] -> [2, x] -> [2, 1] -> [2, 3] -> [2, 4] 이런식으로 리스트에 수가 들어갈것 수가 사용될때마다 visited에서 해당 값은 True로 처리 n, m = map(int, input().sp..
[OS] Process 동기화(1)
[OS] Process 동기화(1) Process 동기화란 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것 임계구역(Critical Section) 문제 do { entry section critical section exit section remainder section } while(TRUE); 임계구역은 여러개의 프로세스가 수행되는 시스템에서 각 프로세스들이 공유하는 데이터를 변경하는 코드 영역을 말함 간단하게 말하면, A라는 변수를 2개의 프로세스가 공유한다고 해보자. 각 프로세스가 코드에서 A 값을 변경한다면 해당 코드는 임계구역이다. 임계구역을 해결하기 위해서 만족해야 하는 조건 Mutual exclusion(상호배타): 임계구역에 오직 한 프로세스만 진입 가능 Progress(진행): ..
[BaekJoon] 11729번 하노이 탑 이동 순서
[BaekJoon] 11729번 하노이 탑 이동 순서 문제: www.acmicpc.net/problem/11729 내코드 A,B,C 기둥이 있고, n개의 원판이 있다고 생각하자 A기둥에 n개의 원판이 있을 때 C 기둥으로 옮기려면 n-1개를 B기둥으로 옮기고 나머지 가장 큰 한개를 C로 옮기고 B기둥에 있는 n-1개를 C로 옮기면 된다 이렇게 생각하면 재귀가 적용이 된다. 위의 3과정을 그대로 코드로 옮겨주면 된다. n-1개의 원판을 옮기는 방법, n-2개... 이렇게 반복되는 것 주의) 원판이 한개인 경우는 한번만 옮기면 되므로 따로 처리해준다. def hanoi(n, a, b, c): # 원판이 한개인 경우는 한번만 옮기면 되므로 따로 처리 if n == 1: print(a, c) # a기둥에 n개의..
[OS] 동기와 비동기
[OS] 동기와 비동기 동기는 어떤 일이 끝난 후에 다음일을 하는 것, 비동기는 어떤 일이 끝나지 않더라도 다음 일을 수행할 수 있는 것이다. Blocking & None-Blocking 동기 & 비동기를 살펴보기 전에 blocking & none-blocking 먼저 살펴보자 Blocking I/O 작업은 user level에서 직접 수행할 수 없고 kernel level로 들어가야 한다. 따라서 user level에서 kernel level로system call을 보내서 I/O 작업을 수행한다. 이때 application 단의 스레드에 block이 걸린다. (I/O 작업이 끝나기 전까지 반환되지 않기 때문) 그리고 kernel level에서 해당 I/O 작업이 끝나고 데이터를 반환하면 그때서야 app..
[BaekJoon] 백준 1629번 곱셈
[BaekJoon] 백준 1629번 곱셈 문제: www.acmicpc.net/problem/1629 내코드 이 문제는 일단 brute force 방식으로 접근하면 O(n) 시간 복잡도로 풀수 있지만 이 경우에 시간 초과가 남 분할 정복 방식으로 풀어야하는 문제: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 간단하게 생각하면 a^b mod c를 풀어야 하는 문제 여기서 b=2k+1 일때 a^b = (a^k)^2xa이고 b=2k일때 a^b = (a^k)^2임을 생각해보자 예를 들어 2의 16제곱이면 brute force 방식은 16번 계산해줘야하지만 분할 정복을 하면 2의 8제곱한 결과를 제곱해주면 된다. 즉, 2의 8제곱은 2의 4제곱의 제곱이고, 2의 4제곱은 2의 제곱의 제..
[OS] 멀티스레딩 & 메모리 공간
[OS] 멀티스레딩 & 메모리 공간 멀티스레딩이란 하나의 프로세스를 다수의 스레드로 나눠서 작업을 실행하는 것 멀티스레딩 멀티스레딩이란 하나의 프로세스를 다수의 실행 단위인 스레드로 나눠서 작업을 실행하는 것을 말함 장점 메모리 공간과 시스템 자원 소모가 줄어듬 스레드 간의 통신에 별도의 자원을 이용하는 것이 아니라 전역 변수의 공간 또는 동적으로 할당된 공간인 heap 영역을 이용하여 데이터를 주고 받아 멀티 프로세스(프로세스 여러개로 실행하는 방식, 멀티 프로세스의 경우 IPC와 같은 통신 사용)보다 훨씬 간단 (이전 글: 스레드는 레지스터와 stack만 독립적으로 갖고 나머지는 공유한다) 스레드의 context switch(실행하던 스레드를 멈추고 다른 스레드를 실행 시키면서 실행에 필요한 정보들을..
[Algorithm] 재귀 (Recursion)
[Algorithm] 재귀 (Recursion) 재귀(recursion) 란? 재귀로 문제를 푼다는 것은 하나의 함수에서 다시 자기 자신을 호출해 문제를 해결해 나가는 것을 말한다. 자기 자신을 다시 호출할 때, 보통 인자를 더 작게 해주며 호출해주며 인자 or 함수값이 일정 값 이하일때 반복을 종료 해줄 수 있도록 조건을 추가해 준다. 이런 하위 문제를 base condition이라고도 한다. 예를 들어 아래와 같다. #include using namespace std; void recursion(int arg) { cout