프로그래머스
-
[프로그래머스] 가장 먼 노드알고리즘/프로그래머스 2021. 8. 16. 15:20
문제 링크 풀이 bfs를 이용하면 방문하는 노드가 최단거리가 됩니다. 거리를 기록하는 배열인 dist를 이용해 지금 노드에서 다음 노드를 방문할 때 +1을 해서 값을 갱신합니다. 코드 #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector vec(n + 1, vector(n + 1)); size_t size = edge.size(); for (int i = 0; i < size; ++i) { auto n1 = edge[i][0]; auto n2 = edge[i][1]; vec[n1][n2] = 1; vec[n2][n1] = 1; } vector visited(n + 1, ..
-
[프로그래머스] 추석 트래픽알고리즘/프로그래머스 2021. 8. 15. 19:58
문제 링크 풀이 문자열로 되어 있는 시간 로그를 실제 숫자로 변경해 주어진 로그에서 시작 시간을 구해, 시작 시간과 완료 시간을 pair로 가지는 벡터에 넣습니다. 1초 동안 최대로 걸려 있는 처리량을 구하는 것이 답입니다. 문제를 보면 lines 배열은 응답완료시간을 오름차순 정렬이 되어 있습니다. 이 말은 n번째 로그의 완료시간은 무조건 n-1보다 늦다는 이야기가 됩니다. 즉 시작 시간을 기준하면 됩니다. 예제 2를 보면 첫 번째 로그가 끝나는 시점과 두 번째 로그의 시작 지점이 1초에 같이 속하기 때문에, 최대 2개가 카운트 된다는 것이 힌트입니다. 1초라는 간격을 적용했을 때 카운트할 수 있는 최대값을 찾는 것이 목표입니다. 즉 n번째의 시작 시간이 n-1번째의 완료시간 + 999ms보다 같거나 ..
-
[프로그래머스] 예상 대진표알고리즘/프로그래머스 2021. 8. 5. 14:32
문제 링크 풀이 시드 개념으로 접근했습니다. {1,2}는 1번 시드, {3,4}는 2번 시드. 라운드가 진행되면서 주어진 a, b가 같은 시드가 되면 됩니다. 1번 시드에 속하면 계속 1번 시드이지만 다른 시드에 속한 사람은 배정된 번호가 라운드마다 바뀌므로 새롭게 시드가 배정됩니다. 배정 번호로 시드를 구하면 됩니다. 짝수 번호는 나누는 수가 자신의 시드이지만 홀수인 자는 올림 연산을 해야 합니다. 7번은 4번 시드이니까요. 처음에 ceil()을 사용했지만 비트 연산을 활용하는 방법도 있습니다. 코드 #include int solution(int n, int a, int b) { int answer = 0; while (a != b) { a = ceil(a / 2.f); b = ceil(b / 2.f)..
-
[프로그래머스] 올바른 괄호알고리즘/프로그래머스 2021. 8. 5. 14:16
문제 링크 풀이 예외 케이스를 생각해봐야 하는 문제 같습니다. 처음에 작성한 코드는 괄호 짝을 다 맞추고 나서 뒤에 붙는 괄호를 걸러낼 수가 없었습니다. "()()(" 이런 경우가 해당됩니다. 그래서 조건문을 조금 변경했습니다. 코드 #include #include using namespace std; bool solution(string s) { if (s[0] == ')') return false; stack b; for (int i = 0; i < s.size(); ++i) { char c = s[i]; if (!b.empty() && c == ')') b.pop(); else b.push(c); } return b.empty() ? true : false; }
-
[프로그래머스] 조이스틱알고리즘/프로그래머스 2021. 7. 28. 16:42
문제 링크 풀이 마냥 쉬운 문제는 아닌 것 같습니다. 조이스틱의 위아래 조작의 최소 횟수를 찾는 건 쉽습니다. A->Z 방향, Z->A 방향으로의 조작 중 더 작은 값을 취하면 됩니다. 문제는 좌우 조작입니다. 몇 번 직접 사례를 찾아가면서 규칙을 찾아야 합니다. ABABAAA의 경우를 보면 오른쪽으로 세 번만 움직이면 됩니다. 이것이 최소 횟수입니다. AABAAAAAB의 경우에는 먼저 왼쪽으로 한 번 갔다가 오른쪽으로 세 번 움직이는 게 최소 횟수입니다. ABAAAAABA의 경우는 일단 오른쪽으로 한 번 갔다가 왼쪽으로 세 번 가는 방법이 최소 횟수입니다. 이 세 가지의 경우 중 가장 작은 값을 구하면 되는 것입니다. 여기서 한 가지 공식을 만들 수 있습니다. 원점 기준 A가 아닌 위치를 찾고 나서, ..
-
[프로그래머스] 튜플알고리즘/프로그래머스 2021. 7. 27. 02:12
문제 링크 풀이 주어진 문자열을 적절히 파싱하여 정수형으로 변환했습니다. 그다음에는 규칙을 찾았는데요. 주어진 집합에서 사이즈가 1인 경우를 찾는 게 가장 먼저 진행돼야 합니다. 이것이 튜플의 첫 번째 원소에요. 그다음에 사이즈가 2인 것을 찾으면 다른 하나가 두 번째 원소가 되죠. 이를 위해 집합을 정수형으로 바꾼 벡터를 사이즈의 오름차순으로 정렬을 한 뒤에 차례대로 찾아서 넣어줬습니다. answer 변수에 넣은 값을 판별하기 위해 vector을 이용했습니다. vector은 부분 특수화가 되어 있습니다. true/false 정보만 담으면 되므로 bitwise로 최적화됐습니다. s의 길이가 최대 백 만이므로 여유있게 vector 변수의 공간을 백 만개로 잡았습니다. 정적으로 선언하면 백 만 바이트(1mb..
-
[프로그래머스] 단체사진 찍기알고리즘/프로그래머스 2021. 7. 25. 16:37
문제 링크 접근법 멤버의 모든 조합을 체크하면 되기 때문에 C++의 경우 next_permutation이라는 함수를 이용하면 비교적 쉽게 풀 수 있습니다. 주어지는 조건을 '모두' 충족하는 경우의 수를 찾는 문제입니다. next_permutation 함수를 쓰기 위해선 오름차순이 되어 있어야 합니다. 그래서 멤버의 문자열을 만들어 줄 때 오름차순으로 정렬되도록 초기화했습니다. 조금 편하게 풀고자 전역 변수 두 개를 뒀습니다. max, min, abs 같은 간단한 함수는 라이브러리를 쓰지 않는 편입니다. 물론 복잡한 기능의 경우에는 라이브러리를 사용하는 것이 당연히 낫습니다. 가령 min, max를 구할 때 C++11부터는 파라미터에 initializer_list가 있어서 중괄호를 이용해서 세 개 이상의 ..
-
[프로그래머스] 게임 맵 최단거리알고리즘/프로그래머스 2021. 7. 21. 14:46
문제 링크 풀이법 큐를 이용해서 풀 수 있습니다. 이 문제는 깊이 우선이 아니라 너비 우선 방식으로 풀어야 합니다. 너비 우선 방식을 이용하면 모든 노드에 도달하는 카운트가 최소가 됩니다. 현재 노드에서 동서남북 방향을 훑어 보고 처음 방문한 곳이면서 노드 값이 1인 경우에 탐색을 합니다. 이 과정이 순차적으로 이루어지며, 탐색을 선점하게 되면 해당 위치의 카운트는 갱신되지 않게 코드를 작성할 것이기 때문입니다. 프로그래머스에선 이차원 배열을 vector로 선언했을 때 속도가 더 빠르게 나오는 걸 확인했습니다. 하지만 효율성 테스트와 비주얼 스튜디오 2019에선 당연히 정적으로 선언한 경우가 더 빨랐습니다. 예제 1번 기준으로는 0.2ms 차이가 났고, 효율성 테스트에서는 0.05~0.07ms로 작은 차..