욤미의 개발일지

[Python] 리스트 자료형 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용할 수 있으며, C나 자바와 같은 언어의 배열(array) 기능을 포함한다. 내부적으로는 연결 리스트 자료구조를 채택하고 있으며 C++의 STL vector와 유사하다. 리스트 대신 배열 혹은 테이블 이라고 부르기도 한다. a = list() # 빈 리스트 선언1 a = [] # 빈 리스트 선언2 a = [0] * 10 # 모든 값이 0이고 크기가 10인 1차원 리스트 초기화 리스트 메서드 함수명 사용법 설명 시간 복잡도 append() 변수명.append() 원소를 하나 삽입할 때 O(1) sort() 변수명.sort() / 변수명.sort(reverse=True) 기본 정렬 기능, 오름차순 정렬 / 내림차순 정렬 O(..

1. Array / Linked List 둘 다 데이터를 저장하는 선형 자료구조인데 그 목적과 장단점이 다르기 때문에 어떤 걸 사용하느냐에 따라 프로그램의 성능이 달라진다. 1) Array (배열) 특징 인덱스-원소값( index,value )의 쌍으로 구성 같은 타입의 데이터를 나열한 선형 자료구조 (sequence container) 데이터의 논리적 순서와 물리적 주소가 일치하며 항목을 연속된 메모리 공간에 순차적으로 저장 배열의 크기는 고정. 선언할 때에 배열의 크기를 정하고, 변경할 수 없다. Complie time에 연속된 메모리 주소를 할당받는다. (Stack 영역에 정적 메모리 할당) 시간 복잡도 배열의 맨 앞에 삽입/삭제하는 경우 : O(n) 배열의 중간에 삽입/삭제하는 경우 : O(n) ..

[Python] 수 자료형 정수형과 실수형 정수형은 정수를 다루는 자료형으로 양의 정수, 음의 정수, 0 이있고 실수형은 소수점 아래의 데이터를 포함하는 수 자료형으로 파이썬에서느 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 자동으로 처리한다. 정수부 혹은 소수부가 0인 경우에는 생략하고 작성할 수 있다. a = 200 print(a) # 200, 양의 정수 b = -10 print(b) # -10, 음의 정수 c = 0 print(c) # 0, 0 d = 15.75 print(d) # 15.75 양의 실수 e = -16.58 print(e) # -16.58 음의 실수 f = 5. print(f) # 5.0, 소수부 0 생략 g = - .7 print(g) # -0.7, 정수부 0 생략 지수표현 a..

탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. 자주 등장하는 유형이기때문에 꼭 숙지해야한다! 1. DFS(Depth First Search) 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 혹은 재귀함수를 이용한다. 동작 과정 탐색을 시작하는 노드를 스택에 삽입하고 방문 처리 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2, 3번의 과정을 수행할 수 없을 때까지 반복한다. def dfs(graph, v, visited): visite..

보통 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 그러나, 고차원적인 사고력을 요구하지는 않는 경우가 많아서 문법에 익숙하다면 오히려 쉽게 풀 수 있는 유형. 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데 파이썬은 상대적으로 쉽게 해결할 수 있다. 완전 탐색 시뮬레이션 코딩 테스트에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다. 보통 C/C++보다 파이썬은 동작 속도가 느린데, 내 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 시간제한에 안정적이다. 시간제한 1초, 데이터 개수 100만 개인 문제는 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘으로 풀어야 한다. (예를 들어 N = 1,000,000..

그리디 알고리즘: 탐욕법, 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 시간상으로 매우 효율적이지만, 순간마다 최선의 선택을 하는 방법으로 항상 최적화되지 않음으로 최종 답이 최적이 아닐 가능성이 있다. 그 때문에 순간의 최적해가 전체 문제의 최적해가 되어야 사용할 수 있다. 사전에 외우고 있지 않아도 풀 가능성이 높은 문제 유형이지만, 많은 유형을 접해보고 훈련해야 한다. 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요! 그 대상이 무엇인지 고민해보고 푸는 것이 중요하다. ex) 가장 큰 순서대로, 가장 작은 순서대로 등,,, 정렬 알고리즘과 짝을 이루어 자주 출제된다.