![]()
문제는 다음과 같다. https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 우선 여기서 주목해야할 세가지가 존재한다. A : 고정비용 B : 노트북 생산 비용 C : 노트북 판매 비용 아마 필자를 포함한 대부분의 사람들이 처음에는 반복문을 통한 해결방법을 생각했을 것이라 생각한다. 하지만 잘 생각해 보면 이 문제는 반복분에 의한 시간복잡도 O(n)이 아닌 단순 논리판단에 의한 시간복잡도 O(1)로 문제를 해결할 수 있다. 손익분기점은 판매 총 수익이 생산..
![]()
이진검색(Binary Search)에 대해 알아보자. 이진검색 또한 검색 기법중 하나이다. 단 전제조건이 하나가 존재한다. 이진검색을 사용하기 위해서는 해당 배열의 데이터가 정렬(sort)되어있어야 한다. * 결론적으로 이진검색인 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있도록 도와주는 알고리즘이라는 것이다. 예시를 하나 들어 [5,7,15,28,29,31,39,58,68,70,95] 라는 리스트가 있고, 나는 여기서 39라는 값을 검색하고 싶다고 가정하자. 가정하자. 우선 검색 범위의 시작 인덱스를 pl, 끝 인덱스를 pr, 중간 인덱스를 pc라고 부르기로 약속하자. 과정에 대한 사진은 다음과 같다. 1) 우선 초기 검색범위는 당연히 처음(index 0)부터 끝(index ..
![]()
선형 검색 알고리즘(Linear Search Algorithm)에서 종료조건은 두가지가 존재한다. 1) 검색할 값을 찾지 못하고 배열의 맨 끝을 지나갔는가? -> 검색실패조건 2) 검색할 값과 같은 원소를 찾았는가? -> 검색 성공 조건 종료를 위해 이 두가지를 항상 검색하는데, 이 과정을 계속해서 반복하다 보면 종료조건을 검사하는 '비용(cost)'를 무시할 수 없다. 우선 기본적으로 검색 대상인 sequence가 있다면 그 sequence 맨 끝에는 검색하고자 하는 key값을 넣어준다. 여기서 sequence맨 끝에 넣어주는 이 검색하려는 key값을 '보초'라고 한다. 만약 원래 seqeunce에 자신이 찾으려는 key값이 존재하지 않는다면, 스캔 인덱스는 원래 sequence의 길이와 동일해 질 것..
문제 출처 : 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과 자기자신만을 약수로..
![]()
코드 링크는 아래에 있습니다(queue.ipynb) https://github.com/J-hoplin1/Python-DataStructure/blob/master/Queue.ipynb 큐(Queue)란 스택과 달리 항목이 들어온 순서대로 접근이 가능한 FIFO(First In First Out, 선입선출)구조이다. 큐 또한 배열 인덱싱을 통한 접근이 불가능하다. 가장 쉽게 생각하면 우리가 줄서는 것을 생각해보면 된다. 큐 또한 스택과 동일하게 다양한 동작들이 있으며 이 또한 O(1)의 시간복잡도를 가지게 된다. - enqueue : 큐 뒤쪽에 항목을 삽입한다. - dequeue : 큐 앞쪽의 항목을 반환 후 제거 - peek : 큐의 앞쪽 항목 조회 - empty : 큐가 비었는지에 대해 확인 - siz..
BOJ(백준 온라인저지) 2108번 통계학 코드 및 해설 백준 온라인 저지 2108번 문제 풀이 사용언어 : Python3 문제 제목 : 통계학 링크 : https://www.acmicpc.net/problem/2108 문제와 주어진 예시들 ) Code 풀이순서 우선 문제를 보면 첫번째 입력값에는 총 입력 수의 개수를 적는것이라고 되어있다. 그 후의 입력값들은 입력개수만큼 수를 입력해 주어야 한다고 한다. 우선 우리가 값을 받기 위해서는 input도 있지만 이 input 함수는 꽤 느린 속도를 가지고 있는 함수이다. 그렇게 때문에 빠른 받기가 가능한 sys모듈의 readline를 사용해 주었다. import sys s = sys.stdin.readline io = int(s()) 우선 출력해야하는 결과값..
![]()
파이썬에서 만약 배열 원소들을 역순으로 나열해서 작성해야하는 문제가 있다고 가정하자. 필자는 이와같은 문제를 풀다가 Extended Slice라는 기본 개념을 놓쳤기에 이 포스팅을 통해 바로 잡고 가려고한다. 형태는 다음과 같다. ARR[q:w:e] : index q부터 index w 까지 e간격으로 만들겠다 이러한 형태를 띄고 있는것이 Extended Slice라고 한다. 이를 직접적으로 연계시켜 생각할수 있는 문제는 밑에 링크를 참조하자. https://www.acmicpc.net/problem/2908 2908번: 상수 문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 ..
![]()
한동안 알고리즘을 건드리지 않았다. 좀더 효율적인 코딩을 요구하는 작업들을 함에 따라 백준 새로운 계정을 만들고 문제들을 서서히 풀어 나갔다. 아침에 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..
![]()
Big - O Notation, 흔히 말하는 O표기법이란 최악, 최선의 성능중 최악의 성능에 해당한다. 최악의 성능을 평가하는 이유는 적어도 일정정도의 성능은 보장한다는 의미이다. O 표기법은 알고리즘의 성능을 평가하기 위해 처리해야할 데이터의 양에 대한 실행시간을 수학적 으로 계산한 방법이다시간 복잡도 함수에서 알고리즘 분석을 원활하게 하기 위해 시간 복잡도를 표기하는것을 Big -ONotation이라고 한다. 다음과 같은 for문이 있다고 가정하자. 이 루프 제어문은 n개의 대입연산과, n+1번의 비교연산, n번의 덧셈 연산을 포함하여, 총 3n + 1개의 연산이 생긴다. 추가적으로 루프문 내에서는 n번의 덧셈연산과, n번의 대입연산, 총 2n이 발생하여 해당 루프문은 최종적으로5n+1 이라는 연산을..
![]()
(Codes : https://github.com/J-Hoplin/Algorithm-with-Python/tree/master/4%20.%20Double%20Linked%20List)1 . Doubly Linked List 앞에서 보았던 연결리스트는 단일 연결 리스트(Singly Linked List)였다. 연결리스트는 배열과 같이 물리적 메모리적 메모리가 아닌 링크라는 형식의 개념을 사용하기에 관리하기가 매우 쉬웠다. 하지만 단일 연결리스트의 한계가 있다. 바로 일방성이라는것이다. 한방향으로만 나아갈 수 있을뿐 그와 반대방향으로 링크를 시킬 수 없다는 단점이 존재한다. 앞으로 볼 이중 연결리스트는 단일 연결리스트와 달리 양방향성을 지니고 있다.다음 사진을 보자. 임의의 링크는 자신의 다음 링크도 가리키..
