Cohe

공부한 내용 그래프 그래프 용어 정리 그래프의 특징과 종류 흐름을 표현하는 방향성 방향 그래프 : 방향이 있는 간선이 있는 그래프 무방향 그래프(비방향 그래프) : 방향이 없는 간선이 있는 그래프 흐름을 정도를 표현하는 가종치 가중치 그래프 : 가중치가 있는 그래프 시작과 끝의 연결 여부를 보는 순환 순환그래프 : 순환이 있는 그래프 비순환 그래프 : 순환이 존재하지 않는 그래프 그래프 구현 그래프 예시 ex) 서울에서 부산으로 유동인구 8000명 데이터를 담고 있는 노드(서울, 부산) 노드를 잇는 간선(서울과 부산의 연결 유뮤) 간선의 방향 (서울에서 부산 방향으로) 간선의 가중치(유동인구 8000명) 그래프의 구현 방식에는 인접 행렬과 인접 리스트가 있다 인접 행렬 그래프 표현 보통 배열 사용 노드는..

공부한 내용 해시 : 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조, 인덱스(보통은 키)를 활용 ex) 전화기록부 (이름(key)-전화번호(value)) 해시의 특징 단방향 동작 : 키를 통해서만 값을 찾을 수 있음! 값을 통해 키를 찾을 수 없다. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기위한 탐색 과정이 필요치 않다. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다. 해시의 특성을 활용하는 분야 비밀번호 관리 : 값(value)를 바로 외부에 공개하지 않으므로 보안에 이용한다. 네트워크 보안에도 이용된다. 데이터베이스 인덱싱 블록체인 : 각 블록은 이런 블록의 해시..

큐 줄을 서다라는 뜻으로 FIFO 형식이다. 큐의 ADT 연산 boolean isFull() boolean isEnpty() void push(item Type item) 상태 int fromt init rear : 최근에 푸쉬한 데이터의 위치를 기록합니다 itemType data(maxsize) : 큐의 데이터를 관리하는 배열, maxsize개의 데이터를 관리 큐의 세부동작 isFull() 연산으로 현재 큐가 가득 찼는지 확인가득차지 않았으므로 rear+1한 다음 rear가 가리키는 위치에 푸쉬함이 상태로 팝을 한다면?isEmpty() 연산을 내부에서 수행비어 있지 않다면 front +1 수행 -> 1번은 이미 진행한 상황이면 rear, front 모두 0으로 같아진다이 경우 isEmpty() 연산을 ..

공부한 내용리스트를 활용해서 스텍을 표현할 수 있어야 함.각 메서드의 시간복잡도가 정리되어야 함 스택 -> 가장 최근의 값이 필요할 때 ex) 괄호 짝맞추기스택을 활용하는 경우 https://cafe.naver.com/dremdeveloper/1001문제출처 : https://cafe.naver.com/dremdeveloper/1001

05 배열 공부한 내용 배열 기초 인덱스와 값을 일대일 대응하는 자료구조 선언 방법 #1. 일반적인 방법 arr = [0, 0, 0, 0, 0, 0] arr = [0] * 6 # 2. 생성자를 사용하는 방법 arr = list(range(6)) # [0, 1, 2, 3, 4, 5] # 3. 컴프리헨션(comprehension)을 활용하는 방법 arr = [0 for _ in range(6)] # [0, 0, 0, 0, 0, 0] 배열과 차원 배열은 차원과는 무관하게 메모리에 연속 할당됨! 1차원배열 : 간단한 형태 2차원배열 : 1차원 배열 확장 형태 # 2차원 배열을 리스트로 표현 arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] # arr[2][3]에 저장된..

03 알고리즘 효율 분석 알고리즘 선택의 기준 : 시간복잡도 시간복잡도란? 알고리즘의 성능을 나타내는 지표, 입력 크기에 대한 연산 횟수의 상한 의미 -> 낮으면 낮을수록 좋다! 1차원 배열에서 예시 최선 : 1회 비교 최악 : 배열의 개수만큼 비교 알고리즘 수행 시간 측정 방법 절대 시간 측정 방법이 있지만 코테에서는 추천하지 않음!! (프로그램을 실행하는 환경에 따라 달라질 수 있음!) 시간 복잡도 측정 결과에 따라 최선, 보통, 최악으로 나뉨, 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방식을 점근적 표기법이라고 함 빅오 표기법 - 점근적 표기법 중 상한선 활용 방법 - 연산 횟수가 f(x)일 때 함수의 최고차항만 남기고 차수를 지워 O(g(x))와 같이 표기 - 그래프를..