본문 바로가기
728x90
반응형

분류 전체보기497

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/12015 1. 문제 설명2. 풀이과정해당 문제는 주어진 수열을 순서대로 봤을 때 가장 긴 증가하는 부분 수열을 찾아 그 길이를 구하는 문제이다.수열의 값을 하나씩 불러오며 바로 이전 값보다 크면 바로 추가하고 이전 값보다 크지 않으면 해당 값이 들어갈 자리를 찾아 새로 저장한다.값이 들어갈 자리를 찾는 방법은 결과 수열을 저장한 리스트의 양쪽 끝을 기준으로 잡고 중간 지점을 찾아 해당 위치의 값과 비교한다.만약 넣을 값이 중간 위치의 값보다 크면 더 뒤쪽에 값을 넣어야 하므로 앞쪽 기준을 중간 지점 다음으로 옮긴다.반면에 넣을 값이 중간 위치의 값보다 크지 않으면 더 앞쪽에 값을 넣어야 하므로 뒤쪽 기준을 중간 지점으로 옮긴다.계속 반복하다가 앞.. 2024. 7. 25.
[백준] 2110번 : 공유기 설치 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2110 1. 문제 설명2. 풀이과정해당 문제는 집에 정해진 개수만큼 공유기를 설치할 때 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이다.가장 인접한 두 공유기 사이의 최대 거리를 구하려면 공유기가 설치된 집의 위치를 알아야 한다.공유기를 설치할 때 그 거리의 최소 거리인 1과 최대 거리인 가장 양끝에 위치한 두 집의 거리를 시작으로 하여 공유기를 설치하면서 최소 거리와 최대 거리를 계속적으로 수정해 나간다.공유기를 설치할 때는 최소 거리와 최대 거리를 통해 그 중간 거리를 구하고 공유기가 설치된 바로 이전 집에서 중간 거리보다 같거나 더 멀리에 있는 집에 공유기를 설치한다.이후 공유기가 설치된 집의 수가 공유기의 수보다 적으면 더 좁은.. 2024. 7. 24.
[백준] 1654번 : 랜선 자르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1654 1. 문제 설명2. 풀이과정해당 문제는 처음 가지고 있는 랜선의 개수에서 필요한 랜선의 개수만큼 생기도록 랜선을 자를 때, 만들 수 있는 랜선의 최대 길이를 구하는 문제이다.처음 가지고 있는 랜선의 길이에서 만들 수 있는 랜선의 최소 길이와 최대 길이를 정한 후, 그 중간 길이를 구하여 각 랜선을 중간 길이로 잘라 개수를 세어준다.만약 랜선의 개수가 필요한 랜선의 개수보다 적으면, 기준이 되는 중간 길이가 더 짧아야 하므로 최대 길이를 중간 길이 이전으로 변경한다.반면에 랜선의 개수가 필요한 랜선의 개수보다 많거나 같으면, 기준이 되는 중간 길이가 더 길어도 되므로 최소 길이를 중간 길이 다음으로 변경한다.최소 길이가 최대 길이를 넘기 전.. 2024. 7. 23.
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/6549 1. 문제 설명2. 풀이과정해당 문제는 히스토그램에서 가장 면적이 넓은 직사각형의 넓이를 구하는 문제이다.문제를 해결하기 위해서는 스택 자료구조를 활용하여 히스토그램의 막대를 하나씩 가져와 2가지 과정을 수행한다.우선 첫 번째 과정은 히스토그램의 막대를 하나씩 가져오며 이전 막대의 길이보다 작은 막대가 나올 경우 현재까지 막대의 중에서 가장 큰 직사각형의 넓이를 구한다.두 번째 과정은 이전 막대보다 크거나 같은 길이의 막대가 나올 경우 해당 막대를 스택에 추가한다.첫 번째 과정에서 가장 큰 직사각형의 넓이를 구할 때는 현재 막대의 길이보다 큰 막대들만 가지고 가장 큰 직사각형의 넓이를 구해야 한다. sys.stdin.readline() 함.. 2024. 7. 22.
[백준] 11444번 : 피보나치 수 6 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11444 1. 문제 설명2. 풀이과정해당 문제는 선형대수 지식이 요구되는 문제이다.피보나치 수를 행렬로 나타내면 아래와 같은 식으로 나타낼 수 있다.해당 행렬을 활용하여 피보나치 수를 10830번 : 행렬 제곱 문제와 동일하게 분할 정복 알고리즘으로 해결한다.피보나치 수를 행렬로 나타내는 선형대수 지식만 알고 있었다면 쉽게 해결할 수 있는 문제지만, 해당 선형대수 지식이 쉽게 떠오르지 않는다.해당 문제를 해결하면서 선형대수 지식을 다시 한번 상기시켜 봤다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys구하고자 하는 피보나치 수의 번호를 입력받는다. N = int(sys.stdin.readl.. 2024. 7. 20.
[백준] 10830번 : 행렬 제곱 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/10830 1. 문제 설명2. 풀이과정해당 문제는 이전에 해결했던 2740번 : 행렬 곱셈 문제와 1629번 : 곱셈 문제를 함께 고려하면 문제를 해결할 수 있다.두 행렬을 곱하는 연산과 거듭제곱 연산을 분할 정복으로 해결하는 과정을 합치면 해결할 수 있다.각 행렬의 원소를 1,000으로 나눈 나머지를 구하는 문제이므로 두 행렬을 곱하는 연산에서 결과를 1,000으로 나눈 나머지로 저장한다.거듭제곱 연산에서는 1이면 기본 행렬을 반환하고, 1이 아닐 경우 짝수이면 두 행렬의 곱을 반환하고 홀수이면 두 행렬의 곱에 기본 행렬을 한 번 더 곱한 결과를 반환한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. imp.. 2024. 7. 19.
[R 공부하기] 8. 데이터 전처리 - 우당탕탕 개발자 되기 프로젝트 목차결측값특이값데이터 정렬데이터 분리와 선택데이터 샘플링과 조합데이터 집계와 병합 데이터 전처리란 수집한 원본(raw) 데이터를 분석이 가능하거나 용이한 형태로 변형 가공하는 작업을 말한다.데이터 전처리는 모든 데이터 분석의 시작이며 반드시 거치는 과정이다. 데이터 전처리의 목적은 데이터 품질의 향상을 위함이며, 데이터 품질이 낮으면 분석 기법이나 도구가 아무리 훌륭해도 좋은 분석 결과를 얻기 못한다.데이터 품질 문제를 야기하는 요인으로는 측정 오류와 수집 과정의 오류가 있다.측정 오류는 실수로 잘못된 기록을 하거나 측정 장비 자체의 결함 및 한계 등으로 발생한 오류이다.수집 과정의 오류는 데이터의 손실이나 중복으로 발생한 오류이다. 1. 결측값결측값(missing value)란 데이터를 수집하고 저장하.. 2024. 7. 12.
[백준] 2740번 : 행렬 곱셈 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2740 1. 문제 설명2. 풀이과정해당 문제는 간단히 행렬 곱셈을 구현해 보는 문제이다.행렬의 곱셈은 앞 행렬의 행을 차례대로 가져오고, 뒷 행렬의 열을 차례대로 가져와 각 위치에 있는 숫자를 서로 곱하여 더하면 결과 행렬의 값이 된다.앞 행렬의 첫 번째 행 1, 2를 뒷 행렬 첫 번째 열 -1, 0을 각각 곱하여 더하면 1 x -1 + 2 x 0 = -1 이 되는 것이다.이런 방식으로 행렬을 곱하면 위 그림과 같은 결과가 나오게 된다.행렬의 곱셈 연산을 수행하는 함수를 구현하며 문제를 해결한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys첫 번째 행렬 A의 크기를 입력받는다. N, M .. 2024. 7. 11.
[백준] 11401번 : 이항 계수 3 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11401 1. 문제 설명2. 풀이과정해당 문제는 이항 계수를 구하는 식 N! / (N - K)! * K! 을 1,000,000,007로 나눈 나머지를 구하는 문제이다.문제를 해결하기 위해서는 나머지 연산의 분배 법칙과 페르마의 소정리를 활용한다.분배 법칙은 (A x B) % p = ((A % p) X (B % p)) % p이다.페르마의 소정리는 p가 소수일 때 a^p = a % p를 의미하며, 양 변을 a^2로 나눠주면 a^(p - 2) = 1/a % p 가 된다.이를 활용하기 위해 N! / (N - K)! * K! 식을 곱셈으로 정리하면, N! * (N - K)! ^ -1 * K! ^ -1로 변환할 수 있고 이를 1,000,000,007로 나눈.. 2024. 7. 10.
[백준] 1629번 : 곱셈 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1629 1. 문제 설명2. 풀이과정해당 문제는 큰 수의 거듭제곱을 어떤 수로 나눈 나머지를 구하는 문제이다.거듭제곱의 최종 결과를 가지고 나머지 연산을 하면 큰 숫자일 경우 그 계산이 쉽지 않다.하여 거듭제곱을 전부 계산하기 전 작은 수일 때의 나머지 연산을 활용하여 최종 나머지 값을 구한다.A * B % C의 연산을 나눠보면 ((A % C) * (B % C)) % C의 연산과 동일한 결과가 나오게 된다.이를 활용해 거듭제곱의 나머지 연산을 구한다.문제에 나와있는 예시를 활용해 보면, 10^11 % 12 연산은 ( (10^5 % 12) * (10^5 % 12) * (10 % 12) ) % 12의 연산으로도 볼 수 있다.이를 더 작은 연산으로 나누.. 2024. 7. 9.
728x90
반응형

티스토리툴바