기록공간

모든 경우를 검사하면서 조건에 알맞은 답을 골라주면 되는 문제였다. 노란 격자가 한개라도 들어가기 위해서는 카펫의 크기를 3 x 3부터 시작해야 한다. 조건 중 "카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다."를 주목하자. 이와 같은 정보들은 세로 길이는 절대 가로 길이를 넘어갈 수 없으므로 검사하는 범위를 줄이는데 도움을 줄 수 있다. 접근 방법은 다음과 같다. 이중 반복문을 사용한다. i x j 라고 가정했을때 i를 3부터 크게잡아 brown + yellow까지 반복한다. j는 3부터 i까지 반복한다. yellow의 크기는 brown의 가로, 세로 길이값이 2씩 더 작으므로 yellow 격자의 갯수는 (i - 2) * (j - 2)이다. (i - 2) * (i - 2)가 yellow..

우선 처음 생각해 볼 수 있는 방법은 반복문을 사용하여 모든 위치를 검사하며 그 위치로부터 정사각형이 되는 범위를 찾는 것이다. 하지만 이 방법의 시간 복잡도는 O(n^3)로 만약 행과 열의 크기가 1000이라면 최악의 경우 1000 * 1000 * 1000 = 1000000000으로 효율성 테스트를 통과할 수 없게 된다. 이런 이유로 동적 계획법을 활용하여야 한다. 동적 계획법의 사용 방법은 다음과 같다. 우선 표의 정보를 모두 동적 테이블에 담아 놓는다. 그리고 다음 과정을 반복한다. 동적 테이블 위치는 [1, 1] 부터 시작한다. 이 위치에서 왼쪽, 위쪽, 왼쪽 위쪽(대각선) 값들 중 가장 작은 값 min을 찾는다. 그리고 min + 1을 하면 해당 위치에서의 정사각형 넓이가 된다. 그 값을 현재 ..

우선 두 가지 조건이 존재한다는 것을 간접적으로 알려주고 있다. 답은 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부터 전체 문자열의 절반 크기까지 반복한다. 전체 문자열의 절반까지만 구하는 ..