문제 풀이

[프로그래머스 lv2] N개의 최소공배수 (최대공약수, 최소공배수) [C++]

https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 처음엔 배열의 최댓값부터 1씩 증가하면서, 모든 원소와 최초로 나눠 떨어지는 수를 찾았다. 맞았지만, 데이터의 크기가 커지면 시간 초과가 날 수 있는 풀이였다. 다른 분들의 풀이를 보니, 최대공약수와 최소공배수를 구해서 풀었다. a와 b의 최소공배수를 구하는 것은 a와 b의 곱을 최대공약수로 나눈 것이기 때문에 배열의 ..

[프로그래머스 월간 코드 챌린지 시즌 1] 이진 변환 반복하기 (구현, 계산) [C++]

https://programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 단순한 문제이다. 주어진 이진수를 1. 이진수에서 0을 제외한다. - deleteZero 함수 (pair 로 변환한 이진수와 지운 0의 개수를 반환한다) 2. 나온 이진수 결과물의 길이를 다시 이진수로 만든다. - convert 함수 3. 위의 과정을 반복하면서 최종적으로 1이 나오면 종료한다. 여기서 진행하면서 변환 횟수와 지운 0의 개수를 세서 반환하면 된다. #include #include #include #include using namespace std; typedef pair psi; psi deleteZero(string..

[프로그래머스 2018 KAKAO BLIND RECRUITMENT 3차] 방금 그곡 (문자열, ) [C++]

https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 신경 쓸게 많은 까다로운 문제였다. 내가 문제를 푼 순서는 1. 입력값으로 주어진 musicInfos를 파싱 했다. - split 함수를 통해 vector 으로 바꿨다. 2. 파싱 한 값들 중 HH:MM 형식의 시간 데이터를 int형으로 변환했다. - convert함수를 통해 int형으로 변경 3. string형태의 melody를 split 해줬다...

[프로그래머스 위클리 챌린지] 피로도 (완전탐색, next_permutation) [C++]

https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 각 던전에는 입장할 수 있는 최소 피로도, 던전을 돌고 나면 소모되는 피로도가 주어진다. 전체 피로도가 주어지고, 던전을 입장하면서 최대 몇 개의 던전을 돌 수 있는지 구한다. 처음엔 그리디 같은 걸 생각했지만, 던전의 개수도 8개 이하이기 때문에 완전 탐색으로 풀었다. 완전 탐색으로 던전을 진입하는 순서를 만들고, 각 순서 쌍마다 다 던전을 돌아보는 방..

[baekjoon 22867] 종점 (스위핑, 문자열, 정렬) (C++)

https://www.acmicpc.net/problem/22867 22867번: 종점 주행을 마친 버스들이 종점에 들어온다. 종점에 들어온 버스는 버스를 정비하기 위한 자리에 들어간다. 즉, 종점에 버스 4대가 있다면 버스를 정비할 수 있는 공간이 최소 4개 이상 필요하다. www.acmicpc.net 버스들이 정류장에 들어오고, 나가는데 정류장에 최대 몇 대가 머무르다 가는지 출력하는 문제이다. 나는 처음에 시간을 모두 파싱 해서, 모두 ms로 단위를 바꿔준 다음에 누적합 풀듯이 풀었다. 시각 * 3600 * 1000 + 분 * 60 * 1000 + 초 * 1000 + 밀리초 그래서 총배열의 크기가 86400000이지만 메모리 제한이 1024mb라 통과했다. 하지만 더 간단한 방법이 있다. 어차피 시..

[프로그래머스 2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (파라매트릭 서치) [C++]

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr n이 20만이고 각 배열의 최댓값(m)은 2억이다. 따라서 매번 모든 배열에 -1을 빼주면서 k개 이내의 돌다리를 건너는 게 가능한지 확인하는 방법은 시간 초과가 날 것이다. 따라서 파라매트릭 서치를 사용했다. 이분 탐색으로 몇 번째에 건너지 못하는지를 찾는 것이다. 그렇게 되면 건너는 게 가능한지 확인하는 O(n) * 적당한 값을 이분 탐색하는 logm이므로 O(nlogm)에 해결이 가능하다. #include #include #include using namespace st..