기록공간

간단하게 풀어봤지만 역시 예상대로 대다수 케이스가 실패로 떴다. 푼 방법은 비용 순서로 오름차순 정렬하여, 순서대로 다리를 설치하면서 방문하는 섬을 기록해 놓는다. 다리를 설치할 위치의 두 섬이 이미 모두 다리가 있는 경우에는 설치하지 않는다. 그렇게 모든 섬을 방문할 때까지 반복한다. 하지만 이 방법이 잘못된 이유는 다음 같은 케이스 때문이다. 다음과 같이 5개의 섬이 있고 [[0,1,1],[0,2,2],[1,2,5],[2,3,8],[3,4,1]] 인 경우를 생각해보자. 우선 비용으로 오름차순을 하면 [[0,1,1],[3,4,1],[0,2,2],[1,2,5],[2,3,8]]이 된다. 내가 했던 방식으로 순서대로 3번째까지 다리를 이어보면 다음과 같이 된다. 이렇게 모든 섬을 방문했다고 판단하고 다리 설..

그리디 알고리즘을 사용하는 문제였다. 차들이 공통적으로 사용할 수 있는 카메라의 수를 부분적으로 찾아야 한다. 그러기 위해서는 우선 차량의 진입 지점을 오름차순으로 정렬해줘야 한다. 어떠한 경우더라도 단속 카메라는 1개 이상은 설치되어야 하므로 answer는 1부터 시작한다. 정렬한 상태에서 자동차들의 진입 진출 범위는 다음과 같다. 처음 진입하는 차량은 15까지 진출을 하기 때문에 적어도 15에는 카메라가 배치되어야 한다. (이 카메라는 최초로 배치해야 할 카메라이다. 즉, answer의 1에 대한 카메라를 배치하는 과정인 것이다.) 하지만 다음 차량이 -13까지 진출하기 때문에 최소의 카메라 배치를 만족하기 위해 카메라의 위치는 -13에 위치하게 된다. 이렇게 하면 첫번째, 두 번째 차량이 진입 진출..

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

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

이진수로 변환하는 방법을 알고 있다면 어렵지 않게 풀 수 있는 문제였다. 이진수 변환 방법은 이전 문제를 풀 때 사용했던 방법을 그대로 사용하였다. 자세한 내용은 다음 링크를 참고하자. 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을 하면 해당 위치에서의 정사각형 넓이가 된다. 그 값을 현재 ..