본문 바로가기
반응형

코테털기

[ 알고리즘 ] 백트래킹 1. 개념 해를 찾다가 해가 아니어서 막히면, 되돌아가면 다시 해를 탐색하는 방법. DFS의 일종. 모든 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 방법. 가지치기. --> 최적화 문제와 결정 문제일 때 2. 방법 DFS 등으로 모든 경우의 수를 탐색할 때, 조건으로 절대 해가 아닌 경우일 때는 탐색을 중단하고 그 이전으로 돌아가, 즉 '백트래킹'해서 다른 경우를 탐색하는 방법으로 주로 구현. 주로 재귀로 구현하다가 조건이 맞지 않으면 종료. 3. 예제 https://www.acmicpc.net/problem/15651 n, m = map(int,input().split()) l = [] def dfs(num): if len(l) == m: for i in l: print(i, end = '.. 더보기
[ 알고리즘 ] BFS (너비 우선 탐색) 1. 개념 '너비 우선 탐색' 깊게보다 넓게 탐색. 시작 노드에서 인접한 노드를 먼저 탐색하는 방법 --> 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 2. 방법 큐(Queue, FIFO)를 사용해서 구현하면 된다. 1) 우선 방문해야할 정점을 넣을 queue 선언, 방문 정점(v)으로 초기화 2) 현재 방문한 곳은 노드 방문 처리 3) queue 안에 데이터 있는 동안 반복 -1) queue에서 pop해서 방문 정점(v)에 넣고 출력 -2) 반복문 실행해서 방문 정점과 인접한 정점 찾아서 queue에 append --> 방문하지 않았고, 현재 방문 정점인 v와 인접해있으면 queue에 넣어주고, 방문처리 해준다. 3. 예제 4. dfs와의 비교 n에 대한 반복문을 실행하면서 방문하지 않.. 더보기
[ 알고리즘 ] 완전 탐색 (브루트 포스) 1. 개념 말 그대로 '완전 탐색'. 모든 경우의 수를 탐색한다. 장점 - 쉽고, 빠르게 구현할 수 있다. 단점 - 시간과 공간(메모리)적으로 매우 불리하다. --> 따라서 모든 경우의 수를 탐색하되, 각 경우에서 쓸데없는 연산을 하지 않는 것이 중요하다. break 잘 때려주기! 2. 분류 1) 선형구조 - 배열(선형 리스트), 연결리스트(Linked List), 스택, 큐, 데크 - 데이터가 연속적으로 연결되어 있는 모양의 구조 - 포인터 등을 사용해서 자료를 연결하면, 자료가 일직선상에 표시되거나 하나의 원 상에 표시되는 구조 --> 순차탐색 2) 비선형구조 - 트리, 그래프 --> 백트래킹, DFS, BFS 3. 예제 - 백준 2798 블랙잭 https://www.acmicpc.net/proble.. 더보기
[파이썬] python EOF (입력 끝날 때까지 출력하기) 입력이 끝날 때까지 읽어들이려면 except (예외처리)를 이용하면 된다. 정상적일 때는 try 문의 내용을 수행하다가 오류가 발생하면 except 문의 내용을 처리한다. 아래와 같이 사용하면 된다. 아래의 코드는 입력이 끝날 때까지 입력을 받아서 그대로 출력하는 코드이다. while True: try: n = input() if n == "": break print(n) except: break 더보기
[Python] 파이썬에서 0과 1 반전시키는 방법 사실 파이썬 뿐 아니라 모든 코딩에서 사용이 가능한 방법이다. 문제를 풀다보면, 0이면 1로, 1이면 0으로 바꾸는 문제가 많다. 이 때, 굉장히 쉬운 방법이 있다. 1에서 해당 수를 빼주면 된다. cur[i] = 1-cur[i] 더보기
[코테] 복잡도 - 시간복잡도, 공간복잡도, 프로그램 수행 시간 측정(파이썬) 0. 시간 복잡도와 공간 복잡도 - 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 - 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 1. 시간복잡도 코딩테스트에서 시간복잡도는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미. (메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 메모이제이션 기법 존재) 빅오(Big-O) 표기법 : 시간 복잡도를 표현. 가장 빠르게 증가하는 항만을 고려하는 표기법. ex) 2중 반복문의 경우에는 O(N^2) ex) 퀵 정렬은 O(NlogN) - 최악의 경우 O(N^2) - 빅오 표기법과 N이 1,000일 때의 연산 횟수 빅오 표기법 명칭 N이 1,000일 때의 연산 횟수 O(1) 상수 시간 (Constant ti.. 더보기
[코테] 코딩테스트 TIP 참고도서 : 이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈) 1. 온라인 저지 사이트 목록 - 해외 : 코드포스 / 탑코더 / 릿코드 / 코드셰프 - 국내 : 백준 온라인 저지 / 코드업 / 프로그래머스 / SW Expert Academy * 코드업은 국내의 한 정보 교사가 알고리즘 교육을 목적으로 운영하는 사이트. 난이도가 낮은 문제가 많아서 초보자에게 적합. [문제] - [문제집]에서 [기초 100제] 꼭 풀어보기 * 백준 : [문제] - [알고리즘 분류]에서 유형별 알고리즘 선택해서 풀 수 있음. 2. 개발 환경 - 온라인 : 리플릿(Repl.it) / 파이썬 튜터 / 온라인 GDB (디버깅 기능 제공) - 오프라인 : 파이참 3. 자주 출제되는 문제 유형 - 구현 - DFS/BFS - .. 더보기
반응형

티스토리툴바