파이썬 백준 2217번 실버 4 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 보기 분류: 수학, 그리디 알고리즘, 정렬 문제 풀기 최대 중량을 들기 위해서는 단일 로프가 허용하는 중량이 클수록 그리고 중량을 분산할 로프가 많을수록 유리하다. 따라서 임의의 순서로 주어지는 로프의 중량 정보를 내림차순 정렬을 하고 가장 허용 중량이 작은 로프부터 하나씩 제거해 가며 최댓값을 찾는다. 내림차순 정렬된 로프 리스트에서 맨 오른쪽 데이..

파이썬 백준 1789번 실버 5 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 문제 보기 분류: 수학, 그리디 알고리즘 문제 풀기 가장 많은 N 개의 자연수를 얻기 위해서 가장 작은 1 부터 2, 3, ,,, 순서로 합을 시켜준다. 이때 S 를 넘게 되면 그 이전의 순차 자연수는 마지막 S 를 맞추기 위해 정확한 값으로 한 번 들어간다. 최대 N 을 위해 이런 식으로 진행된다는 의미이다. 코드 작성은 S 에서 1, 2, 3, ,,, 순차적으로 자연수를 빼주다가 S 가 음수가 되는 시점에 반복문을 빠져나오고 그때의 N 의 개수를 출력하는 식으로 작성하였다. 코드..

파이썬 백준 2212번 골드 5 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 보기 분류: 그리디 알고리즘, 정렬 문제 풀기 예제 입력 1 번에 대한 경우를 그림으로 나타내면 위와 같다. 집중국이 커버칠 수 있는 최소한의 거리를 찾으면 가장 넓은 구간 3 을 제외하고 2, 1+2 를 선택하여 최솟값을 이루는 집중국을 위치시킬 수 있다. 임의로 주어진 센서의 순서를 오름차순으로 정렬을 하고, 그 숫자(센서) 간의 ..

파이썬 백준 12904번 골드 5 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 보기 분류: 구현, 문자열, 그리디 알고리즘 문제 풀기 역으로 T 에서 S 로 변경이 가능한지를 확인한다. 이 문제로 주어진 문자열을 다루는 것에 대해 일부 학습이 되었다. 맨 뒷 문자 확인, 맨 뒷 문자 제거, 문자 전체 뒤집기. while loop 를 실행하면서 같은 T 와 S 가 같아질 때까지 반복을 하여 조건을 만..

파이썬 백준 16953번 실버2 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 보기 분류: 그리디 알고리즘, 그래프 탐색, 너비 우선 탐색 문제 풀기 A 에서 B 로 가지 않고 B 에서 A 로 가능한지를 바라보았다. while 을 통해 B 가 짝수일 때는 2 로 나누고, 맨 뒷자리 1 이 있을 때 1 을 제거하여 답을 찾을 때까지 반복한다. 함수 fnConversion() 에 적용된 조건은 다음과 같다. 1. 제일 먼저 B 와 A 가 같은지 비교하여 결과를 내보내고 while 을 멈출 수 있도록 한다. 2. 변환이 불가능한 경우에 대한 조건으로 B 가 A 보다 ..

파이썬 백준 1026번 실버4 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 보기 분류: 수학, 그리디 알고리즘, 정렬 문제 풀기 문제의 의도가 좀 애매한 것 같다. B를 정렬하지 말라고 했는데 정작 결과를 도출해야 하는 요소는 주어진 계산식으로 만들어질 수 있는 최솟값이다. 따라서, S = A[0] × B[0] + ... + A[N-1] × B[N-1] 에서 B 의 배열은 마음속에 고정해 두고, A 와 B 가 짝을 이룰 수 있는..

파이썬 백준 2167번 실버5 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 보기 분류: 구현, 누적 합 문제 풀기 난이도 실버5 표시되어 있어 생각한 방법으로 제출해도 될 것이라 생각했다. 하지만 시간 초과 결과를 얻었다. 동일한 코드를 PyPy3 로 제출하면 정답처리가 된다. 이 과정에서 다이나믹 프로그래밍으로 풀어야 함을 확인하였고, 다음 문제를 해결하는데 적용할 계획이다. PyPy3 로 제출한 코드는 ..

파이썬 백준 10825번 실버4 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 보기 분류: 정렬 문제 풀기 sort() 함수와 lambda 를 이용하여 한 줄로 작성을 하려 했는데 생각처럼 되지 않았다. 아니 다시 해보니 생각대로 된다. 답안은 이미 제출했는데.. 맥주의 힘인가.. 괄호를 치는데 잘못됨이 있었다 더 공부하자 문제에서 제시한 조건 1. 2. 3. 4. 순서를 보면 순차적으로 다음 조건을 제시하는데 이는..

파이썬 백준 1476번 실버5 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 보기 분류: 수학, 브루트포스 알고리즘, 정수론 문제 풀기 문제에서 제시한 설명대로 코드를 작성하였다. 매해 1년이 한 번씩 올라갈 때마다 지구, 태양, 달을 나타내는 수를 하나씩 증가시켜 입력에서 제시한 E, S, M 의 값이 나올 때까지 반복문을 작동시키고 해당 조건을 만족하면 결과 year 를 출력시키고 반복문을 빠져나온다. 코드 보기 import sys inp..

파이썬 백준 4963번 실버2 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 기존 상하좌우 이웃으로 연결된 문제에서 대각선 네 방향에 대해 추가적 처리를 생각한다. matrix 에서 처음으로 1을 발견하면 fnBFS() 를 실행하여 이웃된 8방향 모두 찾아가 1이 보이면 방문 처리한다. 이렇게 남은 matrix 에 대해 조건을 만족하여 fnBFS() 함수에 들어..