본문 바로가기

알고리즘

[코딩테스트]코테 준비 및 정리 ✔️ 알고리즘 종류 1. 문제가 나왔을 때 (어려운 난이도 코테 빼고) 예상할 수 있는 유형들 - 시뮬레이션(구현) - DFS / BFS - DP - 그리디 - 이분탐색 - 최단경로 - 자료구조 구현 - 정렬 - 백트래킹 - 브루트포스 - 분할정복 - 투포인터 2. 난이도 중일 경우 예상할 수 있는 유형들 - DFS / BFS - 자료구조(힙,스택,큐,트리) - 시뮬레이션 혹은 브루트포스 - DP - 이분탐색 3. 난이도 중상일 경우 예상할 수 있는 유형들 - DP - 자료구조(트리 포함) - 투포인터 - 어려운 시뮬레이션 - 그리디 / 그래프 4. 난이도 상일 경우 예상할 수 있는 유형들 - 트리 - 어려운 시뮬레이션 - 문자열 - DP - 이분탐색 - 그리디 등등... ✔️ 문제 분석 1. 문제 접근.. 더보기
[코테 문제 유형 정리] 1. 공유기 설치 - 문제 : N개의 집이 있고(각 좌표가 주어짐), C개의 공유기가 있을 때 C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램? - 알골: 이분탐색 - 추가 해설: # min_distance = 1, max_distance = N번 집 좌표 - 첫번째 집 좌표 # mid_distance로 min과 max의 중간값을 가지고, 1번 집부터 mid_distance거리만큼 공유기를 설치했을 때 설치가능한 공유기 개수 확인 -> C개보다 크면 거리가 넘 짧은 것이므로 max 값 줄이고, C개보다 적으면 answer와 값 비교 후 min값 크게 함 2. 튜플 - 문제: n개이면서 중복 원소가 없는 튜플 (a1,a2,..an)이 주어졌을 때 집.. 더보기
[코테 정리] 0 . 시간 복잡도 입력 범위 시간 복잡도 알고리즘 500 N^3 3중 for, 플루이드 2,000 N^2 2중 for 100,000(10만) N log N 이때부터 2중 for쓰면 안됨. 20,000,000(2천만) N 100만 logN 이분탐색 - format 출력 :print( "구구단 {0} * {1} = {2} ".format( a, b, a*b) # 0,1,2는 인덱스 in 시간복잡도는 자료형에 따라 다름 -> 리스트말고 dictionary나 set이 더 짧음 if arr in set자료형 "하면 set 집합 안에 리스트 값들이 전부 들어가 있는지를 한번에 확인할 수 있다. 0-2. 구현 - DP배열에 초기값 넣을 때 항상 조심하자!!! 초기값은 보통 고정값으로 넣기 때문에 런타임에러가 발생할.. 더보기
코딩테스트 대비 백준 문제 뽀개기 : dp 0. 출처 https://covenant.tistory.com/224?category=727170 코딩테스트 대비를 위한 백준 문제 추천 코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고 covenant.tistory.com 0-2. 런타임 에러 발생 시 확인 https://blockdmask.tistory.com/550 [python] 파이썬 에러 종류 10가지 안녕하세요. BlockDMask입니다. 오늘은 파이썬에서 자주 보는 에러 종류에 대해서 이야기해보려 합니다. 우리가 코드를 작성하다 보면 빈번히 발생하는 것이기 때문에 놀라지.. 더보기
코딩테스트 대비 백준 문제 뽀개기 : 기초 백준 문제 추천 1. 수들의 합 (그리디) - 문제: 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값? https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net - 해결 과정: 1,2,3,...부터 연속된 합이 최소인 줄 알고 구간합 구하는 방식으로 투포인터 썼는데, 생각해보니 항상 연속인 값이 나올 순 없다.!!!! 1,2,3,...부터 누적합을 구하다가 1+2+3+ ...M = num > S를 처음으로 만족하게 되면, (S - num)인 숫자만 쏙 빼면 되므로 M-1을 출력한다. ----------------------------------------.. 더보기
최소 스패닝 트리(MST) 1. 스패닝 트리 / 신장 트리 - 그래프 내의 모든 정점을 포함하고 그래프의 일부 간선을 선택해서 만든 트리 - 스패닝 트리는 노드가 N개, 간선이 N-1개가 됨 - Spanning Tree는 모든 정점들이 연결 되어 어야 하고 사이클을 포함해서는 안된다. Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 2. 최소 스패닝 트리(MST) - 간선의 가중치의 합이 최소인 스패닝 트리 - 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우에 사용됨 - 알고리즘 : 크루스칼, 프림 (둘 다 그리디 기반 알고리즘) 3. 알고리즘1 : 프림 - https://www.fun-coding.org/Chapter20-prim-live... 더보기
코딩테스트 대비 백준 문제 뽀개기 : 준비운동 PART2. 약점 체크 0. 문제 출처 https://covenant.tistory.com/224?category=727170 코딩테스트 대비를 위한 백준 문제 추천 코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고 covenant.tistory.com 1. 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데.. 더보기
런타임 에러 확인 1. dp문제에서 초기값 넣을 때 N값보다 큰 값 넣었는지 확인 - N = 1일 수 있는데 dp[2] = k 값 삽입구문이 있다거나.. 2. if else 조건 제대로 넣었는지 확인 (else문 안썼다거나, if인데 elif 썼다거나) 3. 비어있는 스택, 큐에 인덱스로 접근했을 때( 인덱스 접근 전에 len(stack)을 비교 안했거나, 맨 처음 데이터가 들어왔을때 처리라거나 등등) 더보기

티스토리툴바