문제 풀이/프로그래머스 알고리즘, SQL
[프로그래머스 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개 이하이기 때문에 완전 탐색으로 풀었다. 완전 탐색으로 던전을 진입하는 순서를 만들고, 각 순서 쌍마다 다 던전을 돌아보는 방..
[프로그래머스 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..
[프로그래머스 2019 카카오 개발자 겨울 인턴십] 불량 사용자 (DFS, 조합) [C++]
https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 불량 사용자로 판단되는 아이디의 경우를 찾는 문제이다. 1. *로 일부분 마스킹된 banned_id와 user_id가 일치하는지 확인해야 한다. - 이건 문자열 하나씩 보면서 일치하는지, 불일치하는지 확인하면 된다. *인 경우는 패스, 길이도 봐야 한다. 2. 찾은 user_id로 중복을 제외하고 경우의 수를 찾아야 한다. - 나는 처음에 각 banned_id에..