DFS를 공부하면서 관련 문제를 풀어보는데 분명 vscode에서 실행해보면 답은 제대로 나오는데 백준에서 제출하면 런타임 에러가 발생했다. 👿 하루코딩에서 풀이해주는 영상도 보았는데 코드에는 틀린 부분은 없는 것 같았다. 그래서 구글링해보니 파이썬에서는 재귀의 최대 깊이의 기본 설정이 1,000회로 설정되어있어서 재귀를 사용하는 경우에 런타임 에러가 발생하는 경우가 있다고 한다. 그래서 아래 코드와 같이 작성하면 재귀의 깊이를 변경해주면 에러를 해결할 수 있다. 괄호 안의 숫자를 필요에 따라 다르게 설정하면 된다. import sys sys.setrecursionlimit(10 ** 6) 그런데 나는 위 코드를 추가해주었는데도 런타임에러가 발생하였다. setrecursionlimit의 숫자를 높여도 런타..
프로그래머스 레벨1 문제인 달리기 경주 문제에서 테스트 9 ~ 13번까지 시간 초과 에러가 발생했다. 아직 문제를 풀기 전 시간복잡도를 고려하는 것이 익숙하지 않아서 생긴 에러 였다. 내가 처음 작성한 답안은 아래와 같다. def solution(players, callings): for name in callings: n = players.index(name) players[n], players[n-1] = players[n-1], players[n] return players 결과값은 정답과 맞게 나오지만 시간초과 에러가 나오는 걸로 봐서는 index() 함수나 swap해주는 부분에서 문제가 있을 것 으로 예상된다. 하지만 swap해주는 부분보다는 index() 함수가 시간복잡도에 더욱 연관이 있을 ..
1️⃣ 버블 정렬 (Bubble) loop를 돌면서 인접한 데이터 간의 swap 연산을 통해 정렬하는 방식 - 시간 복잡도 : O(n^2) - 다른 정렬 알고리즘보다 속도가 느린 편 N개의 데이터를 정렬한다고 가정하면, 루프를 한번 돌때마다 맨 뒤에 데이터부터 하나씩 픽스해 나간다. → 루프를 한번 도는데 N번의 비교를 하니 N의 시간복잡도를 가진다. → 그 루프를 N번 돌아야 모든 데이터가 정렬된다. 한 번 도는데 N의 시간복잡도를 가지는 루프를 N번 도니까 버블정렬의 시간복잡도가 n^2이다. 버블 정렬 구현 과정 말로 풀어 써보기 1) 비교 연산이 필요한 루프 범위를 설정한다. 2) 인접한 데이터 값을 비교한다. 3) swap 조건에 부합하면 swap 연상을 수행한다. 4) 루프 범위가 끝날 때까지 ..
1️⃣ 구간 합 합 배열을 이용하여 시간 복잡도를 줄이기 위한 알고리즘 합 배열 S S[i] = A[0] + A[1] + ... + A[i-1] + A[i] 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 합 배열을 구하는 방법은 S[0] = A[0] S[i] = S[i-1] + A[i] 예를 들어, 배열 A와 배열 A의 합 배열 S는 다음과 같다. A = [1, 2, 3, 4, 5] S = [1, 3, 6, 10, 15] 구간 합을 구하는 방법 배열 A의 인덱스 i부터 j까지의 구간 합을 구하고 싶다면 S[j] - S[i-1] 예를 들어, A = [15, 13, 10, 7, 3, 12] 라는 배열에서 A[2]부터 A[5]까지의 구간 합을 구하면 S[5] = A[0] + ..
1️⃣ DFS (깊이 우선 탐색) 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노트에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐새을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 (완전 탐색이란 그래프에 있는 모든 노드를 탐색하는 것) 특징 - 재귀 함수로 구현 - 스택(Stack) 자료구조 이용 - 시간 복잡도는 O(V+E) V : 노드 수, E : 예지 수 깊이 우선 탐색을 응용하여 풀 수 있는 문제 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬, ... DFS 핵심 이론 DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다. 그래프는 인접리스트로 표현하고, 스택을 사용하여 DFS를 구현해보자. 1) 시작 노드를 ..
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다. 그래서 시간 복잡도는 코딩테스트를 풀 때 어떤 알고리즘을 사용할지에 대한 선택의 기준이 된다. 예를 들어, 파이썬 프로그램에서는 2,000만번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있으므로 연산 횟수와 수행 시간을 고려하여 어떤 알고리즘을 써야할지 생각해 볼 수 있다. 물론, 시간 복잡도만으로 어떻게 문제를 풀지 선택하는 것은 아니지만 데이터의 갯수에 따라 시간 복잡도를 계산할 줄 알면 써야하는 알고리즘의 범위를 좁힐 수 있게 된다. 시간 복잡도 표기법 시간 복잡도를 정의하는 3가지 유형이 있다. 빅-오메가 Ω(n)최선일 때(best case)의 연산 횟수를 나타낸 표기법빅-세타 θ(n)보통일 때(ave..
