본문 바로가기

Algorithm/이것이 취업을 위한 코딩테스트다5

TIL - 2021.05.27 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적인 탐색 알고리즘으로 DFS,BFS를 꼽을 수 있다. 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조' 를 의미한다. DFS(Depth-First Search) , 깊이 우선 탐색이라고 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 먼저 들어간건 제일 늦게 나오는 FILO 구조를 지니고 있는 스택으로 구현한다. # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v,end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: .. 2021. 5. 27.
TIL - 2021.05.26 구현(Implementation) 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다 구현 유형의 예시 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 실수 연산을 다루고,특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용하는 문제 완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 문제 상하좌우 # 상하좌우 문제 n = int(input()) dx = [0,0,-1,1] dy = [-1,1,0,0] # L R U D con = ['L', 'R', 'U', 'D'] move = list(input().split()) x = 0 .. 2021. 5. 26.
TIL - 2021.05.24 입출력시 공백으로 구분된 데이터의 개수가 많으면, data = list(map(int,input(),split()) 으로 해주는 것이 좋다. 그게 아니고 데이터의 개수가 적다면 data = map(int,input(),split()) 으로 해줘도 된다. 만약에 PS 문제에서 시간초과 문제가 발생할 경우를 막기위해 속도가 최대한으로 빠른 방법도 존재한다. 외우자. import sys # 문자열 입력받기 data = sys.stdin.readline().rstrip() sys 라이브러리를 사용할 때는 한 줄 입력을 받고 나서 rstrip() 함수를 꼭 호출해야 한다. readline() 으로 입력하면 ㅇ비력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한.. 2021. 5. 24.
TIL - 2021.05.23 인덱싱(Indexing) - 인덱스 값을 입력하여 리스트의 특정한 원소에 접근하는 것 슬라이싱(Slicing) - 리스트에서 연속적인 위치를 갖는 원소들을 가져올 때 사용하는 기능. a = [1,2,3,4,5,6,7] print(a[1:4]) # RESULT [2,3,4] 슬라이싱 구동 방법. 리스트 관련 기타 메서드 메서드 명 사용법 설명 시간 복잡도 append() 변수명.append() 리스트에 원소를 하나 삽입할때 사용 O(1) sort() 변수명.sort(), .sort(reverse= True) 1. 오름차순 정렬 2. 내림차순 정렬 O(NlogN) reverse() 변수명.reverse() 리스트의 원소 순서를 모두 뒤집어 놓음 O(N) insert() 변수명.insert(삽입할 위치 인덱스.. 2021. 5. 23.
자주 접할 수 있는 시간 복잡도 알고리즘의 시간 복잡도 중에서 자주 접할 수 있는 형태로는 다음과 같은 것들이 있다. O(1) 상수 시간 알고리즘(Constant-time algorithm)의 수행시간은 입력의 크기에 영향을 받지 않는다. 상수 시간 알고리즘의 예로는 공식을 이용하여 답을 바로 계산해내는 알고리즘이 있다. O(log n) 로그 시간 알고리즘(Logarithmic algorithm)은 대체로 단계마다 입력의 크기를 절반씩 줄여나간다. n을 계속 2로 나눠가면서 1이 되도록 하는 데에 필요한 단계 수는 log2 n 이고, 따라서 이러한 알고리즘의 수행시간은 로그 시간이다. 로그의 밑수가 시간 복잡도에 나타나 있지 않음에 유의하라. O(√n) 제곱근 시간 알고리즘(Square root algorithm)은 O(log n) 보.. 2021. 3. 13.

IT_learning's Commit


티스토리툴바