Dawn

가장 기본적인 약수의 개수를 구하는 문제부터 시작해보자. 어떤 자연수 n이 주어졌을 때, n의 약수의 개수를 구하라.약수는 나누어 떨어지게 하는 수를 의미한다.n = int(input())cnt = 0for i in range(1, n+1): if n % i == 0: cnt += 1 print(cnt)어떤 수를 입력 받고, 개수를 셀 변수를 선언한다.range는 end에서 -1한 값까지 반복한다.자기자신을 나누는 것도 가능하기에 n+1을 하여 구해준다. 시간복잡도는 n에 따라 반복횟수가 선형적으로 증가하기에 O(n) 이다. (1부터 n까지 반복) 이제 최적화를 해보자.약수는 항상 a * b = n 쌍으로 존재하기 때문에 짝수 개가 된다.ex) 6 = 1 * 6, 2 * 3..

그리디 알고리즘 (Greedy Algorithm, 탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.매순간 좋아 보이는 것만 고르며, 현재 선택이 나중에 미칠 영향을 고려하지 않고, 상황이 오면 그때 적합한 것을 선택한다.알고리즘이 작성할 때 두 가지 조건을 만족시켜주어야 한다.탐욕스러운 선택 조건 (Greedy Choice Property)각 단계에서 최적의 선택을 함으로써 전체 문제의 최적 해를 얻어야 한다.현재 단계에서의 최적 선택이 이후 단계에서도 여전히 최적 선택으로 이어져야 하고, 이를 통해 한 번의 선택이 전체 문제 해결에 유리하게 작용하도록 구성해야 한다. 최적 부분 구조(Optimal Substructure)문제의 최적 해답이 그 하위 문제들의 최적 해답으로부터 구해질 수 있는..

프로그래머스, 기능개발 - 42586 파이썬(Python) 풀이 안녕하세요. 프로그래머스 Level 2 문제인 '기능개발 - 42586' 파이썬으로 풀어보았습니다.문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다.  문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 설명프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도..

백준, 18870 - 좌표 압축 파이썬(Python) 풀이 안녕하세요. 백준 실버2 문제인 '18870 - 좌표압축' 파이썬으로 풀어보았습니다.문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다. 문제 링크https://www.acmicpc.net/problem/18870  북마크가 생성이 안되어 나중에 추가하겠습니다..문제 설명수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.제한사항입력첫째 줄에 N이 주어진다.둘째 줄..

프로그래머스, 귤 고르기 - 138476 파이썬(Python) 풀이 안녕하세요. 프로그래머스 Level 2 문제인 '귤 고르기 - 138476'를 파이썬으로 풀어보았습니다.문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다.  문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/138476?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하..

프로그래머스, 멀리 뛰기 - 12914 파이썬(Python) 풀이 안녕하세요. 프로그래머스 Level 2 문제인 '멀리 뛰기 - 12914'를 파이썬으로 풀어보았습니다. 문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는..

백준, 10799 - 쇠막대기 파이썬(Python) 풀이 안녕하세요. 백준 실버2 문제인 '10799 - 쇠막대기' 문제를 파이썬으로 풀어보았습니다. 문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다. 문제 링크 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 설명 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자..

프로그래머스, 카펫 - 42842 파이썬(Python) 풀이 안녕하세요. 프로그래머스 Level 2 문제인 '카펫 - 42842'를 파이썬으로 풀어보았습니다. 문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Le..