# Foundation (88) # Foundation/백준풀이 백준 1439 풀이 및 해설 개요 어떤 문제들은 입력을 짧게 치환해도 상관없는 경우가 있습니다. 이 문제가 그러한 것 중의 하나이며, 이 문제를 쉽게 풀려면 연속된 구간을 압축해야 합니다. 특정 값이 연속되는 구간은 나중에 같이 뒤집혀져야 하므로, 각 구간을 대표값 하나로 축약할 수 있겠죠. 축약 전: 1100000011 축약 후: 101 직관적으로 풀기 입력형식 되새김하기 이제 우리는 숫자가 연속되는 경우를 생각할 필요가 없습니다. from을 to로 바꿔야 한다고 했을 때, 다음과 같이 간략화된 입력만 생각하면 되는 것입니다. from으로 시작하는 경우: from from-to from-to-from from-to-from-to ... ... to로 시작하는 경우: to to-from to-from-to to-from-to-fro.. 2020. 12. 3. 16:45 # Foundation/백준풀이 백준 2437 풀이 및 해설 개요 매우 복잡해보이는 문제가 그림으로 풀면 매우 단순하게 풀리는 경우는 그리 드문일이 아닙니다. 이 문제는 수학적 귀납법으로도 풀 수 있지만, 수직선을 사용하면 훨씬 직관적이고 쉽게 풀립니다. 핵심은 측정할 수 있는 무게의 구간을 끊기지 않게 확장시키는 것 입니다. 핵심 현재 닫힌구간 [1, 10]을 측정할 수 있는 상태에서 무게가 5인 무게추가 더 주어졌다면, 기존에 측정할 수 있었던 무게 + 5를 측정할 수 있으므로, 1부터 10까지 순회하면서 5를 더한값을 추가로 측정할 수 있습니다. 즉, 닫힌구간 [1+5, 10+5]를 추가로 측정할 수 있습니다. 그렇다면 닫힌구간 [1, 5]를 측정할 수 있는 상태에서 무게가 7인 무게추가 더 주어지면 어떻게 될까요? 닫힌구간 [1, 12]를 전부 커버할 수 .. 2020. 12. 2. 19:04 # Foundation/백준풀이 백준 2136 풀이 및 해설 개요 보자마자 팟 하고 떠오르지 않으면 매우 고생하는 문제입니다. 어느 문제나 그렇겠지만, 이러한 애드 혹 분류의 문제는 이런 경향이 더 심합니다. 핵심은 개미간 충돌을 고려하지 않는다입니다. 해설 충돌 무시하기 아래와 같이 충돌 직전의 두 개미를 생각해보겠습니다. 1초 뒤에 두 개미는 서로 충돌하여 개미의 진행방향이 다음과 같이 바뀔 것입니다. 여기서 개미가 아닌 화살표에 집중해볼까요? 화살표만 바라보았을 때, → 화살표는 ← 화살표가 있든 없든 상관없습니다. 항상 4에서 5로 이동함을 알 수 있습니다. 마찬가지로 ← 화살표도 → 화살표가 있든 없든 상관없이, 항상 5에서 4로 이동함을 확인할 수 있습니다. 위의 이유로, 각 화살표는 다른 화살표를 신경쓰지 않고 제 갈길만 가면 된다는 결론에 도달합니다.. 2020. 11. 28. 21:50 # Foundation/운영체제 운영체제 정리 🦖 ch09. 가상 메모리 논리적 메모리 개요 프로그램이 실행되기 위해서는 먼저 메모리에 적재되어야 했습니다. 가장 간단한 방법은 프로그램 전체를 메모리에 적재하는 것이지만, 프로그램의 크기가 물리 메모리보다 큰 경우에는 어떻게 메모리에 적재되어야 할까요? 가상 메모리 이러한 문제를 해결하기 위해 전체 중에서 사용할 부분만 적재하는 방식이 탄생했습니다. 프로그램이 필요한 전체 메모리를 논리적(가상적) 메모리로 바라보고, 이 중에서 현재 실행에 필요한 부분만 물리적 메모리에 옮겨다 놓는 식이죠. 이 방식을 사용하면 다음과 같은 장점을 얻을 수 있습니다. 메모리를 프로그램의 관점(논리적 관점)과 램의 관점(물리적 관점)으로 분리할 수 있다. 메인 메모리보다 큰 프로그램을 실행할 수 있다. 절대 실행되지 않는 코드는 적재되지 않는다. .. 2020. 11. 21. 00:52 # Foundation/운영체제 운영체제 정리 🦖 ch08. 메모리 관리 전략 기본 하드웨어 CPU가 직접적으로 접근할 수 있는 메모리는 CPU 레지스터와 RAM이 유일하며, 이외의 메모리는 CPU가 해당 메모리의 주소를 가져오는 것이 불가능합니다. 이 때 CPU 레지스터는 단일 클럭만에 연산이 가능한데 반해, RAM은 메모리 버스를 경유해야 하기 때문에 훨씬 많은 클럭이 소요되므로, 이 속도차이를 보완하고자 중간에 캐시 메모리를 둘 수 있습니다. 프로세스 메모리 프로세스 메모리 범위 각각의 프로세스는 자신만이 사용할 수있는(legal) 메모리 공간을 가지며, 운영체제는 각 프로세스가 합법적인 메모리 영역에만 접근할 수 있도록 강제해야 합니다. 따라서 현대 시스템은 기준 레지스터(BASE)와 상한 레지스터(LIMIT)를 두어 합법적인 메모리 영역을 표현하는데, 일반 프로세스는 [B.. 2020. 11. 19. 22:22 # Foundation/운영체제 운영체제 정리 🦖 ch07. 교착상태 교착상태 개요 이전 챕터인 프로세스 동기화을 떠올려보면 공유자원을 요청한 작업은 해당 공유자원이 자신에게 할당될 때 까지 대기하고 있음을 알 수 있습니다. 그러나 지금까지는 공유자원이 1개인 작업만을 이야기했지만, 공유자원이 2개 이상 필요한 작업의 경우에는 어떨까요? 이러한 경우에는 교착상태라는 특이한 문제가 생길 수 있습니다. 두 개의 작업이 각각 고유자원을 소지하고 있는 상태에서, 상대의 고유자원을 요청하고, 반대편이 그것을 내놓을때 까지 기다리는 상황이죠. 양쪽 모두 고유자원을 내놓을 생각이 없다면, 이 둘은 반대편이 고유자원을 내놓길 기다리면서 영원히 대기하게 됩니다. 이미지 출처 : 땔감툰 필요조건 교착상태가 발생하려면 아래의 조건을 모두 만족해야 합니다. 상호배제 : 각 공유자원은 하나의 작.. 2020. 11. 18. 18:53 # Foundation/운영체제 운영체제 정리 🦖 ch06. 프로세스 동기화 공유자원 문제 덮어씌우기 현대 시스템은 다중 처리기 시스템이므로 여러개의 작업이 동시에 실행될 수 있으며, 공유 메모리를 사용하여 작업들은 서로에게 영향을 주고받을 수 있습니다. 이러한 현대 시스템 작업의 특징을 병렬성과 협력성이라고 부릅니다. 만약 두 개의 작업이 하나의 공유 영역에 동시에 접근하면 어떤 일이 일어날까요? 아래와 같이 공유변수 v에 쓰기연산을 실행하는 쓰레드를 정의해보겠습니다. char v = 'X'; void assignToA(){ _sleep(1000); // 1초 대기 v = 'A'; } void assignToB(){ _sleep(0); // 0초 대기 v = 'B'; } int main() { thread a(assignToA); thread b(assignToB); a.joi.. 2020. 11. 17. 20:23 # Foundation/알고리즘 [코딩테스트 대비] 트라이(Trie) 자료구조 개요 접근법 Trie라는 용어 자체는 생소할 수 있지만, 알게 모르게 실생활에서도 사용한 적이 있을만큼 매우 간단한 개념입니다. 예를 들어, 영어사전에서 apple 이라는 단어를 찾고 싶다면, 앞에서부터 a - p - p - l - e 순서로 prefix를 조합하면서 찾아갈 수 있습니다. // 영어사전에서 apple를 찾고 싶다면... 앞에서 a를 찾는다. -> a 이어지는 p를 찾는다. -> ap 이어지는 p를 찾는다. -> app 이어지는 l를 찾는다. -> appl 이어지는 e를 찾는다. -> apple 위와 비슷하게 xx시 xx고등학교 xx학년 xx반에 소속된 학생정보를 찾고 싶다면, 앞에서부터 prefix를 조합하면서 차례대로 접근하면 됩니다. step 1) xx시 step 2) xx시 xx고등.. 2020. 9. 16. 19:37 이전 1 2 3 4 ··· 11 다음
