TIL💡/Algorithms(157)
-
[프로그래머스] 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 요즘 어려운 알고리즘을 도전하면서 오히려 기본기를 놓치는 기분이랄까... 그래서 DFS를 다시 해보았다. 끝까지 n개의 숫자를 탐색하면서 풀어야 한다. void dfs(vector &numbers, int idx, int value) { if(idx == sz) { if(value == target_g) { answer++; } return; } int num = numbers[idx]; valu..
2022.07.23 -
[AtCoder] Jumping Takahashi 2
https://atcoder.jp/contests/abc257/tasks/abc257_d D - Jumping Takahashi 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 처음에 나는 BFS 방식을 시도하였으나 시간 초과가 발생하였다. 그러나 스터디를 하면서 플로이드 와샬 알고리즘을 이용하면 빠르게 풀 수 있다는 소식을 접했다. 지금까지 자주 풀어보았던 다익스트라 알고리즘은 한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 반면 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 ..
2022.07.23 -
[AtCoder] Addition and Multiplication2
https://atcoder.jp/contests/abc257/tasks/abc257_e E - Addition and Multiplication 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 뭔가 쉬워보였으나 마음처럼 쉽게 풀리지 않은 문제였다. $x$가 10의 자리 단위로 커지니 최대한 큰 수부터 앞자리에 넣는 것이 유리하다는 생각을 하여서 C 배열의 뒷자리부터 확인하며 $x$를 만들어나갔다. 정말 간단한 Greedy 문제라고 생각했다. 하지만 그렇지 않았다.. 아무리 앞에 큰 9를 넣는다한들 결과적으로 자릿수가..
2022.07.22 -
[프로그래머스] 베스트앨범 (feat. Hash)
이전에 N사 코딩테스트를 봤을 때 해시를 잘 다루지 못해 그런 아쉬움으로 해시 연습 삼아 다시 풀어보았다. 우선순위: 장르별 재생 횟수 내림차순 - 장르 내 재생 횟수 내림차순 - 고유번호 오름차순 노래의 장르를 나타내는 문자열 배열: genres 노래별 재생 횟수를 나타내는 정수 배열: plays 이렇게 되면 추가적으로 필요한 자료 구조 - 장르별 전체 재생 횟수 저장 - 장르별 곡당 재생 횟수: 곡별로 재생횟수를 저장해야하므로 value에는 vector어야 한다. 이렇게 문제를 까고 보면 어렵지 않은데 막상 해시를 여러 개 써야하는 순간이 오면 굉장히 헷갈린다... 따라서 헷갈리지 않고 어떤 자료구조를 써야하는지를 유심히 고민하고, 헷갈리지 않는다면 쉽게 풀 수 있을 것 같다. unordered_ma..
2022.07.18 -
[프로그래머스] 폰켓몬
https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr LV 1. 답게 메소드에 익숙하면 빠르게 풀 수 있는 문제이다. 만약 종류의 수가 N / 2보다 작으면 조합의 최대 크기는 종류의 수 그 자체이고, 그렇지 않다면 최대로 고를 수 있는 수인 N / 2가 된다는 아이디어만 살리면 된다. #include #include using namespace std; int solution(vector nums) { int answer = 0; int sz = n..
2022.07.17 -
[AtCoder] C - Robot Takahashi
https://atcoder.jp/contests/abc257/tasks/abc257_c C - Robot Takahashi AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 1. 이분 탐색 2. 완전 탐색 3. 누적합 주의 사항 - 모든 요소가 child or adult일 가능성 - 중복된 weight 존재 가능성 처음에는 보자마자 이분 탐색으로 풀면 될 거 같아서 계속 도전했으나 잘되지 않았다. 이분 탐색을 하려면 답의 탐색 기준이 명확해야 했기 때문이다. 하지만 이 문제는 명확할 수 없었다. 이 문제가 요구하는 바는 ..
2022.07.05