기록공간

크러스컬 알고리즘은 그리디 알고리즘을 이용하여 가중치가 존재하는 그래프를 최소의 비용으로 연결하는 최적의 해답을 구하는 알고리즘이다. MST(최소 비용 신장 트리)가 최소 비용의 간선으로 구성되어 있고, 사이클을 포함하지 않은 조건에서 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 크러스컬 알고리즘의 동작 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. -> 가장 낮은 가중치를 먼저 선택한다. -> 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST의 집합에 추가한다. 동작과정을 그림으로 표현하면 다음과 같다. 사이클 생성 여부를 항상 체크하는 것이 중요하다. 추가할 새로운 간선의 양끝 정점이 이미 MS..

그리디 알고리즘 문제였다. 위, 아래로 조작하여 알파뱃을 바꾸는 것은 어렵지 않았지만, 개인적으로 왼쪽, 오른쪽 조작을 구하는 것이 좀 어려웠다. 예를 들어 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을 하면 해당 위치에서의 정사각형 넓이가 된다. 그 값을 현재 ..