본문 바로가기
728x90
반응형

Baekjoon243

[백준] 1940번 : 주몽 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제의 시간 제한은 2초인데 N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용할 수 있다. O(nlogn) 시간 복잡도 알고리즘을 사용할 수 있기 때문에 정렬을 사용할 수 있다. 하여 재료들의 번호를 입력받은 뒤, 오름차순으로 정렬하여 양쪽 끝의 위치를 투 포인터로 지정해 문제를 해결한다. 투 포인터 start, end를 정렬한 재료들의 번호 양쪽 끝에 위치시킨 후 포인터.. 2024. 1. 8.
[백준] 2018번 : 수들의 합 5 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 주어진 시간 제한은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있다. 이러한 상황에서는 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 연속된 자연수의 합을 구하는 것이 문제이므로, 시작 값과 끝 값을 지정하여 연속된 수를 표현한다. (투 포인터) 시작 값과 끝 값을 모두 1로 두고 연속된 자연수의 합도 1로 저장한다. 두 위치를 끝까지 이동하면서 합이 N이 되는 경우의 수를 구한다.. 2024. 1. 8.
[백준] 10986번 : 나머지 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 최댓값이 106이라 연산량이 작게 느껴질 수 있겠지만 106개의 수에 대하여 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵다. 나머지 합 문제 풀이의 핵심 아이디어는 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구산 합의 나머지 연산을 한 값은 동일해야 한다는 것이다. (A + B) % C = ((A % C) + (B % C)) % C S[i] % M.. 2024. 1. 7.
[백준] 12865번 : 평범한 배낭 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제이다. 먼저 첫 번째 물건까지만 고려하여 배낭에 넣었을 때, 무게가 6이므로 6일 때 가치가 13이다. 무게가 7인 경우에는 더 이상 넣을 물건이 없으므로 그대로 최대 가치가 13이다. 두 번째 물건까지 고려하여 배낭에 넣었을 때, 두 번째 물건의 무게가 4이므로 무게가 4일 때 최대 가치는 8이다.. 2024. 1. 7.
[백준] 11660번 : 구간 합 구하기 5 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 문제 설명 2. 풀이과정 질의의 개수가 100,000이므로 해당 문제는 질의마다 합을 구하면 안 되고, 구간 합 배열을 이용해야 한다. 표가 2차원이므로 구간 합 배열 또한 2차원 배열로 생성해야 한다. 해당 구간 합 배열을 어떻게 구성할 것인지 고민하는 것이 문제의 핵심이다. S[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합 2차원 구간 합 배열의 1행, 1열부터 구한.. 2024. 1. 4.
[백준] 11659번 : 구간 합 구하기 4 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 수의 개수와 합을 구해야 하는 횟수는 최대 100,000이다. 게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다. 하여 구간 합을 이용해 문제를 해결한다. N개의 수를 입력받음과 동시에 합 배열을 생성한다. S[i] = S[i - 1] + A[i] 구간 i ~ j가 주어지면 구간 합을 구하는 공식으로 정답을 출력한다. S[j] - S[i - 1] 슈도코드 N(숫자 개.. 2024. 1. 4.
[백준] 1546번 : 평균 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 1. 문제 설명 2. 풀이과정 최고 점수를 기준으로 전체 점수를 다시 계산해야 하므로 모든 점수를 입력받은 후에 최고점을 별도로 저장해야 한다. 또한 문제에서 제시한 한 과목의 점수를 계산하는 식은 총합과 관련된 식으로 변환할 수 있다. A, B, C 점수에 대해 변환 점수의 평균을 구하는 식 (A / M * 100 + B / M * 100 + C / M * 100) / 3 = (A + B + C) * 100 / M / 3 = 총합 * 100 / 최댓값 /.. 2024. 1. 4.
[백준] 11720 : 숫자의 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 파이썬의 리스트 자료구조를 통해 쉽게 해결할 수 있다. 입력으로 주어지는 숫자를 문자열로 입력받아 리스트의 형태로 저장한다. 저장 후, 해당 리스트의 각 원소를 하나씩 불러와 문자형을 정수형으로 변환해 모든 자릿수의 값을 더한다. 숫자의 개수만큼 입력받은 값을 리스트 형태로 저장한다. numbers 리스트를 탐색하며 각 값을 정수형으로 젼환하여 결과에 누적으로 더한다. 슈도코드 n값 받기 numbers 변수에 list 함수를 이용하여 숫자를 한 자리씩 나누어 받기 sum 변수 선언 및 초기화 for nu.. 2024. 1. 3.
[백준] 9251번 : LCS - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 두 문자열의 부분 수열 중 가장 긴 부분 수열의 길이를 구하는 문제이다. 각 문자열을 2차원 리스트로 고려하여 해당 문자열까지 가장 긴 부분 수열의 길이를 저장해 나간다. 2차원 리스트는 각 문자열의 길이보다 1씩 크게 만들어 제일 앞에는 문자열을 빼는 경우를 생각한다. 초기 2차원 리스트는 위 배열처럼 나타낼 수 있다. [1][1] 위치에서부터 시작하여 마지막 칸까지 가장 .. 2023. 12. 29.
[백준] 2565번 : 전깃줄 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 전깃줄이 교차하지 않도록 하기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이다. 전깃줄은 A 전봇대에서 B 전봇대로 연결되기 때문에 교차하지 않으려면 연결된 전깃줄을 전깃줄의 B 전봇대 번호를 기준으로 오름차순 정렬하고, 이후 전깃줄을 차례대로 이전 전깃줄과 비교하여 교차되는지 안되는지 확인하면 된다. 처음부터 비교할 전깃줄 전까지 비교하며 만약 이전 전깃줄의 B 전봇대 번호가 더 작으면 해당 두 전깃줄은 서로 공존할.. 2023. 12. 28.
728x90
반응형

티스토리툴바