자료구조 & 알고리즘/백준(Baekjoon)

[백준]2343(파이썬) - 기타레슨

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이 문제는 정말 어이없는 실수로 꽤나 시간을 쏟았던 문제입니다.. 해설을 하면서 말씀드리도록 하죠. 처음 봤을 때 생각은 '뭔가 기준점이 있어야 하고 그 기준점은 조건에 따라 달라질 수 있다.... 그렇다면 이분 탐색이겠구나'였습니다. 이분 탐색에서 가장 핵심은 이분탐색풀이에서의 mid 값을 뭐로 설정하느냐? 라고 저번 이분탐색 포스팅에서 언급한적이 있는데요, 이번에도 무엇을 mid로 둘 것이냐를 생각하..

2022.01.10 게시됨

CS & Network/운영체제(OS) & 컴퓨터구조

[운영체제(OS)] 동기화(Synchronization) 와 임계구역 문제(Critical Section Problem) - 2

0. 들어가면서 저번 시간에는 운영체제에서의 동기화가 무엇인지 살펴보았고, 임계 구역 문제가 무엇인지 알아봤습니다. 이번 시간에는 임계구역을 어떻게 관리하는지, 동기화 문제를 어떻게 해결하는지 방법들을 알아보려고 합니다. 1. 임계구역 문제 SW 해결 방법들(Software-only-solution) 1 - 1. 먼저 프로세스가 두 개일 때의 해결 방법에 대해서 알아보겠습니다. //Process P1 do { while(turn!=i); //critical section turn = j //remainder section } 위의 코드를 살펴보겠습니다. turn이라는 공유 변수는 어떤 프로세스/쓰레드에 자원이 할당될지 넣어놓는 변수입니다. turn 변수가 자기 자신인 i를 가리키기 전까지 critical..

2022.01.10 게시됨

CS & Network/운영체제(OS) & 컴퓨터구조

[운영체제(OS)] 동기화(Synchronization) 와 임계구역 문제(Critical Section Problem) - 1

0. 동기화 문제란? 저번에 공부했듯이 컴퓨터 메모리에는 동시에 여러 프로세스가 존재하는데, 존재하는 프로세스들이 하나의 공유 메모리나 또 다른 프로세스에 접근할 때는 매우 신중해야 합니다. 저번에도 한 번 언급했었던 내용인데, 두 개의 프로세스 A, B 가 shared memory를 이용해서 데이터를 주고받는 과정에서 A 가 쓰면 그다음 B가 읽어 가야 하는데 A가 이미 쓴 메모리 영역인지, 이제 써야 할 메모리 영역인지 알 수가 없습니다. 때문에 A가 B에 '나 여기 다 썼다'라고 알려줘야 B가 읽어 갈 수 있죠. 프로세스 동기화의 핵심은 여러 프로세스가 공유하는 자원들의 일관성을 유지하는 것입니다. 하나의 공유자원에 여러 프로세스들이 동시에 접근할 때, 프로세스들의 순서를 정해서 동기화가 잘 이루어..

2022.01.09 게시됨

자료구조 & 알고리즘/백준(Baekjoon)

[백준]18405(파이썬) - 경쟁적 전염

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 이 문제는 94퍼센트 정답률 까지는 10분 안에 풀었지만 나머지 반례를 찾지 못해서 꽤 시간이 걸린 문제입니다.. 나머지 6퍼센트가 어느 부분에서 잘못 되었는지는 파악이 되었습니다. 바로 1초가 지난 후 시험관의 상태를 체크할 때, 어떻게 체크할 것이냐의 문제였던 것 같은데요, 제가 처음 풀었던 풀이에서 어디가 잘못되었는지 아시는 분은 댓글 부탁드립니다ㅠㅠ 결국에는 ..

2022.01.08 게시됨