알고리즘
-
[프로그래머스] 조이스틱알고리즘/프로그래머스 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로 작은 차..
-
[프로그래머스] 프린터알고리즘/프로그래머스 2021. 7. 19. 14:42
문제 링크 풀이 이 문제는 크게 두 가지 방법으로 풀 수 있는 것 같습니다. 효율성이나 성능을 고려했을 때 반복문을 줄이는 게 좋다고 생각합니다. 이 관점에서, 우선순위 큐를 사용하면 알고리즘 헤더의 max_element를 매번 사용하지 않아도 되기 때문에 빠르고 효율이 좋습니다. pair을 연습해볼 수도 있어서 좋습니다. 코드1 #include #include #include using namespace std; int solution(vector priorities, int location) { int answer = 1; queue index_value_q; priority_queue pq; for (int i = 0; i < priorities.size(); ++i) { index_value_q...
-
[프로그래머스] 오픈 채팅방알고리즘/프로그래머스 2021. 7. 19. 11:51
문제 링크 풀이 C++에는 문자열을 구분자로 친절하게 잘라주는 함수가 없습니다. 대신에 string 클래스에 find 함수를 이용해서 만들 수 있습니다. 여기에서는 공백이 구분자인데, 어떤 구분자가 주어져도 자를 는 split 함수를 외워두면 다른 문제 풀이에도 도움 될 것 같습니다. 문제의 답은 변경이 모두 적용된 최종 상태를 가지고 시스템 메시지를 출력하는 것입니다. Enter, Leave 메시지는 출력하지만 Change는 출력하지 않습니다. 사용자 아이디를 키로 하고 닉네임을 값으로 해 최종 상태를 반영했습닙다. 이를 위해 map을 사용했습니다. unordered_map을 사용해도 됩니다.. map은 균형 이진 트리인 red-black tree로, unordered_map은 해쉬로 구현됐습니다. 데..
-
[프로그래머스] 문자열 압축알고리즘/프로그래머스 2021. 7. 12. 22:10
문제 링크 문자열을 잘 자르기만 하면 됩니다. 하나씩 자를 때는 하나씩 비교하면 되고 두 개씩 자를 때는 두 칸씩 이동하면서 비교해야 합니다. 문자열의 길이가 8인데 자르는 갯수가 3일 때는 나누어 떨어지지 않습니다. 이럴 때는 나머지를 꼭 뒤에 붙여줘야 하겠습니다. string의 += 연산자는 append()를 감싸는 형태입니다. 코드 #include #include using namespace std; int min(int a, int b) { return a < b ? a : b; } int solution(string s) { int answer = s.size(); for (int i = 1; i
-
[백준] 1로 만들기알고리즘/백준 2021. 7. 11. 17:33
문제 링크 풀이 실제로는 10분도 안 돼서 풀었는데, 사소한 실수 하나 사소하지 않은 결과를 만들어 해결까지 거의 30분을 넘게 썼습니다. 처음부터 실수하지 않게 주의하는 것이 중요한 것 같습니다. vs에서는 정적 배열을 백만 개 만들면 경고를 주면서, 프로그램 실행이 되지 않습니다. 동적 배열을 직접 만들거나 벡터를 쓰면 됩니다. 백준에서는 편의성을 위해 스택 공간을 많이 잡아둔 것 같습니다. 정적 배열 백만 개를 만들어도 괜찮네요. 이 문제는 전형적인 DP 문제입니다. d[i]는 i를 1로 만들기 위한 최소 연산 횟수입니다. d[i]는 d[i-1], d[i/2], d[i/3] 중에서 가장 작은 값에 1을 더해주면 되는데, 문제에 나와 있듯이 i가 2의 배수면 2로 나누고, 3의 배수면 3으로 나누는 ..