CS 지식/Algorithm-Problem Solving 정리

링크 : https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수열 문제이다. 피보나치 수열이란, 제 0항을 0, 제 1항을 1로 두고, 두번째 항부터 바로 앞의 두수를 더한 수로 놓는다.(F(2) = F(1) + F(0)). 피보나치 수를 상향식 분석하면 아래와 같다. 결론적으로 계속해서 f(n) = f(n-1) + f(n-2) 형태로 나아가는것을 볼 수 있다. 다만 주의해 줄 것이 있다. 피보나치 ..

링크 : https://level.goorm.io/exam/43083/%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0/quiz/1 구름LEVEL 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이 level.goorm.io 우선 문제를 분석해 보겠습니다. 계단을 최대 2칸 오를 수 있다고 할때 계단을 오르는 방법의 가짓수를 출력하는 프로그램을 작성하시오. n 이 3인경우 1. 1 - 2 - 3 2. 1 - 3 3. 2 - 3 이를 기반으로 그림으로 작성해 보면 아래와 같습니다. 내가 지은 결론은, 계단을..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 소인수 분해를 문제를 풀면서 두가지 접근 방법을 생각하였다 1) 재귀 2) 단순 반복문 우선 문제를 파악해보자 문제 : 정수 N이 주어졌을때 소인수분해하는 프로그램을 작성하시오 입력 : N(1

문제는 다음과 같다. https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 우선 여기서 주목해야할 세가지가 존재한다. A : 고정비용 B : 노트북 생산 비용 C : 노트북 판매 비용 아마 필자를 포함한 대부분의 사람들이 처음에는 반복문을 통한 해결방법을 생각했을 것이라 생각한다. 하지만 잘 생각해 보면 이 문제는 반복분에 의한 시간복잡도 O(n)이 아닌 단순 논리판단에 의한 시간복잡도 O(1)로 문제를 해결할 수 있다. 손익분기점은 판매 총 수익이 생산..

문제 출처 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net import math a,b = map(int,input().split()) for b in range(a,b + 1): if b == 1: continue if b == 2: print(b) else: boolT = True for c in range(2,int(math.sqrt(b)) + 1): # 제곱근을 통해서 나누어지는 수 검사를 줄인다. 왜냐? 수가 많아질수록 for문이 도는 속도는 더 길어지기 때문 if b % c == 0: boolT = False brea..

문제출처 : https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. www.acmicpc.net import sys donknowwhat = list(map(int,sys.stdin.readline().split())) val = None for a in range(0,2): r = list(map(int,sys.stdin.readline().split())) if val == None: val = r else: val += ..

문제 출처 : https://www.acmicpc.net/problem/1978 import sys totalNum = int(input()) vals = list(map(int,sys.stdin.readline().split())) total_count = 0 for a in vals: if a == 1: continue if a == 2: total_count+=1 else: TF = True for b in range(2,a): if a % b == 0: TF = False break else: continue if TF == True: total_count+=1 else: continue print(total_count) 일반적인 소수판별문제랑 동일하다. 기본적으로 소수는 1과 자기자신만을 약수로..

BOJ(백준 온라인저지) 2108번 통계학 코드 및 해설 백준 온라인 저지 2108번 문제 풀이 사용언어 : Python3 문제 제목 : 통계학 링크 : https://www.acmicpc.net/problem/2108 문제와 주어진 예시들 ) Code 풀이순서 우선 문제를 보면 첫번째 입력값에는 총 입력 수의 개수를 적는것이라고 되어있다. 그 후의 입력값들은 입력개수만큼 수를 입력해 주어야 한다고 한다. 우선 우리가 값을 받기 위해서는 input도 있지만 이 input 함수는 꽤 느린 속도를 가지고 있는 함수이다. 그렇게 때문에 빠른 받기가 가능한 sys모듈의 readline를 사용해 주었다. import sys s = sys.stdin.readline io = int(s()) 우선 출력해야하는 결과값..

한동안 알고리즘을 건드리지 않았다. 좀더 효율적인 코딩을 요구하는 작업들을 함에 따라 백준 새로운 계정을 만들고 문제들을 서서히 풀어 나갔다. 아침에 1교시 수업을 기다리며 1110번 문제를 풀어보았다. 막힘은 없었다. 잘 풀리겠지 하면서 말이다. 우선 1110번의 문제는 다음과 같다. 주어진 예시 입력과 출력값들은 다음과 같은것들이 있다. 필자가 초반에 작성한 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 global b global value global cycle cycle = 0 value = 0 def add_zero(num): return "0" + num #try..