기록공간

우선 두 가지 조건이 존재한다는 것을 간접적으로 알려주고 있다. 답은 0이 포함되지 않는다. (1~9까지 숫자) 답은 서로 중복되는 숫자를 가질 수 없다. (서로 다른 임의의 숫자) 해결 방법은 다음과 같다. 입력되는 값은 서로 다른 숫자이므로 이를 만족하는 최솟값 123부터 최댓값 987까지 숫자를 문자열 n으로 바꾼다. (n 문자열은 야구 게임의 정답 후보이다) 만약 n 문자열에 0이 포함되어 있거나 서로 중복되는 경우 위 조건을 만족하지 않은 정답 후보이므로 다음 값으로 넘어간다. 질문을 검사하며 n과 대조해본다. 만약 서로 같은 위치에 같은 문자열이 있다면 스트라이크 값을 증가시킨다. 위치는 다르지만 같은 문자열이 존재하는 경우 볼 값을 증가 시킨다. 3의 작업을 모두 마치고 질문에서 주어진 스트..

대기목록의 문서들을 순서대로 담을 큐와 가장 중요도가 높은 문서를 알 수 있도록 해주는 최대 힙이 필요한 문제였다. 풀이과정을 정리해보면 다음과 같다. 문서 순서와 중요도를 기록할 큐 q와 중요도가 큰 순서대로 보여줄 최대 힙 pq를 선언한다. 주어진 priorities 정보를 q와 pq에 담는다. q의 값을 꺼내 pq top에 있는 값과 비교한다. 만약 같다면 pq를 pop 한다. (문서 순서가 location과 같으면 요청한 문서이므로 알고리즘을 종료한다.) 만약 다르다면 q에서 꺼낸 값을 다시 집어넣는다. 3, 4 작업을 q가 빌 때까지 반복한다. 5번 작업이 끝난 후 pq가 pop 한 횟수가 구하는 값이 된다. 코드는 다음과 같다. #include #include using namespace st..

스택을 이용하는 문제이다. 스택에 전 시간들을 기록해놓으면, 현재 시간의 가격과 스택에 쌓인 시간들의 가격을 비교해서 정답을 유추할 수 있다. 과정을 나눠보면 다음과 같다. 지간 값을 담을 스택 s를 만든다. 그리고 정답을 담을 벡터 v를 만든다. 시간을 1초부터 입력받은 가격 크기(총 시간에 해당)초 만큼 루프를 돌면서, s에 현재 시간값을 넣어준다. 만약 s가 비어 있지 않고 s의 top에 있던 시간 (바로 이전 시간)의 가격이 현재 시간 가격보다 큰 경우, (현재 시간 - top에 있던 시간)값을 v[top에 있던 시간]에 기록하고 s를 pop한다. 이 값은 가격이 떨어지는 기간이다. 5번 작업을 3번 조건이 만족하지 않을때까지 반복한다. (이전 시간들의 가격이 현재 시간 가격보다 작은 경우에는 정..

힙의 특성을 이용하면 원활하게 풀 수 있는 문제이다. '스코빌 지수가 가장 낮은 음식'에 주목하자. 이는 최소 힙을 이용한다면 쉽게 가져올 수 있다. 힙에 대해 더 자세하게 알고 싶다면 다음 링크를 참고하길 바란다. https://lipcoder.tistory.com/entry/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queue?category=804356 우선순위 큐 (Priority Queue) 컴퓨터에서는 우선순위 개념이 종종 필요할 때가 있다. 예를 들면, 운영 시스템에서 시스템 프로세스는 응용 프로세스보다 더 높은 우선순위를 갖는다. 따라서 자료구조에서도 이러한 우선순위 lipcoder.tistory.com 힙은 STL에서 std::pri..

그저 알고리즘 요구에 맞게 재귀적으로 코딩하면 되는 문제이다. 우선 위에서 제시한 알고리즘을 다음과 같이 나눠보았다. 1 -> 재귀 함수 반환조건 설정 2 -> 받은 문자열을 u, v로 쪼개기 3, 4 -> 올바른 괄호인지, 아닌지 검사 3-1 -> 올바른 괄호일 경우 해야 할 작업 4-1 ~ 4-5 -> 올바르지 않은 괄호일 경우 해야 할 작업 이제 다음 목록들을 하나씩 살펴보도록 하겠다. 재귀함수 반환조건 설정 재귀 함수를 작성할 때 주의할 점은 어떤 상황에서도 재귀 함수가 종료될 수 있도록 return 조건을 설정하는 것이다. 이 작업을 해주지 않는다면 재귀 함수는 계속해서 똑같은 함수를 타고 들어가 무한루프에 빠지게 될 것이다. 이 조건은 알고리즘 1번("입력이 빈 문자열인 경우, 빈 문자열을 반..

특정 알고리즘 유형을 필요로 하는 문제는 아니었다. 문제에서 요구하는 답은 압축된 문자열의 길이 이므로 직접 압축된 문자열을 만들어볼 필요는 없었다. 우선 압축할 문자열의 길이를 기록한다. 쪼갤 수 있는 횟수만큼 쪼갠다. 만약 쪼갠 문자열이 그 이후에 쪼갤 문자열과 같다면 카운트를 증가시킨다. 만약 서로 다르다면 지금까지 카운트 값을 검사했던 (기록한 카운트 값 * 측정한 문자열 크기)만큼 기록한 문자열 길이에서 빼주고 압축된 정보 크기만큼 더해준다. aaaaabbbbacccc(a 5번 중복) -> bbbbacccc(검사했던 알파뱃 삭제) -> 5abbbbacccc(압축된 정보 추가) ->... 이 작업을 쪼갤 수 있는 횟수 1부터 전체 문자열의 절반 크기까지 반복한다. 전체 문자열의 절반까지만 구하는 ..

영역을 구하기 위해서는 BFS(너비 우선 탐색)를 사용해야 한다. https://lipcoder.tistory.com/entry/%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-BFS?category=843242 너비 우선 탐색 (BFS) 너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 �� lipcoder.tistory.com 특정 위치에서 시작하는 경우 현재 BFS를 이용해 양 방향으로 갈 수 없을 때까지 검사한다. 갈 수 없는 조건을 다음과 같다. -> 해당 색과 다른 색인 경우 ..

스킬 트리가 스킬 순서의 조건을 지키는지를 검사하는 문제였다. 스킬 순서가 CBD인 경우 스킬 트리에서 B 스킬을 찍기 위해서는 C가 먼저 나와야 한다. CBD는 순서만 지키면 되지 스킬 트리에서 해당 스킬들이 안 나와도 상관없다. 처음부터 검사를 하는 경우 어떻게 접근해야 하는지 살펴보자. 우선 첫 번째 스킬 나올때 까지 스킬 트리의 스킬들을 차례대로 검사한다. 만약 해당 스킬이 나왔다면 두 번째 스킬로 넘어가 나올 때까지 검사하면 된다. 스킬 트리에서 스킬이 안 나오더라도 상관없으므로 올바른 스킬 트리이다. 하지만, 해당 스킬 이후 번째 스킬이 스킬 트리에서 먼저 나온다면, 그것은 불가능한 스킬 트리이다. 코드는 다음과 같다. #include #include using namespace std; in..