Algorithm

[Algorithm] 시간 복잡도 (Time Complexity)

🟩 시간 복잡도(Time Complexity)란?알고리즘이 입력 크기에 따라 얼마나 많은 시간을 소요하는지를 나타내는 척도.즉, 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.일반적으로, 입력 데이터의 크기가 커질수록 알고리즘의 실행시간이 어떻게 증가하는지를 분석하여 효율성을 평가하는데 사용한다. 시간 복잡도는 보통 빅오 표기법(O)을 사용하여 표현한다.예를 들어, O(n)이라면 입력 크기 n에 비례하는 시간을 소요한다는 의미이다. 🟩 시간 복잡도 표현 방법시간 복잡도는 보통 점근 표기법(Asymptotic Notation)으로 사용된다.https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95..

[BOJ] 1259 팰린드롬수 - Python

■ 문제 링크 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net ■ 문제 본 문제는 solved.ac 브론즈 1 문제이다. ■ 풀이 처음에 반복문 안에서 시작한다. 이는, 0을 입력 받았을때, 소스코드를 종료하기 위함이다. number를 입력 받는데, 예를들어 number이 1221일때, 펠린드롬 수인지 분별하기 위해, 우리는 이것을 비교하게 된다. number[0] == number[-1] number[1] == number[-2] 이 두개가 모두 같은지 확인..

[BOJ] 2231 분해합 - Python

■ 문제 링크 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net ■ 문제 본 문제는 solved.ac 브론즈 2 문제이다. ■ 풀이 음.. 이 문제를 푸는데에 고민이 많았던 것 같다. 처음 나의 계획은, N에서부터 하나씩 마이너스 해주면서, 분해합을 만족하는 값을 찾는다. 분해합을 구했을 경우, 반복문 탈출을 하려 했으나, 문제가 있었다. 여기서는 N의 가장 작은 생성자를 구하라고 하였다. 그래서 시간초과로 안될 것 ..

[BOJ] 2869 달팽이는 올라가고 싶다 - Python

■ 문제 링크 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net ■ 문제 본 문제는 solved.ac 브론즈 1 문제이다. ■ 풀이 나는 이 문제를 풀때 우선 처음 이 방식으로 접근했다. 이 수식에 대해 설명하자면, 달팽이가 낮에 올라가고 밤에 내려오는 것이 A-B 이걸 x번 반복했다고 생각하는 것이다. 그리고 여기서 중요하게 보아야 할 것이, 달팽이가 마지막 날에 A미터를 올라가서 그게 나무막대의 길이보다 크거나 같으면, 이미 도착했으니 굳이 내려올 필요가 없다. 올라가는데 걸리는 시간은, x에 1(마..