기록공간

그리디 알고리즘 문제였다. 위, 아래로 조작하여 알파뱃을 바꾸는 것은 어렵지 않았지만, 개인적으로 왼쪽, 오른쪽 조작을 구하는 것이 좀 어려웠다. 예를 들어 JERAAN을 입력을 받으면 위아래 조작은 위와 같이 해야 최소한의 조작이 된다. 이 조작 횟수를 따로 담아 놓는다. 이제 처음 위치부터 위, 아래로 조작한 횟수를 더해준다. 더해준 값은 0으로 갱신한다. (0인 경우는 그 위치에 알맞는 알파벳으로 조작을 완료했다는 뜻이다.) 그리고 현재 위치에서 왼쪽(초록색) 또는 오른쪽(주황색) 방향으로 갈 경우 0이 아닐 때까지의 거리를 측정한다. 이 거리를 측정하는 이유는 다음과 같다. 그림과 같은 경우 오른쪽 방향으로 조작하면 6번을 해야 하지만, 왼쪽 방향으로 조작하면 3번만 해주면 된다. 즉 위아래 조작..

부분 단계적으로 해결하는 그리디 알고리즘 문제였다. 여벌 체육복을 가져온 학생이 도난 당할 수 있다는 점에 주목하자. 이 경우에는 여벌 체육복을 가져왔다고 해도 다른 학생에게 체육복을 빌려줄 수 없다. 접근 방법은 다음과 같다. 도난 당한 학생을 담은 벡터에서 여벌 체육복을 가져온 학생들을 뺀다. (도난 당했지만 체육 수업을 들을 수 있으므로) 마찬가지로 잃어버린 학생을 담은 벡터에서 위 학생을 뺀다. 남은 잃어버린 학생들은 체육 수업을 들을 수 없으므로, 이 학생들 앞뒤로 여벌의 체육복이 있는 학생이 존재하는지 검사한다. 만약 있다면 여벌을 가진 학생은 이제 체육복을 빌려줬으므로 벡터에서 빼준다. 답은 (학생 수) - (잃어버린 학생 수) + (잃어버렸지만 여벌이 있는 학생 수) + (빌려준 수) 가 ..

클래스 하나를 인스턴스 별로 다른 객체형으로 표현할 수 있게 만드어, 새로운 '클래스들'을 유연하게 만들 수 있게 한다. 의도 개발 중인 판타지 RPG에서, 포악한 몬스터 무리를 구현해야 한다고 해보자. 몬스터는 체력, 공격력, 그래픽 리소스, 사운드 등 다양한 속성이 있지만 여기서는 체력과 공격 속성만을 고려한다. 모든 몬스터에는 체력 값이 있다. 체력은 최대 체력에서 시작해 피해를 입을 때마다 조금씩 줄어든다. 몬스터에게는 공격 문구(attack string) 속성도 있다. 몬스터가 영웅을 공격할 때, 이 공격 문구는 유저에게 표시된다. 기획자는 '용'이나 '트롤'같이 몬스터 종족(breed)을 다양하게 만들고 싶어 한다. 각 종족은 몬스터의 특징을 나타내고, 던전에는 같은 종족 몬스터가 여러 마리 ..

이진수로 변환하는 방법을 알고 있다면 어렵지 않게 풀 수 있는 문제였다. 이진수 변환 방법은 이전 문제를 풀 때 사용했던 방법을 그대로 사용하였다. 자세한 내용은 다음 링크를 참고하자. https://lipcoder.tistory.com/entry/%EB%B9%84%EB%B0%80%EC%A7%80%EB%8F%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4?category=843241 비밀지도 (프로그래머스) 이진수로 변환하는 방법만 안다면 어렵지 않게 풀 수 있는 문제이다. 이진수 변환에는 쉬프트 연산을 사용하였다. 예를 들어 9를 이진수로 변환한다고 하자. 9의 이진수는 1001이다. (전체 이진수 lipcoder.tistory.com 풀이 과정을..

스택을 알고 있다면 어렵지 않게 풀 수 있는 문제였다. 스택을 이용하여 입력받은 괄호정보를 순회하며 '('를 만나면 그 값은 스택에 집어넣는다. 만약 ')'를 만나면 스택에서 '(' 하나를 꺼낸다. 모든 작업을 마치고 만약 스택이 비어 있다면 그것은 올바른 괄호이므로 true를 반환하면 된다. 하지만 주의할 점이 있는데 처음부터 ')'이 나오는 경우이다. 이 경우 '('를 스택에서 꺼내고 싶어도 스택이 비어 있어 꺼낼 수 없으므로 바로 false를 반환하면 된다. 코드는 다음과 같다. #include #include using namespace std; bool solution(string s) { bool answer = false; stack v; for(const auto& iter : s) { i..

모든 경우를 검사하면서 조건에 알맞은 답을 골라주면 되는 문제였다. 노란 격자가 한개라도 들어가기 위해서는 카펫의 크기를 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의 작업을 모두 마치고 질문에서 주어진 스트..