Odds and Ends

문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한 사항 n은 2 이상 100,000 이하인 자연수입니다. 입출력 예 n return 3 2 5 5 문제 풀이 : 재귀 함수 문제로 봤다가는 시간 초과 에러가 뜬다. ..

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..

CPU-I/O Burst 사이클 : 프로세스 실행은 CPU 실행과 I/O 대기 사이클로 구성된다. (CPU 버스트로 시작되고 뒤이어 I/O 버스트가 발생함) - 마지막 CPU 버스트는 또 다른 입출력 버스트가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다. CPU 스케줄러 - 준비 큐(ready queue)에 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다. (좋은 프로세스 > CPU를 바쁘게함) ** 준비 큐(ready queue)는 반드시 선입선출 방식의 큐가 아니어도 된다. CPU 스케줄링을 결정하는 4가지 상황 1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (ex. I/O 요청, 자식 프로세스 종료) > 자진 반납 2. 프로세스가 실행상..

이분탐색이란? : 이진탐색이란 '정렬된 자료'를 반으로 쪼개가며 원하는 값을 찾아가는 탐색 알고리즘 * 가운데 지점(mid)을 찾고, 계속 left, right 값을 mid를 이용해 갱신하면서 범위를 좁혀나가는 알고리즘 최선: O(1) 평균: O(log N) 최악: O(log N) >> 데이터가 한 개 남을 때 까지 찾는 경우가 최악 # 이분탐색 알고리즘 (정방향) def BinarySearch(arr,target): #L: left, R: Right, M: Mid L,R = 0, len(arr)-1 while(L R 되면 탈출 (배열에 target이 없다) M = (L + R) // 2 if(arr[M] == target): # target값에 해당하는 idx 찾음 return M elif(arr[M]..

[Overview - 1] 📌 스레드란? > 실행되는 흐름 : CPU 이용의 기본 단위 - 제어 흐름 표현 - 스레드 ID, 프로그램 카운터 (PC), 레지스터 집합, 스택으로 구성 - 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유 - Single threaded program: 1 process에 1 thread (하나의 프로세스에 실행흐름은 하나, main thread 1개) [싱글 스레드 > 멀티스래드] 스택 공유 안함 : 실행 시 로컬 변수가 따로따로 만들어 주어야함 함수 단위로 스레드 만듦. > 3함수 3스레드(실행흐름 3개) 스레드 간 서로 공유하는 것 : 코드, 데이터, 파일, 전역변수 기본적으로 공유. * 프로세스는 대략적..

Union-Find란? Union-Find의 개념 서로 중복되지 않는 부분 집합 (Disjoint Set = 서로소 집합 자료구조)을 표현할 때 사용하는 자료구조 초기화 / 합치기 (Union) / 찾기 (Find) 세 가지 연산을 사용한다 최소 스패닝 트리를 구현하는 크루스칼 알고리즘에 사용되며, 사이클을 만들지 않고 모든 노드를 방문할 수 있다 Union-Find의 구현 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화한다 -> 각각을 유일한 원소로 가지는 집합 생성 Union (합치기) : 두 원소 a, b 가 각각 속한 두 집합을 하나로 합친다 -> 두 개의 집합을 하나로 연결하는 역할 Find (찾기) : 원소 a 가 주어질 때, 이 원소가 속한 집합을 루트노드를 반환한다 -> a..

합병 정렬 (Merge sort) 란? : 분할정복과 재귀알고리즘을 이용한 정렬로, 주어진 배열에서 수가 하나밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기순으로 재배열(정렬) 하며 원래 크기의 배열로 합치는 정렬방법입니다. 합병정렬의 시간복잡도 : O(nlogn) 합병정렬의 공간복잡도 : O(N) 구현 - 파이썬 코드 sublist = [3,23,7,12,5,8,1] def mergeSort(list): size = len(list) if size 0 and len(list2) > 0: if list1[0] 0: merged += list1 if len(list2) > 0: merged += list2 return merged sorted = mergeSort(sublist) print (sor..

CHAP 04 Process 📌 프로세스 개념 * Process란? 메인 메모리에 로드되어 실행중인 프로그램 [프로세스 요소 5가지] 💡코드 섹션 (텍스트 섹션) : 기계어 코드, 실행 코드 💡데이터 섹션 : 전역 변수 (프로그램 실행 중 필요한 data) 💡스택 : 함수를 호출할 때 임시 데이터 저장장소, 로컬 변수 💡프로그램 카운터 : 마이크로 프로세서에 있는 레지스터, 다음 실행될 명령어 주소를 가지고있어 실행할 기계어 코드의 위치 지정 💡힙: 실행중에 메모리 요청하면 힙 메모리를 할당해줌 [프로세스 메모리 배치] 📌 프로세스 상태 : 프로세스는 실행되며 상태가 변한다. 상태는 그 프로세스의 현재 활동에 따라 정의된다. 프로세스는 다음상태 중 하나에 있게 된다. 1. new : 프로세스 생성 중 2..