코젤브

[01강 - 기초 코드 작성 요령 I] 0. 시간, 공간 복잡도 1) 시간복잡도 2) 공간복잡도 1. 정수 자료형 1) char 2) short, int, long long 3) Integer Overflow 2. 실수 자료형 -> float(4byte), double(8byte) 1) 실수의 저장/연산 과정에서 반드시 오차 발생 2) double에 long long 범위 정수 함부로 담기 X 3) 실수 비교 시 등호 X[정리] 정수 자료형 char (signed : -128~127 / unsigned : 0~255) short (signed :..

문제를 풀기 전 파이썬에서 리스트를 정렬하는 방식에 대해 간단하게 알아보자! sort() 리스트를 제자리에서(in-place) 수정하는 내장 함수원본을 정렬하고, 수정한다.리스트에게만 정의그리고 리턴값이 None 이다.L.sort()reverse 매개 변수로 내림차순(True) 정렬 지정 가능sorted() 이터러블로부터 새로운 정렬된 리스트를 만드는 내장 함수리스트에서만 정의되는 것이 아니라 모든 이터러블을 받아들임리턴값이 정렬된 값이다.L2 = sorted(L1)reverse 매개 변수로 내림차순(True) 정렬 지정 가능 두 함수 모드 오름차순과 내림차순을 위해 불리언 값을 갖는 reverse 매개 변수를 받음reverse=True 로 지정시 내림차순 정렬 프로그래머스코드 중심의 개발자 채용. 스택..

오늘은 이어서 탐색 알고리즘 DFS, BFS 에 대해 공부하겠다! 더보기 사실 차근차근 진도를 나가면서 블로그에 정리하려고 했으나, 항상 밀려서 급하게 정리한다. 알고리즘 개념에 해당하는 간단한 세미코테 문제들도 곧 올리겠다! 탐색 알고리즘 : 리스트/배열 내에서 특정 원소를 탐색하는 방법 DFS, BFS를 공부하기 전, Stack과 Queue의 자료구조와 그래프에 대해 간단하게 복습하자. 자료 구조 데이터를 표현 관리 처리하기 위한 구조 Stack : 선입후출 구조 먼저 들어온 것이 나중에 나간다 first in last out (FILO) Queue : 선입선출 구조 들어온 순서대로 나간다 first in first out (FIFO) 그래프 유한개의 꼭지점 Vertex의 집합 V와 두 꼭지점을 원소..

💡 내용 순차탐색 이진탐색 보간탐색 속도 비교 탐색 알고리즘 : 리스트/배열 내에서 특정 원소를 탐색하는 방법 순차 탐색 가장 기본적인 탐색 알고리즘 주어진 데이터를 찾기 위해 처음부터 하나씩 차례로 확인 시간복잡도: O(n) 단점 : 데이터가 큰 경우에는 적합하지 않음 장점 : 데이터가 작거나 중간 정도는 적당 / 미리 정렬 필요 X L=[9,8,1,2,7,3,6,4,5] def LinearSearch(L, n): for i in range(0, len(L)): if L[i] == n: return i return -1 print(LinearSearch(L, 3)) Binary Search (이진 탐색) 배열 내부 데이터가 정렬되어 있어야만 사용 가능 배열 크기 작으면 효율적이지 않음 각 단계에서 배열..

알고리즘 : 어떤 문제를 해결하기 위한 정해진 절차 정렬 알고리즘 : 데이터를 특정 기준에 따라 순서대로 나열 naive sort : 선택 정렬 가장 작은 원소를 찾아 맨 앞으로 이동 그 다음 작은 원소를 찾아 두 번째로 이동 위 과정의 반복 시간복잡도: O(n²) L=[4,2,1,0,5,3,6] def sort_list_naive(L): nlen= len(L) for i in range(0, nlen): idx = i for j in range(i+1, nlen): if L[idx]>L[j]: idx = j L[i], L[idx] = L[idx], L[i] return L print(sort_list_naive(L)) insert sort : 삽입 정렬 현재 위치 이전은 정렬되어 있다 가정하고, 이후의..

- Big O 표기법 = worst와 비슷 : 점근적 상한 : 궁극적으로 이것보단 좋다(=기울기가 같거나 낮다) - Ω 표기법 : 점근적 하한 : 아무리 좋아도 이것보다 좋아질 수 없다(=기울기가 높다) - Θ 표기법 : 점근적 협소 : 차수가 같다(=기울기가 같다) - Small o 표기법 : 차수가 작다(=기울기가 낮다) (같을 수 없다) - 차수의 주요 성질 g(n) ∈ O(f(n)) f(n) ∈ Ω(g(n)) g(n) ∈ Θ(f(n)) f(n) ∈ Θ(g(n)) 로그 복잡도 함수는 모두 같은 카테고리 => Θ(lg n) 지수 복잡도 함수는 모두 같은 카테고리 X n! 는 어떤 지수 복잡도 함수보다 나쁨 좋은 것부터 나열 n c ≤ 0, d > 0 일 때, g(n) ∈ O(f (n)), 그리고 h(..

- 강좌의 목표 : 설계, 분석, 계산적 복잡도(문제 자체의 복잡도) - 알고리즘 : 각 단계가 명확하게 정의되고 실행이 가능한 유한 시간대에 종료되는 어느정도의 일반성을 가진 일련의 절차 - 알고리즘의 요구조건 유한시간 내 종료 termination 명확성 definiteness 실행 가능성 executableness 기타: 일반성 generality - 프로그램 설계 과정 - 문제의 표기 방법 - 문제: 답을 찾고자 던지는 질문 - 파라미터(parameter): 문제에서 특정값이 주어지지 않은 변수 - 문제의 사례(입력): 파라미터에 특정 값을 지정한 것 - 사례에 대한 해답(출력): 주어진 사례에 관한 질문에 대한 값 - 알고리즘의 표기 : C++에 가까운 의사코드 사용 (자연어, 프로그래밍 언어 ..

백준 2750번 문제를 합병 정렬과 퀵 정렬로 각각 풀어보자. * 재귀 알고리즘: 큰 문제를 작은 문제로 쪼개고 작은 문제의 해답을 return하면서 큰 문제의 답에 접근하는 알고리즘 백준 2750번: 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 합병 정렬 : 리스트를 분할하여 정렬하고 합병 // 합병 정렬 알고리즘 코드 void merge(int list[], int left, int mid, int right) { int i, ..