코딩테스트 문제풀이/코딩테스트 알고리즘5 [코딩테스트] 파이썬 기초지식 코딩테스트 대비 파이썬 기초지식 ※ 시간복잡도 ※ 시간제한이 1인 경우 ※ 시간과 메모리 측정 import tume start_time = time.time() # 측정시작 # 프로그램 소스코드 end_time = time.time() # 측정종료 print("time :", end_time - start_time) # 수행시간 출력 ※ 온라인 개발환경 리플릿(Repl.it) 파이썬 튜터(Python Tutor) 온라인 GDB(Online GDB) ※ 수행시간을 빠르게 하는 입력 # 상단에 추가 import sys input = sys.stdin.readline ※ dfs vs bfs DFS BFS 동작 원리 스택 큐 구현 방법 재귀 함수 큐 자료구조(while queue) 사용 적은메모리 최소비용 / .. 2021. 3. 26. [alice] 자료구조의 끝판왕 알고리즘을 위한 자료구조 [4장 자료구조의 끝판왕] 프로그램의 핵심: 되풀이 비슷한 일을 여러번 되풀이해서 풀어내기 반복(Iteration): for, while 재귀(Recursion) 재귀(Recursion) 스스로를 호출하는 방식의 반복법 식의 종료 조건 필요(=Base 조건) ex) factorial(n) = n * factorial(n-1) [실습- 팩토리얼] 동적 프로그래밍(Dynamic Programming) 재귀 + 정보 저장 (메모이제이션) 저장 값을 다른 자료 구조에 저장 [실습- 피보나치] 트리 나무 형태의 자료구조 부모노드 -> 자식노드 방향으로 연결이 존재 루트(root): 부모x 노드 리프(leaf): 자식x 노드 트리의 깊이(Depth): 루프-리프까지의 경로의 길이 루트는 1.. 2020. 8. 9. [alice] 심화된 자료구조 알고리즘을 위한 자료구조 [3장 심화된 자료구조] 연결 리스트(Linked List) 여러개의 노드들이 한 줄로 연결 노드 = 저장할 데이터 + 다음 노드로의 연결 1) 단순 연결 리스트 한 방향으로만 이어진 연결 리스트 2) 이중 연결 리스트 양쪽 뱡향으로 이어진 연결 리스트 ※ 다음 노드로의 연결 -> 꼭 한 데이터를 가르키지 않아도 ㄱㅊ 3) 원형 열결 리스트 가장 뒤의 노드가 맨 앞의 노드에 연결된 연결 리스트 4) 기타 연결 리스트 아무 형태의 연결 리스트 모두 가능 [배열 vs 연결 리스트] 배열: 인덱스를 이용해서 데이터 접근 연결 리스트: 현재 노드에서 연결된 노드로만 head: 시작노드 tail: 끝 노드 None: 마지막노드(노드가 더이상x) [시간 복잡도] 자료 중간에 추가/삭제 : .. 2020. 8. 9. [alice] Big-O, 문제풀이 효율적인 프로그램이란? 시간복잡도 : 알고리즘에 사용되는 총 연산횟수 공간복잡도 : 알고리즘에 사용되는 메모리공간의 총량 ※ 입력변수의 크기 : N -> 코드의 시간복잡도 = f(N) Big-O : 시간복잡도 함수의 가장 높은 차수 반복문 : 한번 중첩마다 O(N) list 다돌면 : O(N) set : O(N) sort() : O(NlogN) 매번 절반씩 입력값이 줄어들면 : O(logN) - 시간복잡도 인덱스를 알 때 : O(1) 인덱스를 모를 때 : O(N) 배열을 전부 순회 : O(N) 자료끝에 추가 : O(1) 자료중간에 추가 : O(N) 2020. 7. 19. [alice] 개념 & 문제풀이 알고리즘을 위한 자료구조 alice 온라인 --> '알고리즘을 위한 자료구조' 여기에다가 기록하기로 하겠다.ㅎㅎ 자료구조 : Data Structure 데이터를 저장할 때 필요한 구조 ex) int, str, float, array, hash, stack, tree.... 알고리즘 : Algorithm 프로그램을 어떻게 실행 -> 계산절차 적절한 입력 적절한 출력 명확성 : 코드의 사용목적 정확 유한성 : 무한루프 x 효율성 자료구조 --> 알고리즘 : 자료구조를 활용하여 어떤문제를 해결? 2020. 7. 17. 이전 1 다음 반응형
