본문 바로가기

분류 전체보기

 (120)
[OS] 스레드의 동기화 기법 - 유저 모드 동기화/커널 모드 동기화 스레드는 메모리의 구조 중 스택 영역을 제외한 코드/데이터/힙 영역을 공유한다. 이 때 여러 스레드가 동시에 같은 자원에 접근하는 것을 막기 위해 동기화 기법을 취해야 한다. 스레드의 동기화 기법 실행 순서의 동기화 스레드의 실행 순서 정의, 이 순서에 반드시 따르도록 하는 것 한 순간에 하나의 스레드만 접근 메모리 접근에 대한 동기화 메모리 접근에 있어서 동시 접근 막는 것 실행 순서가 중요한 상황이 아닌 경우, 한 순간에 하나의 스레드에만 접근하면 되는 상황 동기화 기법의 두 가지 구분 유저 모드 동기화 커널의 힘을 빌리지 않는(커널 코드가 실행되지 않는) 동기화 기법 성능상의 이점, 기능상의 제한(라이브러리를 이용) 종류 크리티컬 섹션 기반 동기화 - 메모리 접근 동기화에 사용. 임계영역 객체(Ke..
[OS] 단편화(Fragmentation)란? 내부 단편화와 외부 단편화란? 단편화(Fragmentation) 주기억장치에 프로그램을 할당하고 반납하는 과정에서 발생하는 사용되지 않는 작은 조각 공간 주기억장치 상에서 빈번하게 기억장소가 할당되고 반납됨에 따라 기억장소들이 조각들로 나누어지는 현상 내부 단편화란? 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남아있는 공간 주기억장치 내 사용자 영역 > 실행 프로그램 외부 단편화란? 주기억장치 내 사용자 영역보다 실행 프로그램이 커서 프로그램이 할당될 수 없어 사용되지 않고 남아있는 공간 주기억장치 내 사용자 영역
[OS] 뮤텍스(Mutex)와 세마포어(Semaphore)란? 프로세스 간 메시지를 전송하거나, 공유메모리를 통해 공유된 자원에 여러 개의 프로세스가 동시에 접근하면 Critical Section 문제가 발생할 수 있다. 이를 해결하기 위해 데이터를 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 두는 동기화 방식을 취해야 한다. 동기화 도구에는 대표적으로 뮤텍스(Mutex)와 세마포어(Semaphore)가 있다. 이들은 모두 공유된 자원의 데이터를 여러 스레드/프로세스가 접근하는 것을 막는 역할을 한다. 뮤텍스와 세마포어에 대해 공부하기 전에, 용어 하나 알고 가자. 임계 영역(Critical Section) 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 블록 즉, 여러 프로세스가 동일 자원을 동시에 참조하..
[Algorithm] 백트래킹(Backtracking)이란? Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를 상태공간트리로 표현 DFS 방식으로 후보군 확인 상태공간트리 탐색하며 제약조건을 만족하지 않으면 해당 부분에서 파생될 수 있는 모든 경우의 수를 더이상 보지 않는다. 이후 해의 후보가 될 만한 곳을 바로 넘어가서 탐색을 이어간다. 이를 통해 체크해야 하는 조건의 수를 확연히 줄이므로 계산량을 줄일 수 있는 기법이다. Promising : 조건 검사..
[SWEA] 5658. 보물상자 비밀번호(Python) swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 18분 소요 삼성 SW역량테스트 모의 문제 중 가장 쉬운 난이도의 문제이다. 특별한 알고리즘 X 리스트 슬라이싱을 이용해 회전 처리 나온 값에 16진수 처리를 하면서 중복없이 리스트에 담아줌 내림차순 정렬 후 K번째 수 출력 파이썬 코드는 다음과 같다. T = int(input()) for tc in range(T): N, K = map(int, input().split()) A = list(input()) ..
[BOJ] 8911. 거북이(Python) / Simulation www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 실버2 문제라 그리 어렵지 않은 시뮬레이션 문제였다. 맵을 그릴 필요 없이 (0, 0) 위치에서 시작하여 문제에 주어진 조건 그대로 구현한다. L과 R의 경우는 방향만 바꿔준다. 이 때, 현재 방향을 각 경우별로 만들어놓은 방향 전환 리스트(dirL, dirR)를 참조하여 현 방향에 해당하는 인덱스로 바꾼다. F와 B의 경우는 현재 방향으로 한 칸 나아간다. 이 때, 이동한 위치를 min_r/c, max_r/c 최솟값과 ..
[BOJ] 1063. 킹(Python) / Simulation www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 무난한 수준의 시뮬레이션 문제였다. King의 위치와 Stone의 위치를 입력받은 정보대로 움직이며 최종 위치를 출력한다. 이동 정보는 파이썬 Dictionary 자료구조를 활용해 이동할 곳을 Masking해주었다. Input 받을 때 좌표를 다루기 쉬운 숫자 형태로 변환하는 것과 이동 처리 후 Output할 때 다시 문자 형태로 변환하는 것이 꽤 까다로웠다. 이 때, 파이썬의 ord() 함수와, chr() 함수를 사용해..
[BOJ] 9466. 텀 프로젝트(Python) / DFS www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 꽤 까다로웠던 DFS 문제였다. 각 학생이 함께 프로젝트 하고 싶은 사람들 지목하고 지목을 한 사람들끼리 사이클을 이루는지 여부를 파악하여 팀을 이루지 못한 학생들의 수를 계산해야 한다. DFS를 이용하여 1번 학생부터 n번 학생까지 방문표시하며 지목한 다음 학생의 번호를 차례대로 확인한다. 이 때, 사이클 리스트에 넣는데, 다음 숫자가 이 리스트에 있다면 사이클 이루는 경우이므로, 전체 학생의 수에서 사이클을 이루..

티스토리툴바