Level 3. 기지국 설치 전파가 닿지 않는 구간들을 구해, 각 구간을 (2w + 1) 크기씩 채워주면(나누면) 된다. 기지국의 번호가 정렬된 상태로 주어지므로, 앞에서부터 구간을 구할 수 있다. #include #include #include using namespace std; int solution(int n, vector stations, int w) { int answer = 0; int start = 1; vector section; for (int st : stations) { section.emplace_back(st - w - start); start = st + w + 1; } if (start

Level 3. 순위 플로이드-워셜(Floyd-Warshall) 알고리즘 그래프 탐색 알고리즘 - 노드의 개수가 100개 미만으로 적은 것이 특징이다. 시간 복잡도가 3중 for문을 사용하는 O(n³)이기 때문이다. - 특정 점들이 아닌 모든 점들 사이의 최단 거리를 구한다. - 음수 가중치가 있어도 사용할 수 있지만, 음수 사이클은 존재해선 안 된다. 1. 가중치가 정해지지 않은 간선들은 ∞로 초기화한다. ∞를 무작정 INT_MAX로 설정하면, 더할 때 음수가 돼버리므로 주의해야 한다. 2. 자기 자신의 비용은 0으로 초기화한다. 3. K (임의의 중간 점) → S (시작점) → E (끝점) 순으로 3중 for문을 구성하여 최단 거리를 갱신한다. [프로그래머스] 순위(Floyd-Warshall Algo..

Level 2. 조이스틱 좌우로 조이스틱을 조작할 때 더 짧은 거리를 거리를 구하는 함수와 상하로 조이스틱을 조작할 때의 더 적은 비용을 구하는 함수를 만들었다. 인덱스 계산이 좀 번거롭긴 했다. 그리디로 풀었더니 오답처리 되었다. // 이 풀이는 틀린 풀이다. #include #include using namespace std; int horizontal(int pos, string& current, string& name) { int l = 0, r = 0; size_t len = name.length(); while (current[(pos + l + len) % len] == name[(pos + l + len) % len]) if (len

Level 2. 리코쳇 로봇 최단 거리를 구해야 하는 전형적인 BFS 문제다. 로봇을 이동시키는 것 외에 크게 번거로운 것은 없었고, 범위 검사는 unsigned 형을 사용하면 더 간편하게 할 수 있다. #include #include #include using namespace std; struct Point { unsigned r; unsigned c; int dist; }; enum class DIR { UP, DOWN, LEFT, RIGHT }; Point moveTo(Point& p, DIR dir, vector& board) { size_t R = board.size(), C = board.front().size(); Point pM(p); int dr, dc; switch (dir) { ca..

Level 2. 시소 짝꿍 모든 사람 중 2명을 뽑는 조합을 구하고, 각 조합에서 나온 모든 토크를 set에 넣어 중복이 있는지 확인한다. 하지만, 시간 초과 발생.. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include using namespace std; vector get_comb(int n, int r) { vector result; vector comb(n, 0); fill_n(comb.rbegin(), r, 1); do result.emplace_back(comb); while (next_permutation(comb.begin(), comb.end())); return result; } long long solution(vector weigh..

Level 2. 호텔 대실 겹치는 구간의 최댓값을 구하는 문제다. 가장 간단한 방법은 배열을 만들어 1씩 더한 후, 가장 큰 값을 고르는 것이다. #include #include #include #include using namespace std; int time_to_sec(string time) { return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3)); } int solution(vector book_time) { int answer = 0; vector v(time_to_sec("23:59") - time_to_sec("00:00"), 0); for (vector& time : book_time) { auto first = v.begin() + t..