구름을 채우다

문제 보기 이 문제는 알고리즘 분류는 되어있지 않지만, 시뮬레이션 문제라고 생각한다. 갈수록 삼성의 SW 역량 테스트가 점점 어려워지는 게 느껴진다. 개인적으로 문제를 읽자마자 스택/큐의 개념이 떠올랐지만, 막상 파이썬으로 구현하니 스택/큐를 쓸 일이 없었다. 또한 C/C++의 포인터를 쓰고 싶었지만, 파이썬에는 포인터의 개념이 없기 때문에 해결법을 구상하는데 꽤나 오랜 시간이 걸렸다. 문제를 풀기 전, 중요한 변수가 3개 있다. board_info: 체스판의 색깔 정보를 담고있는 변수 board: 체스판 위의 체스말 정보를 담고 있는 변수 chess_pieces: 체스말 리스트 (각 체스 말의 행, 열과 방향을 담고 있다.) 이를 가지고 문제를 해결하였다. 문제를 푼 로직은 다음과 같다. 체스 말이 다..

Bounded-Buffer 문제 (유한버퍼 문제) 소비자와 생산자가 유한 개의 버퍼 자원을 공유하는 상황에서, 다음 문제를 해결하고자 한다. 소비자와 생산자가 버퍼에 상호 배타적으로 접근 소비자는 버퍼에 원소가 한 개라도 있으면 버퍼를 소비해야 하고, 생산자는 버퍼에 원소가 없으면 원소를 생산해야 한다. 위의 문제를 해결하기 위한 조건은 다음과 같다. 생산자가 먼저 실행된 적이 있어야 하고, 생산자의 실행 횟수가 소비자보다 많아야 한다. 위 문제를 해결하기 위해 사용하는 변수는 다음 세 가지이다. 세마포어 mutex(= 1): 생산자와 소비자의 상호배제를 위한 변수 세마포어 empty(= n): 비어있는 버퍼의 개수를 나타내는 변수 세마포어 full(= 0): 버퍼가 차있는 개수를 나타내는 변수 Read..

Bounded-Buffer 문제 (유한 버퍼 문제) 생산자(Producer)는 데이터를 생성하고, 소비자(Consumer)는 데이터를 소비한다. in과 out의 값으로는 버퍼에 있는 데이터의 양을 알 수가 없다. (위의 그림 참조) 따라서 counter 변수를 사용한다. 하지만 counter 변수는 생산자와 소비자가 동시에 접근하므로 Race condition이 발생한다. 따라서 동기화가 필요하다. Race condition 여러 프로세스(또는 스레드)가 공유자원에 동시에 접근할 때, 접근 순서에 따라 결과가 달라질 수 있는 상황 Synchronizaiton (동기화) Multi-threaded application 스레드는 프로세스 안에서 메모리를 공유한다. (스택은 별개로 가진다.) 데이터 손상을 막..

이번에는 우리가 OpenStack에 contribute하기 전에 Gerrit을 어떻게 사용해야 하는지 알아볼 것입니다. Gerrit 흐름도 위의 그림은 Gerrit을 통한 코드 리뷰의 흐름을 나타낸 것입니다. 위의 그림을 간단하게 설명하자면 다음과 같습니다. 코드를 수정하고자 하는 프로젝트를 로컬 환경으로 clone합니다. 로컬 환경에서 수정하고자 하는 버그에 대해서 브랜치를 생성합니다. 변경사항에 대해 저장하고, 유닛 테스트를 진행한 다음, git commit을 실행합니다. (가장 첫 번째 커밋만 git commit으로 로컬 환경에 변경사항을 저장합니다.) git review를 통해 Gerrit 리뷰시스템에 변경사항을 제출합니다. 자동 테스트 툴을 통해, 빌드 및 테스트를 진행하고, 제출한 코드를 리뷰..

문제 보기 이 문제는 힙 문제이다. 힙 자료구조를 사용해서 우선순위 큐를 구현하는 것이 문제의 의도이다. 문제를 푼 로직은 다음과 같다. 주어진 스코빌 리스트를 힙으로 변경한다. (7~8번째 줄) 문제에서 주어진 방식대로 음식 2개를 섞어 새로운 음식을 만들고, 이 때의 스코빌 지수를 추가한다. (11~15번째 줄) 모든 음식의 스코빌 지수가 K보다 높아야하므로, 힙의 루트가 K보다 작을 동안(= 힙의 최소값이 K보다 커지면 모든 음식의 스코빌 지수가 K보다 크다) 반복한다. (9~10번째 줄) 더이상 섞을 음식이 없고, 스코빌 지수가 K보다 낮다면 -1을 반환한다. (17~18번째 줄) import heapq def solution(scoville, K): answer = 0 # make scovill..

문제 보기 이 문제는 스택/큐 문제이다. 주식이 시간이 지남에 따라 가격이 떨어지지 않은 시간이 얼마인지 구하는 문제이다. 현재 시간에서 미래에 가격이 떨어지는 시간까지 탐색을 해야하기 때문에 O(n^2)이 나올거라고 생각했다. 문제를 푼 로직은 다음과 같다. 각 시간에서의 주식 가격에 대해서 (5~6번째 줄) 주식 가격이 떨어지지 않는 시간을 구한다. (8~15번째 줄) 각 시점에서의 주식 가격이 떨어지지 않는 시간을 업데이트한다. (17번째 줄) 여기서 눈여겨 볼 점은, 11~15번째 줄이다. 먼저 시간부터 센 다음, 만약 주식 가격이 떨어지면 break를 통해 반복문을 벗어난다. 이는 예제 입력을 보면 알 수 있다. 주식 가격이 상승을 하던 하락을 하던 일단 1초는 지나가기 때문에 시간을 먼저 세는..

문제 보기 이 문제는 스택/큐 문제이다. 문제를 해결하는데 스택이 사용되긴 했지만, 오히려 개념은 DP에 가까운 느낌이다. 문자열을 하나씩 읽을 때마다, 레이저를 만나게 되면 잘린 막대기가 몇 개인지 판단하였다. 문제를 푼 로직은 다음과 같다. 레이저는 "()"로 구분되므로, 더 쉬운 이해를 위해서 다른 문자 하나로 치환한다. (나의 경우 '.'로 치환했다.) 문자열을 읽으면서 '('를 만나면 막대기를 현재에서 한 개 더 올린다는 뜻이므로, '('를 만날 때마다 스택에 추가하고, 쇠막대기의 개수를 한 개 더한다. (7~9번째 줄) 문자열을 읽으면서 ')'를 만나면 젤 위의 막대기가 끝이 났다는 뜻이다. 그러므로 스택에 추가한 '('를 한 개 뺀다. (10~11번째 줄) '.'를 만나면 (=레이저를 만나면..