본문 바로가기
728x90
반응형

알고리즘39

[백준] 12891번 : DNA 비밀번호 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 문제 설명 2. 풀이과정 P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 부분 문자열의 길이가 P이므로 슬라이딩 원도우의 개념을 이용해 문제를 쉽게 해결할 수 있다. 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘이다. 먼저 문자열의 시작 위치에 포인터를 하나 두고, 부분 문자열의 길이만큼 뒤에 포인터.. 2024. 1. 10.
[백준] 1253번 : 좋다 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 개수가 2,000이라고 가정하면 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다. 하여 정렬, 투 포인터 알고리즘을 사용하여 문제를 해결할 수 있다. 단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에서 제외해야 한다. 수를 입력받아 리스트 A에 저장한 후, 오름차순으로 정렬한다. 투 포인터 s, e를 배열 A 양쪽 끝에 위치시키고 A[s] + A[e]가.. 2024. 1. 9.
[백준] 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.
[백준] 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.
728x90
반응형

티스토리툴바