본문 바로가기

Contents168

백준 17404 RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 그냥 RGB거리랑 다른 점은 첫 번째랑 마지막 번째도 이어져 있다고 가정하는 것인데 내가 알고리즘 초보라 푸는데 시간이 너무 오래 걸렸다... 메모리는 굳이 1000개짜리를 사용하지 않아도 풀이가 가능하다. 그냥 RGB 거리를 풀었다고 생각하고 추가된 아이디어는, 메모이제이션으로 사용한 배열 rgb[a][b] 은 첫 번째 집은 a 로 칠하고, 마지막 번째 집은 b 로 .. 2021. 6. 24.
SW마에스트로 12기 면접, 최종합격 후기 및 연수 중간 후기 사실 이전에 작성한 글이 있긴 하다. 이 글 내용과 중복된 내용은 있을 수도 있고, 약간의 내용을 추가했다. 나도 SW마에스트로 면접을 준비할 때 많은 블로그를 참고했기에(찾을 수 있는 11기 면접 글은 모두 살펴본 것 같다.), 내 글도 누군가에게 도움이 되길 바라며 준비 방법에 대한 조언도 남겨보려 한다. 미리 말하지만 조언을 맹신하지는 마라. 13기부터는 250명을 뽑을 예정이라고 한다. 확정인 것은 아니고, 말해도 되는지도 모르겠지만 기사로도 떴으니 되겠지... 전형은 다음과 같다. 서류 -> 1차 코딩테스트 -> 2차 코딩테스트 -> 최종면접 -> 합격 서류 서류에 장난 치지만 않으면 합격한다. 서류에는 기술스택과 자기소개서를 작성할 수 있다. 서류 합격에는 내용이 중요하지 않지만 장난치면 떨어.. 2021. 6. 20.
[운영체제] SSD (Solid State Drive) SSD 는 SamSung Drive 의 약자이다. 구라다. Solid State Drive 인데, HDD 가 Disk 여서 끝에 D 를 Disk 로 오해하는 경우가 있다. 하지만 SSD 에는 disk 가 없다. HDD 의 기계적인 부품들 때문에 고장이 잦고, 느리고, 전력 소모가 심하다. 모바일 환경에선 배터리 소모율에도 영향이 있기 때문에 부적합하다. 하드디스크의 물리적인 부분을 제거하면 전력 문제와 속도 문제를 해결할 수 있지 않을까? 이것이 SSD 이다. NOR flash memory : ram 처럼 random access 가 가능하다. 주로 bios 에 사용된다. NAND flash memory : disk 처럼 block 단위로 접근할 수 있다. HDD 대신 사용된다. SSD 에는 Disk 가.. 2021. 6. 7.
[운영체제] RAID 하드디스크는 비용대비 사용할 수 있는 용량이 크다. 하지만 물리적인 부분을 많이 사용하는 HDD 특성상 고장의 빈도수가 높고 느리다는 단점을 갖고 있다. RAID 는 HDD 여러 개를 같이 사용하여 이런 문제를 해결한다. 또한 RAID 를 사용하는 프로그래머는 여러 개의 HDD 를 이용하고 있다는 것을 몰라야 한다. RAID : Redundant Array of Inexpensive Disks 의 약자이다. 근데 요즘엔 비싸서 inexpensive 대신 independent 로 사용하기도 한다. 서버에서는 표준적으로 사용한다. RAID Controller : cpu, sw, memory 를 갖고 있는 HW 이다. RAID 자체가 운영체제를 갖고 있는 하나의 시스템이다. RAID level 에 따라 con.. 2021. 6. 7.
[운영체제] 하드디스크 (Hard Disk) platter : HDD 에는 여러 장(보통 4장)의 디스크가 있는데 한 장의 디스크를 platter 라고 부른다. 데이터를 저장한다. head : platter 에 있는 데이터를 읽는다. arm : head 를 연결하는 팔 역할이다. 마찬가지로 여러 개가 있다. platter 마다 두 개씩 있는데, 병렬로 읽고 쓸 수 있다. surface : 하나의 platter 는 양면 다 활용이 가능하다. 한 면을 surface 라 부른다. sector : HDD 의 기본 단위이다. 보통 페이지와 같은 크기인 4kb 를 많이 쓴다. track : surface 내에서 반지름이 다른 동심원, 바깥에 있는 track 일수록 더 많은 데이터를 저장할 수 있다. 그리고 더 빠르게 읽고 쓸 수 있다. platter 가 도는.. 2021. 6. 7.
[운영체제] Free space malloc 과 free 는 명시적 메모리 할당과 해제이고, 할당할 수 있는 크기에 제한이 없기 때문에 다음 두 가지 문제를 해결해야 한다. 1. 페이지 단위로 할당하지 않을 경우 메모리 관리가 힘들다. -> 외부 단편화 문제 2. free 의 인자로 포인터밖에 들어가지 않는데, 몇 바이트인지 알 수 있는 방법이 필요하다. malloc 과 free 를 구현하기 위해서는 사용중인 메모리의 상태와 크기를 유지해야 한다. 성능도 O(n) 가 걸리는 방법이 아닌 O(1) 에 처리할 수 있는 방법이 존재한다. heap fragmentation : 일반적으로 외부 단편화를 말한다. free list : 힙 영역에서 사용가능한 영역에 대한 list 를 나타내는 자료구조 연결 리스트를 만들어서 빈 공간에 대한 정보를 .. 2021. 6. 7.
[운영체제] 데드락 (Deadlock) atomicity violation : 연속적으로 수행되어야 하는 연산이 연속적으로 수행되지 못 한 경우 → mutex 로 해결 order violation : 어떤 순서를 가정했는데 그 순서로 실행되지 않는 경우 void init() { mThread = PR_CreateThread(mMain, ...); } mMain() { ... } mMain 보다 mThread 초기화가 먼저 이루어질 거라 가정한 코드이다. 데드락 thread 1 은 lock A 을 잡았고 lock B 를 대기중인 상태, thread 2 는 lock B 를 잡았고 lock A 를 대기중인 상태에서 데드락이 발생한다. 데드락이 발생하려면 다음과 같은 조건을 만족해야 한다. mutual exclusion : 공유 자원에 대한 액세스 .. 2021. 6. 2.
[운영체제] 세마포어 (Semaphore) 제목은 세마포어로 바뀌었지만 병행성과 관련 있는 내용이다. semaphores : mutex 의 일반화된 형태 semaphores 는 edsger dijkstra 라는 사람이 발명했고 mutex 나 condition variable 을 구현할 수 있다. 오 다익스트라 아저씨 여기도 나오네? 기존의 lock 이 하나라면 semaphore 는 락 할 수 있는 횟수를 정수로 나타낸다. 다음과 같은 연산이 있다. p (sem_wait() ) : - 연산, wait 와 유사하다. (n sleep) - lock - n 이 음수라면 기다려야 한다. 음수 절대값은 대기 중인 스레드의 개수가 된다. v (sem_post() ) : + 연산, signal 연산과 유사하다. (n > 0 -> wake one u.. 2021. 6. 1.
[운영체제] 병행성 3 (Concurrency) : Condition Variable lock 만으로는 어떤 조건을 만족해야 수행할 수 있는 스레드를 구현할 수 없다. 락과 함께 어떤 조건을 만족하는 지 확인하는 데, 그 조건, 스레드의 수행을 제어하는데 사용하는 것이 condition variable 이다. condition variable 은 락과 함께 사용된다. condition variable : 스레드들이 공유자원을 향해서 경재하고 있을 때 스레드 수행을 제어하기 위해 사용하는 일종의 시그널이다. bouned buffer 만약에 어떤 buffer 가 있고 이 버퍼의 크기가 특정 이상이 되면 그 때 읽는 로직을 작성하고자 한다면 어떻게 구현해야 하겠는가? 버퍼의 크기가 특정 크기가 될 때까지 스레드는 기다린다. 조건을 만족하게 되면 시그널로 알려 준다. 처음에 버퍼를 읽어들일 때 .. 2021. 5. 31.

티스토리툴바