BackJoon
1.[백준] 파이썬 문제 풀어보기
문제 풀이의 전략과 분석, 구현을 복습하는 차원에서 기록한다
2.[백준/파이썬] 2775번 - 부녀회장이 될테야
풀이 전략각 층의 호실 인원 수 규칙은 파스칼의 삼각형에서 조합의 원리를 떠올릴 수 있다. 예를 들어 2층 3호의 인원은 2층 2호 + 1층 3호 인원을 더한 것이 된다. 0층의 정보를 바탕으로 입력받은 층,호실 까지의 인원 정보를 구하여 출력한다.코드
3.[백준/파이썬] 1011번 - Fly me to the Alpha Centauri
기계의 이동 원리를 고려하여 거리에 따른 이동 패턴과 횟수를 보면, 1부터 2번씩 더해가며 거리가 늘어난다. 따라서 총 거리에서 1부터 2번씩 빼면서 횟수를 세는 방식으로 해결한다.
4.[백준/파이썬] 2839번 - 설탕 배달
주어진 무게를 최소한의 갯수로 채우려면 무게가 큰 봉지를 최대한으로 하여야하고 다르게 말하면 무게가 작은 봉지를 최소화 하여야 한다. 따라서 전체 무게에서 5킬로그램짜리로 채울 수 있을 때까지 3킬로그램으로 채운 후 5킬로그램으로 나머지를 채운다.
5.[백준/파이썬] 1929번 - 소수 구하기
N,M이 최대 1,000,000이므로 O(NlogN)이하의 알고리즘을 사용하여야 시간 초과가 생기지 않을 수 있다. 소수를 구하는 문제에서 사용할 수 있는 전략은 1. 수의 제곱근까지 검사하는 방법 2. 에라토스테네스의 체를 이용하는 방법이 있다. 이 중 에라토스테네스
6.[백준/파이썬] 4948번 - 베르트랑 공준
1929번-소수 구하기와 매우 유사한 문제이다. 소수 관련 문제는 에라토스테네스의 체를 이용하는 것이 가장 효율적이다. 입력 테스트 케이스가 여러개 이므로 매 번 소수를 구하는 것이 아닌 n이 123,456 이하의 수 이므로 $2\*123,456$ 까지 소수를 구해놓
7.[백준/파이썬] 9020번 - 골드바흐의 추측
n의 범위가 $2\\leq n\\leq 10000$ 이고 여러 번의 테스트 케이스를 적용하므로 $O(N^2)$의 시간 복잡도는 안된다. 소수 배열에서 조건을 만족하는 다른 소수를 찾으려면 in을 통하여 찾게 되는데, 이는 $O(N^2)$의 복잡도를 야기한다. 따라서 에
8.[백준/파이썬] 1002번 - 터렛
문제 설명 풀이 전략 코드
9.[백준/파이썬] 2447번 - 별 찍기 - 10
입력이 3의 배수로 주어지고, 문제에서 나온 것 처럼 $(N/3)\\times(N/3)$ 크기의 공백을 N/3 크기의 패턴이 둘러 싼 모양을 출력해야 한다. 가장 작은 N=3의 패턴부터 채워 재귀적으로 패턴을 채워나가는 것이 중요 포인트이다. 별 맵을 만드는 재귀 함수
10.[백준/파이썬] 11729번 - 하노이 탑 이동 순서
n개의 원판을 A에서 C로 이동시키는 과정을 생각해보면 최종적으로 n-1개의 원판을 B에 놓고, 남은 하나의 원판을 A에서 C로 옮긴 후 B의 원판들을 C에 옮기면 된다.hanoi 함수를 보면 재귀 호출을 할 때 인자의 순서가 다른 것을 볼 수 있는데, 원래 인자 순서
11.[백준/파이썬] 2231번 - 분해합
주어진 입력인 분해합에서 역으로 생성자를 추정하는 것은 어려운 일이다. 생성자가 여러 개일 때는 가장 작은 수를 출력해야하므로 작은 수부터 키워가며 분해합을 생성해 본다. 효율적인 계산을 위하여 자릿수에 따른 최소 숫자부터 시작하는 것이 좋다. 각 자릿수를 더할 때에
12.[백준/파이썬] 1018번 - 체스판 다시 칠하기
주어진 입력 보드에서 $8\\times8$ 크기를 분리하고, 분리한 보드의 수정 횟수를 구해가며 최소 수정 횟수를 출력한다. 주어진 보드에서 생성할 수 있는 $8\\times8$ 프레임의 좌상단 꼭짓점 인덱스를 모두 순회하며 수정 횟수를 비교하며 최소 수정 횟수를 구하
13.[백준/파이썬] 2751번 - 수 정렬하기 2
N의 범위가 $1\leq N\leq1,000,000$이므로 $O(NlogN)$의 복잡도를 가진 정렬을 이용한다. 파이썬 내장함수 $sort(), sorted()$가 퀵 정렬로 구현되어 $O(NlogN)$을 가지므로 사용하고, 입력이 N번 들어오므로 $input()$함
14.[백준/파이썬] 10989 - 수 정렬하기 3
N의 범위가 $1\\leq N\\leq 10,000,000$ 으로 $O(NlogN)$의 알고리즘으로도 시간 초과가 발생한다. 입력으로 주어지는 자연수의 범위가 $1\\leq K\\leq 10,000$ 이므로 $O(N+K)$의 알고리즘인 계수 정렬을 이용하면 해결할 수
15.[백준/파이썬] 2108 - 통계학
문제 설명 풀이 전략 문제에서 구해야하는 값 중 중앙값, 최빈값은 정렬을 해야만 구할 수 있는 값이므로 정렬을 해야하는데, 최빈값 코드
16.[백준/파이썬] 18870번 - 좌표 압축
문제를 분석해보면 N개의 숫자가 주어지고 각 숫자에 대해 자기보다 작은 숫자의 수를 출력해야한다. N의 범위가 $1\\leq N \\leq 1,000,000$ 이고, 입력 숫자의 범위는 $-10^9 \\leq X_i \\leq 10^9$ 이다.출력해야 하는 값은 자신보