본문 바로가기

대딩192

[프로그래머스 lv2] 방문 길이 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 좌표를 이동시키면서, 중복되지 않은 이동경로의 개수를 세는 문제이다. 이동하며 특정 루트를 방문했었는지 확인하는 과정이 필요하다. 방문했던 좌표 (x, y)를 저장하는 vector나 set을 쓸 수도 있지만, 주어진 좌표평면의 크기가 작아 bool 타입의 배열을 선언하면 간단히 처리할 수 있다. 주어진 문자열을 순회하면서, U, D, L, R에 따라 새로운 이동 좌표를 구한다. 만약, 새 좌표가 주어진 범위를 넘어간다면 이를 무시하라고 했으므로 아무런 일도 없었던 것처럼 넘어간다. 새 좌표가 주어진 범위 내에 있을 때 좌표를 이동하고, 해당 경로를 방문한적이 없다면 cnt 변수를 1 증가시킨다. 모든 문자를 순회한 후 최종 cnt 값을 리턴하면 정답이.. 2022. 8. 10.
[프로그래머스 lv2] 기능개발 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문제의 조건을 요약하면, 1. 각 기능들은 완성도가 100%가 되었을 떄 배포된다. 2. 배포는 주어진 순서대로 이루어진다. 즉, 뒤의 기능이 먼저 완성되었다 할지라도 앞에 있는 기능이 배포되지 않았다면 먼저 배포될 수 없다. 가장 먼저, 각 기능에 대하여 배포까지 며칠이 남았는지 구할 수 있다. progresses[i]가 현재까지 진행된 완성도, speeds[i]가 하루에 채워지는 완성도이므로 (100-progress[i])를 speeds[i]로 나눈 몫의 올림값이 배포까지 필요한 일수가 된다. n을 k로 나눈 결과를 올림한 값은 (n+k-1)/k로 구한다. (외워두면 가끔 유용하게 쓸 수 있다!) 따라서, 각 기능에 대하여 배포까지 남은 날은 (1.. 2022. 8. 9.
[프로그래머스 lv2] 124나라의 숫자 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 모든 숫자를 (1, 2, 4) 3가지 수로 나타낸다고 했으므로 3진법과 관련있음을 유추할 수 있다. 10진법을 3진법으로 나타내기 위해서는 3으로 계속 나누어가며 나머지가 무엇인지 살펴야 한다. 나머지가 1일 떄는 1, 나머지가 2일 때는 2, 나머지가 0일 떄는 4를 문자열에 붙이고 맨 마지막에 이를 뒤집어 결과를 리턴한다. 단 주의할 것은, 3으로 나누어떨어질 경우(나머지가 0일 경우) 몫을 1 감소시키고 나머지를 3 증가시켜 3을 4로 변환시키자. 예를 들어, 10을 1, 2, 4 숫자로 변환할 때 10 / 3 = 몫 3 ... 나머지 1 => 1 3 / 3 = 몫 1 ... 나머지 0 => 몫에 1을 뺴주면 나머지는 3이 된다. 나머지 3을 4.. 2022. 8. 9.
[프로그래머스 lv2] 멀쩡한 사각형 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문제를 처음 딱 보고, 아 뭔가 규칙을 찾는 문제구나 하는 생각이 든다. h*w의 직사각형에서 대각선이 지나가는 칸 수를 알 수 있다면 전체 블럭의 개수에서 해당 칸의 개수를 빼 정답을 구할 수 있다. 그렇다면 대각선이 지나가는 칸 수는 어떻게 알 수 있을까? 예제로 나온 8*12의 직사각형을 보면, 일정한 패턴이 반복되는 것을 알 수 있다. 8과 12의 최대공약수 4로 가로와 세로를 각각 나누어보면 2*3의 직사각형이 나온다. 이 직사각형은 전체 직사각형 안에 최대공약수(4개) 만큼 반복된다. 이 작은 직사각형을 보면, 대각선이 지나는 칸의 개수는 2+3-1 = 4개가 된다. 즉, W*H 의 전체 직사각형이 있고, W와 H의 최대공약수를 g라 할 때.. 2022. 8. 9.
메모리 관리_Demand paging, Page replacement algorithms(FCFS, LRU, LRU Approximation(NRU), LFU, MFU) Paging Paging은 logical memory를 physical memory로 mapping 하는 여러 방법 중 하나입니다. Logical memory를 같은 크기의 page로, physical memory를 page와 같은 크기의 frame으로 나눈 뒤 page를 특정 frame에 할당하여 이를 page table에 기록합니다. Page table의 크기는 매우 커서 main memory에 저장 해야 하는데, CPU가 명령을 수행할 때마다 메모리에 접근하기에는 overhead가 크므로 TLB(일종의 캐시)에 자주 참조될 것으로 예상되는 page에 대한 정보를 저장하여 사용합니다. (Paging에 대한 자세한 설명을 읽어보고 싶으신 분은 여기로) Demand Paging 그렇다면, 프로그램이 로드.. 2022. 6. 21.
메모리 관리_Mapping(Contiguous allocation, Paging, Segmentation) 지난 포스팅에서는 logical memory를 physical memory에 할당하고 physical address를 확정하는 시점에 대해 다루었습니다. Compile time, Load time, Execution time 중에서 현재 사용되고 있는 방식은 Execution time 입니다. 프로세스의 코드 라인이 실행이 될 때 logical memory를 physical memory에 할당하고, 이를 참조할 때마다 MMU가 logical address를 physical address로 변환합니다. 그렇다면, logical memory를 physical memory에 어떻게 할당할 수 있을까요? 본 포스팅에서는 logical memory와 physical memory를 mapping 하는 방법에 대해 .. 2022. 6. 16.
메모리 관리_Address binding(Compile time, Load time, Execution time) Symbolic Address / Logical Address / Physical Address 우리는 프로그램을 작성할 때, 변수명과 함수명을 통해 값에 접근합니다. 값에 접근하기 위해 사용되는 변수와 함수 이름을 Symbolic Address 라고 부릅니다. 이렇게 작성한 프로그램은 컴파일이 되면서 독자적인 공간을 가지게 됩니다. 이를 logical memory라고 하며, 가상의 공간이므로 virtual memory 라고도 불립니다. 일반적으로 logical memory는 0번지 부터 시작하여 상대적 주소로 표현되고, CPU는 logical address를 참조하여 명령을 내리게 됩니다. 프로그램과 데이터는 실제 메모리 주소에 올라가야 합니다. logical memory의 코드와 데이터들은 실제 메모.. 2022. 6. 16.
Deadlock_Deadlock의 발생 조건 Deadlock 여러 개의 프로세스들이 공유자원에 동시에 접근할 때 비의도적으로 공유자원의 값이 변경되거나 오염될 수 있는데, 이러한 상태를 Race condition 이라고 부릅니다. Race condition을 방지하기 위해 동기화(Synchronization)를 사용하고, 어떠한 프로세스가 Critical section을 사용하고 있다면 다른 프로세스는 사용하지 못하도록 차단합니다. 그런데, 동기화를 사용하다보면 Deadlock의 상황이 발생될 수 있습니다. Deadlock 이란, 2개 이상의 프로세스들이 서로의 작업이 끝나기만을 기다려 결과적으로 모든 프로세스가 무한히 대기하게 되는 현상을 말합니다. 예를 들어 상황을 설명해보겠습니다. Semaphore 변수 S = 1 과 Q = 1이 존재하고, .. 2022. 6. 15.
동기화_High level Synchronizations Tools(Semaphore, Mutex, Monitor) High level mechanism 여러개의 프로세스(스레드)들이 공유자원에 동시에 접근하여 비의도적으로 공유자원의 값이 변경되거나 오염되는 상황을 race condition이라 합니다. Synchronization(동기화)란, 이러한 상황을 방지하기 위한 기법으로 하나의 프로세스가 Critical section을 실행하고 있을 때 다른 프로세스는 접근하지 못하도록 막는 개념입니다. (자세한 설명은 여기에) 본 포스팅에서는 User level에서 사용되는 동기화 기법들에 대해 소개합니다. Semaphore Semaphore는 공유자원에 동시에 접근할 수 있는 프로세스의 수를 정수형 변수로 나타냅니다. 이를 공유 자원에 접근할 수 있는 티켓이라고 생각하면 이해하기 쉽습니다. Semaphore 에서는 프로.. 2022. 6. 15.
동기화_Low Level Synchronization Tools(Spin Lock, Disabling interrupts) Synchronization Tools 여러개의 프로세스(스레드)들이 공유자원에 동시에 접근하여 비의도적으로 공유자원의 값이 변경되거나 오염되는 상태를 Race Condition이라고 합니다. 이를 해결하는 방법론이 Synchronization(동기화)이며, 어떠한 프로세스가 critical section을 실행하고 있을 때 다른 프로세스는 critical section에 접근할 수 없도록 하는 개념입니다. (자세한 설명은 여기에) 이번 포스팅에서는 OS level에서 사용하는 동기화 방법들에 대해 소개합니다. Low Level mechanism Spin Lock(+ Hardware atomic instructions) Critical Section을 보호하는 가장 기본적인 방법은, critical se.. 2022. 6. 14.

티스토리툴바