Computer Sci.

오늘은 백준 1300번 문제를 풀어 보려고 한다. https://www.acmicpc.net/problem/1300 이 문제는 이분 탐색을 사용하여 푸는 문제이다. 이분 탐색을 알고, 약간의 아이디어만 생각해 낼 수 있으면 풀 수 있는 무난한 난이도의 문제인 것으로 보인다. 이분 탐색은 정렬이 되어 있는 데이터에 대해서 순차적으로 값을 찾는 방법이 아닌 탐색 범위를 절반씩 줄여 나가면서 찾아가는 탐색 알고리즘이다. 해당 범위의 중앙 값을 찾고 찾는 값과 비교하여, 찾는 값보다 중앙 값이 크면 두 범위 중 작은 범위에서 탐색을 이어나가고, 찾는 값보다 중앙 값이 작으면 반대로 큰 범위에서 탐색을 이어 나가는 방법이다. 순차 탐색은 최악의 경우 시간복잡도가 O(N)까지 나타난다. N = 1,000,000,0..

오늘 설명할 문제는 백준 10422번 문제이다. https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net 이 문제는 동적 프로그래밍을 사용해서 푸는 문제이다. 아이디어를 알고 나면 되게 쉽지만, ..

오늘 설명할 문제는 백준 2109번 순회 강연이다. https://www.acmicpc.net/problem/2109 2109번: 순회강연 문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 www.acmicpc.net 전형적인 그리디 알고리즘 문제로, 이 알고리즘에 대한 이해가 있다면 어렵지 않게 풀 수..

지난 포스팅에 이어서 메모리 관리에 대해서 이어서 설명해 보도록 한다. 페이지 테이블 관리 페이지 테이블 관리가 복잡한 이유는 시스템에 여러 개의 프로세스가 존재하고, 프로세스마다 페이지 테이블이 하나씩 있기 때문이다. 메모리 관리자는 특정 프로세스가 실행될 때 마다 해당 페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환하는 작업을 반복한다. 페이지 테이블은 메모리 관리자가 자주 사용하는 자료 구조이므로 필요시 빨리 접근할 수 있어야 한다. 따라서 페이지 테이블은 물리 메모리 영역 중 운영체제 영역의 일부에 모아놓는다. 페이지 테이블의 수가 늘어나거나 페이지 테이블의 크기가 늘어나면 운영체제 영역이 그만큼 늘어나 사용자 영역이 줄어든다. 물리 메모리의 크기가 작을 때는 프로세스만 스왑 영역으로 옮겨..

오늘 설명할 문제는 백준 16946번 문제이다. https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 단순한 BFS 문제로 접근했다가 여러번 틀리고 깨달음을 얻은 문제이다. 처음에는 N * M 격자점들에 대해서 하나하나 BFS로 돌면서 이동할 수 있는 ..

이번 포스팅에서는 메모리 관리에 대해서 정리해 보고자 한다. 참고로 내용이 많으므로 두 번에 나누어서 정리한다. 컴퓨터가 널리 보급되면서, 범용 컴퓨터 시스템의 목적은 CPU의 활용률을 극대화 하는 것으로 나아갔다. 사용자들에게 빠른 응답을 제공하기 위해서 보다 많은 프로그램을 메모리에 올려서 실행(multi-programming) 시키게 되었고, 여러 프로그램을 동시에 실행시키기 위한 스케줄링 기법이 등장하게 되었다. 이와 같이 여러 프로그램이 동시에 메모리에 적재되어 실행되면서, 메모리를 공유할 필요가 생겼다. 컴퓨터의 메모리는 한정되었는데, 실행하는 프로그램이 많아지면 메모리 요구량이 증가했기 때문이다. 컴퓨터에서 작동하는 응용 프로그램은 프로그래밍 언어로 만들며, 보통은 컴파일러를 사용하여 작성된..

오늘은 백준 1865번 웜홀 문제를 풀어보려고 한다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 이 문제는 개인적으로 정말 많이 틀리고 나서 해결했던 문제이다. 그래서 더욱 꼼꼼하게 문..

지난번 포스팅 동기화 Part1에 이어서 데드락과 동기화의 고전적 문제들에 대해서 정리를 해 보려고 한다. 데드락(교착상태, Deadlock) 데드락은 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 더이상 수행하지 않는 상태를 의미한다. 교착상태가 발생하는 조건은 여러가지가 있는데 아래와 같다. 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 따라서 배타적인 자원을 사용하면 교착 상태가 발생한다. 비선점(non-preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선..