Altiora Petamus

코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 🤔생각해보기 먼저 문제의 조건을 살펴보자면, 속한 노래가 많이 재생된 장르를 먼저 수록 → 각각 장르의 재생 횟수를 정렬된 상태로 봐야 한다. 장르 내에서 많이 재생된 노래를 먼저 수록 → 특정 장르에서 어떤 노래가 많이 재생되었는지 알아야 한다. 고유번호가 낮은 노래를 먼저 수록 → 최초 정렬시 고유번호로 정렬하여 Stable sort 가 유지되도록 유도하기 어느 정도 방향성을 잡은 후엔, 사고를 단순하게 하기 위해 dictionary 를 두 개 선언해서 풀..

코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 🤔생각해보기 처음엔 문제를 보고 살짝 당황했다. 문자를 하나하나 모두 체크하라는건지 도대체 이걸 어떻게 풀어야하나... 그래서 그림으로 그려봤다. 이런 모양의 그래프가 그려지며, 그림을 보면 반대편 끝에 있는 "cog" 가지 도달하기 위한 깊이를 세어주면 되겠다는 느낌이 든다. 그래프를 그려보면 알게되지만, 결국 모든 스펠링의 검사가 필요하다. 알고리즘을 순서대로 적어보자면, 거리를 알기 위해 BFS 를 이용하여 각 노..

2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 🤔생각해보기 모든 경우의 수를 구한 후, 조건을 초과하지 않는 가장 큰 합을 출력하면 되는 간단한 문제이다. for 문을 돌면서 3가지 카드 '조합'을 구해도 되겠지만, 파이썬 모듈 itertools 를 활용하면 복잡한 과정을 생략할 수 있다. 코드 from itertools import combinations n, m = map(int, input().split()) cards = list(map(int, input().spli..

2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 🤔생각해보기 이 문제는 사실상 최빈값을 구하라는 문제. 나머지는 단순한 연산으로도 구할 수 있다. 최빈값을 구하기 위해 여러가지 방법을 썼지만, 시간초과로 해결하지 못했었는데 Counter를 쓰면 갯수를 세야할 때 아주 편리하다는 것을 알게 되었다. 시간초과 # 최빈값(mode) ; N개의 수들 중 가장 많이 나타나는 값 modes = sorted(numbers, key=lambda x: numbers.count(x), reverse=True) if len(modes) == ..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 🤔생각해보기 지금까지 시작 지점이 하나인 그래프 탐색은 비교적 간단하게 해결할 수 있었다. 하지만 이 문제는 동시에 여러 지점에서 탐색을 진행해야해서 어떻게 해야할까 고민이였는데, 잘 생각해보니 그냥 BFS 알고리즘에다가 시작지점만 여러개를 넣어주면 되는 것이였다. 익은 토마토의 좌표를 찾아서 root 배열에 담아놓는다. BFS 탐색을 위해 queue 에 root 들을 담은 상태로 초기화한다. 미로 탐색 과정을 응용해서 전 칸의 값에 1을 증가시..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 🤔생각해보기 문제는 간단하다. 에라토스테네스의 체를 사용해서 풀면 된다. 개인적으로 소수 구하는 문제에서 자주 쓰는 방법은 제곱근까지만 약수의 여부를 검증해서 O(logN)의 시간 복잡도로 구하는 것이다. 에라토스테네스의 체는 다량의 소수를 한 번에 판별할 때 쓰면 좋은 방식으로 자세한 내용은 다음을 참고하자. 위키독스 온라인 책을 제작 공유하는 플랫폼 서비스 wikidocs.net m, n = map(int, input().split()) a = [False, False] + [True] *..

OddOccurrencesInArray coding task - Learn to Code - Codility Find value that occurs in odd number of elements. app.codility.com 🤔생각해보기 Arrays 관련 문제다보니 여러 풀이 방법이 있을 것이다. 그 중에 필자가 가장 먼저 떠오른 방법은 문제의 마지막에 적혀있는 조건과 관련이 있다. all but one of the values in A occur an even number of times. "A 의 값 중 하나를 제외한 모든 값은 짝수로만 발생한다" 단 하나를 제외한 모든 값이 짝수로 발생한다면, 홀수로 발생하는 그 하나를 집어낼 수 있으면 되는 것 아닌가? 개수를 세는 알고리즘은 여러가지가 있지만..

1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🤔생각해보기 피타고라스 정리 를 활용하여 원의 교점을 구하는 문제다. 생각보다 고려해야할 조건이 많아서 성공할거라고 확신했음에도 7번 정도 실패했다... 하나씩 조건을 해결해가면 금방 풀 수 있는 문제이니 한 번 정리해보자. 우선 distance = 두 터렛 간의 거리 를 구해야 한다. 거리(distance)가 0 보다 커야 두 터렛이 같은 위치가 아니므로 아래 조건(2~4)을 적용한다. 만약 두 터렛이 각자 계산한 거리 r1, r2, 그리고 distance 중 가장 긴 값이 나머지 두 값의 합보다 크다면 만나지 ..