while (1): study();

출처: 1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 전형적인 그리디 유형의 문제입니다. 대략적인 점화식을 써보자면 sum_n = a_n + sum_n-1과 같습니다. 즉 이전까지의 카드 뭉치의 합은 계속 더해지므로 가장 작은 카드 뭉치들을 먼저 합쳐나가는 방식으로 풀어나가면 됩니다. 다만 주의할 점은 단순한 정렬과 반복으로는 풀 수 없다는 점입니다. 다음 코드를 살펴봅시다. n = int(input()) array = [] for _ in ..

출처: https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 정렬 문제라고 마냥 쉬운 것만은 아니라는 것을 깨닫게 해준 문제입니다. 각종 정렬기법을 달달 외우는 것보다, 어떻게 해서 정렬 알고리즘을 효과적으로 이용할만한 로직을 짤 수 있는지가 더욱 관건인 듯 합니다. 특히 이 문제의 경우 세심한 부분을 신경써주지 않으면 모든 테스트 케이스를 통과할 수 없습니다. 이하는 전체 소스코드입니다. def solution(..

출처: https://www.acmicpc.net/problem/18310\ 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 처음에 이진탐색을 이용해 접근하려 했으나 아이디어만 떠올릴 수 있다면 쉬운 문제이다. 역시 문제를 풀기 전에 손보다는 머리를 움직이는 것이 중요하다는 것을 다시금 느끼게 된다. 결과적으로 최적의 안테나 설치 장소는 중앙값이다. 중앙에서 멀어지면 멀어질수록 거리가 멀어진다는 것을 휴리스틱하게 확인할 수 있으며, 생각을 조금만 해봐도 그렇다. 소스코드는 다음과 같이 간단하게 작성할 수 있다. n = int(inpu..

출처: 10825번: 국영수 (acmicpc.net) 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net sort함수에 대한 이해도가 있다면 쉽게 해결할 수 있는 문제입니다. N이 1 이상 100,000 이하이기 때문에 O(NlogN)의 시간복잡도를 보장하는 기본 정렬 기능을 사용할 수 있습니다. 소스코드는 다음과 같습니다. n = int(input()) array = [] for _ in range(n): array.append(input()) array = [row.split() for r..

출처: https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 모든 간선의 길이가 1인 그래프 문제의 경우 BFS를 이용하여 해결할 수 있습니다. 다만 이 문제같은 경우 로봇의 길이가 2x1이기 때문에 좌표 2개를 신경써야 하고, 또한 회전을 구현해야 한다는 점에서 상당히 까다로운 문제입니다. 해당 문제의 시간제한은 1초이며, board의 한 변의 길이가 5 이상 100이하라는 점에서 크게 iteration 횟수에 구애받지 않고 풀이할 수 있으나..