기록공간

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 처음 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 시간 복잡도는 3중 반복문으로 O(n^3)이다. 코드는 다음과 같다. 이외로 간단하다. for(int k = 0; k d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j]; } } } 선행 조건으로 배열에는 두 정점 간..

간단하게 풀어봤지만 역시 예상대로 대다수 케이스가 실패로 떴다. 푼 방법은 비용 순서로 오름차순 정렬하여, 순서대로 다리를 설치하면서 방문하는 섬을 기록해 놓는다. 다리를 설치할 위치의 두 섬이 이미 모두 다리가 있는 경우에는 설치하지 않는다. 그렇게 모든 섬을 방문할 때까지 반복한다. 하지만 이 방법이 잘못된 이유는 다음 같은 케이스 때문이다. 다음과 같이 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에 위치하게 된다. 이렇게 하면 첫번째, 두 번째 차량이 진입 진출..

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

그리디 알고리즘 문제였다. 위, 아래로 조작하여 알파뱃을 바꾸는 것은 어렵지 않았지만, 개인적으로 왼쪽, 오른쪽 조작을 구하는 것이 좀 어려웠다. 예를 들어 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..