기록공간

이진수로 변환하는 방법만 안다면 어렵지 않게 풀 수 있는 문제이다. 이진수 변환에는 쉬프트 연산을 사용하였다. 예를 들어 9를 이진수로 변환한다고 하자. 9의 이진수는 1001이다. (전체 이진수 크기 - 1) 부터 시작한다. 9(1001) >> 3 --> 0001 (1번째 위치의 이진수 값은 1이다) 9(1001) >> 2 --> 0010 (2번째 위치의 이진수 값은 0이다) 다음과 같이, 쉬프트 연산()을 하면 맨 왼쪽 자리에 구하고자 하는 위치의 이진수의 값을 알 수 있게된다. 이 작업을 쉬프트 연산을 0으로 할때까지 반복하면 전체 이진수 값을 구할 수 있게된다. 여기서는 맵의 크기로 n이 주어지기 때문에 n크기에 맞는 이진수 값을 만들어야 한다. 그렇기 때문에 n - 1부터 0까지 반복하며 쉬프트..

크레인으로 옮겨진 인형들은 바구니에 차곡차곡 쌓이기 때문에 스택을 이용하면 편하다. 접근 방법은 다음과 같다. 우선 크레인을 특정 인덱스에 있는 인형을 집어야 한다. 특정 인덱스인 그 열에서 첫번째 행부터 마지막 행까지 반복하며 인덱스 접근으로 인형을 찾는다. 인형이 있는경우 반복문을 빠져나오고 그 자리를 빈공간으로 만들어 준다. 집어넣기 전에, 바구니에 마지막으로 넣은 인형이 현재 크레인이 집은 인형과 같다면 두 인형은 터뜨려져야 하므로 바구니에서 인형을 꺼내고 크레인이 집은 인형은 바구니에 넣지 않는다. 바구니가 비어 있거나 바구니에 마지막으로 넣은 인형과 다르면 크레인이 집은 인형을 바구니에 넣는다. 코드는 다음과 같다. #include #include // STL 스택 사용을 위함 using na..

우선 구조체 INFO를 선언한다. INFO 구조체에는 고유번호와 재생 횟수 값이 저장된다. 이제 해시 컨테이너를 통해 해당 장르의 INFO들을 기록한다. (key값 : 장르, value값 : INFO들을 담은 vector 컨테이너) 이때 2번 기준인 "장르 내에서 많이 재생된 노래를 먼저 수록합니다."를 만족시키기 위해 value값을 재생 횟수 기준으로 내림차순 정렬을 해준다. 그리고 3번 기준 "장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다." 만족 시키기 위해 정렬시 재생 횟수가 같은 경우 고유번호 기준으로 오름차순 정렬을 한다. 이제 1번 기준인 "속한 노래가 많이 재생된 장르를 수록합니다."를 만족하기 위해 총 재생 횟수 기준으로 정렬을 진행해야 한다. 이 ..

옷을 입는 경우의 수를 도출하는데에 애를 많이 먹은 문제였다;; 우선 해시를 이용하여 해당 종류의 맞는 옷의 갯수를 컨테이너에 기록한다. (key값은 옷의 종류 이름, value값은 그 종류의 옷 개수) 옷의 이름은 이 문제를 해결하는데에 전혀 필요가 없다. 옷의 종류별 갯수를 알았으니 이제 이 스파이가 위장할 옷을 입는 경우의 수를 구할 차례이다. 예를들어 얼굴 종류의 옷 5개와 하의 종류의 옷 4개가 있다고 하자. 만약 이 옷을 두가지 모두 입어야 한다면 5 * 4 = 20가지 조합이 나온다. 하지만 옷을 안입는 경우도 있으므로 안입은 경우를 추가해줘야 한다. 그래서 조합 수 는 (5 + 1) * (4 + 1) = 30가지이다. 하지만 30은 정답이 아니다! 위 조건에서 "스파이는 하루에 최소 한 개..

접두어가 있는지 없는지만 찾으면 되는 문제였다. 우선 phone_book을 순회를 돌며 모든 원소에 대해 비교를 진행한다. 검사가 끝난 원소는 string를 key값으로, string의 사이즈를 value값으로 하는 unordered_map인 d라는 컨테이너에 들어간다. phone_book의 원소는 이 컨테이너 d 안에 있는 원소들과 비교를 한다. 접두어를 찾는 것이므로, 비교하는 값 둘 중 사이즈가 더 작은 값을 기준으로 부분 문자열 비교를 진행한다. 만약 검사하는 부분이 같으면 false를 리턴한다. 코드는 다음과 같다. #include #include #include #include using namespace std; bool solution(vector phone_book) { bool answ..

우선 해결방법은 컨테이너에 마라톤 선수의 이름과 정수형 변수를 보관하는 것이다. 참가한 마라톤 선수를 원소로 집어넣을때 정수형 변수를 1 증가시킨다. 그 작업이 끝나면, 이제 완주한 마라톤 선수를 컨테이너에서 찾아 그 원소의 정수형 변수를 1 감소시킨다. 그리고 컨테이너를 순회돌며 정수형 변수가 0이 아닌 마라톤 선수 이름이 정답이 된다. STL의 컨테이너 형식으로 어떤 것을 쓸건지에 따라서 알고리즘의 시간 복잡도가 바뀌게 된다. 우선 첫번째는 STL의 map 컨테이너를 사용하는 것이다. map 컨테이너는 이진 탐색 트리(binary search tree)의 원리를 이용한 컨테이너로 항상 원소의 키값을 기준으로 정렬된 상태를 유지한다. 트리 검색 특성상 원소의 갯수가 N개 일때 검색 시간 복잡도는 O(l..

왼쪽은 빛을 비추지 않은 구이고 오른쪽은 빛을 비춘 구이다. 왼쪽 그림은 상당히 평평해 보인다. 사실 구가 아니라 그냥 2차원 원처럼 보인다. 반면 오른쪽의 구는 실제로 3차원의 구처럼 보인다. 이처럼 조명과 음영은 물체의 입체감과 부피감을 묘사하는 데 큰 도움이 된다. 실제로, 인간의 시각적인 인식은 빛과 물체 재질의 상호작용에 의존한다. 따라서 실사적인 묘사 부분의 상당 부분이 물리적으로 정확한 조명 표현이다. 일반적으로 조명 표현이 정확할수록 계산 비용이 높아진다. 따라서 사실감과 처리 속도의 밸런스를 맞추는 것이 중요하다. 예를 들어 영화 같은 경우는 게임에 비해 더 사실적인 조명 표현이 가능하다. 왜냐하면 영화에서의 그래픽은 실시간 처리가 아닌 미리 렌더링을 계산하기 때문이다. 따라서 한 프레임..

수년 동안 병행성 관련 오류 해결을 위해 연구자들이 엄청난 시간과 노력을 들였다. 대부분의 초기 연구는 교착 상태(deadlock)에 초점이 맞추어져 있었다. 최근 연구들은 다른 종류의 병행성 버그들을 다루고 있다. 실제 프로그램에서 발견된 사례를 중심으로 어떤 오류가 있는지를 살펴보고자 한다. 오류의 종류 첫 번째 질문은 이것이다 : 복잡한 병행 프로그램에서 발생하는 병행성 오류들은 어떤 것들이 있는가? 이 질문에 대한 답을 구하는 것은 어렵지만, 다행히 다른 사람들이 이미 비슷한 작업을 해놓았다. 실제 상황에서 어떤 종류의 오류들이 발생하는지 이해하기 위해 그들은 많이 사용되는 병행 프로그램들을 자세히 분석하였다. 이 연구는 대표적인 오픈소스 프로그램 4개에 집중하였다. 유명한 DBMS(데이터 베이스..