목록알고리즘 (6)
네박자대로
programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr level 3 답게 다른 해시 문제보다 정말 요구사항이 많은 문제였다! 문제를 정확하게 이해하고, 알고리즘을 어떻게 짤지 잘 계획하지 않고 무작정 손부터 움직이면 안되는 문제였다. 먼저 문제를 천천히 뜯어보자. 장르 별로 가장 많이 재생된 노래 2곡씩 모아 베스트 앨범을 출시하려고 한다. 노래는 각 고유번호가 있으며, 노래 수록 기준은 다음과 같다. (1) 가장 많이 재생된..
programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 이전 문제는 굳이 해시로 풀지 않아도 해결 가능했다면 위장 문제 부터는 해시로 풀어야 효율적으로 해결할 수 있었다. 하지만 나는 unordered_map STL을 써본 적도 없었고, 해시맵에 대한 이해가 부족했기 때문에 다른 분들의 블로그 글과 정리를 참고해서 이 문제를 해결할 수 있었다 ㅠㅠ 우선 참고한 블로그 링크를 걸어두겠다 kamang-it.tistory.com/entry/mapunorderedmapC%EC%97%90%EC%84%9C-map%EB%94%95%EC%85%94%EB%84%88%EB%A6%ACdictionary-%EC%97%B0%EA%B4%80..
programmers.co.kr/learn/courses/30/lessons/42577 해시 kit의 두 번째 문제이다. 해시로 풀고 싶은데 계속 vector를 sort해서 풀게 된다.. 아무튼 아이디어는 이렇다. 먼저 phone_book vector를 sort함수로 정렬한다. 그럼 가장 길이가 짧고 알파벳 순서가 빠른 문자열들이 벡터의 앞 쪽에 위치한다. 이렇게 되면 인덱스 번호가 작은 벡터 값은 자신보다 인덱스 번호가 큰 벡터 값의 접두어가 될 가능성이 크다. 그러나 인덱스 번호가 큰 벡터 값이 자신보다 인덱스 번호가 작은 벡터 값의 접두어가 될 일은 절대 절대 없다. 그럼 이중 for문을 만들 수 있게 되는데, 접두어 후보를 head_number라고 칭하고, 접두어가 포함될 가능성이 있는 문자열을 ..
programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 항상 백준에서만 연습하다가 처음 프로그래머스 문제를 풀어봤는데 웹디자인도 보기 편하고 깔끔해서 자주 들를 것 같다! 고득점 kit를 먼저 하나씩 풀어보려고 한다. 우선 해시 kit의 첫 번째 문제, '완주하지 못한 선수'이다. level 1 답게 금방 풀었다. 아이디어는 다음과 같이 생각했다. participant vector와 completion vect..
2018 카카오 코드 페스티벌 예선 2번 문제 www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째 www.acmicpc.net 처음에 문제가 이해되지 않아 겁먹고 포기할 뻔 했는데 반복해서 읽어보니 걱정만큼 어려운 문제가 아니어서 찬찬히 풀 수 있었다! 마찬가지로 곧장 코드를 짜기 전에 어떻게 풀 것인지 손코딩으로 생각해봤다. 우선 N 개의 인형의 나열 순서는 input으로 받기 때문에 고정되어 있었다. 내가 할 일은 이 고정된 인형의 순서에서 K개 이상의 연속된 인형들의 최소 표준편차를 구하..
2018 카카오 코드 페스티벌 예선 1번 문제 www.acmicpc.net/problem/15953 15953번: 상금 헌터 첫 번째 줄에 제이지가 상상력을 발휘하여 가정한 횟수 T(1 ≤ T ≤ 1,000)가 주어진다. 다음 T개 줄에는 한 줄에 하나씩 제이지가 해본 가정에 대한 정보가 주어진다. 각 줄에는 두 개의 음이 아닌 www.acmicpc.net 여태까지는 알고리즘을 머릿속에서 정리하기도 전에 바로 코드부터 무작정 짰었다. 그러다보니 항상 코드도 지저분하고 복잡해져서 주석을 달지 않으면 내가 짠 것도 못알아보게 되었는데 그 습관을 고치기 위해서 블로그에 알고리즘을 찬찬히 정리하고 손코딩으로 충분히 확신이 들 때까지 절대 키보드에 손을 올리지 않으려고 한다! 첫 게시글에서 그치지 말고 앞으로 꾸..