분류 전체보기

퀵 정렬(quick sort)

📔 퀵 정렬(quick sort) 이란 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵이란 이름에 맞게 빠르다. 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법. 보통 재귀함수 호출을 이용하여 구한다. 기준 값(pivot)을 기준으로 그 값보다 큰 값과 작은 값을 서로 교환한 뒤 기준 값을 기준으로 두개의 리스트로 나눈다. (기준 값의 왼쪽에는 작은 값, 오른쪽에는 큰 값) 대부분의 경우에는 퀵정렬이 가장 빠르다. (c언어의 정렬 알고리즘도 퀵정렬 기반) 비교 정렬 ( 다른 원소와의 비교 ) 📔 퀵 정렬(quick sort) 예제 맨앞의 값 3을 pivot 값으로 설정했다 ( 보통 가장 앞의 값을 pivot으로 설정) pivot값..

[python] 백준 - 5014. 스타트링크

🤔문제 해결 G5 | BFS, 그래프 갈 수 있는 길이 2가지인 BFS 문제. 한 지점에서 올라가거나 내려가거나 하면서 원하는 층에 도착할 수 있는지 판별한다. 최초 시작점 S에서 올라가거나(U) 내려간다(D) 만약 올라갈 때 건물의 높이보다 높으면 못올라가고, 내려갈 때 1층보다 낮으면 못내려간다. 또 visited리스트를 만들어둬서 이미 방문했었는지 보고 방문을 안했던 층만 방문한다. BFS로 하기 때문에 이미 방문한 층에 한번 더 들르면 큰값이 들어가게 되므로 무조건 손해이다. 계속 방문을 하면서 원하는 지점(G)에 도착한다면 그 값을 리턴해주고, 도착하지 못한다면 'use the stairs' 를 리턴해준다. 💨 💻소스 코드 from collections import deque def bfs():..

[python] 백준 - 3055. 탈출

🤔문제 해결 G5 | BFS, 그래프? 단순히 최단거리를 찾는 것과 달리 맵이 계속 변하는 문제이다. 로직은 간단하다. 고슴도치를 상하좌우로 이동시킨다. 물도 상하좌우로 흘러넘친다. 다시 고슴도치를 상하좌우로 이동시킨다. (하지만 물에 잠겨있는 고슴도치는 이동할 수 없다) 다시 물을 상하좌우로 흘러넘치게한다. 위의 과정을 반복하면서 고슴도치가 굴에 도착하면 끝 💨 💻소스 코드 def flood(w): new_water = [] for x, y in w: for k in range(len(dx)): nx = x + dx[k] ny = y + dy[k] if 0

삽입 정렬(insertion sort)

📔 삽입 정렬(insertion sort) 이란 숫자를 적절한 위치에 삽입하는 방법 "필요할 경우에만" 위치를 바꾼다. 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 한 세트가 끝날 때마다 앞의 숫자들은 "정렬"된 상태이다. 📔 삽입 정렬(insertion sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 5개의 원소중 처음과 그 다음을 비교한다. 그 둘을 정렬한다. 1세트가 끝나면 앞의 숫자들(노란색)은 정렬된 상태이다. 다음 세트는 두번째 숫자부터 앞의 숫자와 비교한다. 📔 삽입 정렬(insertion sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i in range(len(numbers)-..

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..

선택 정렬(selection sort)

📔 선택 정렬(selection sort) 이란 오름차순의 경우 가장 작은 원소를 맨 앞으로 보낸다. 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 한 세트가 끝날 때마다 가장 작은 수가 맨 앞에 온다. 📔 선택 정렬(selection sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 5개의 원소중 가장 작은 숫자를 맨 앞의 숫자와 바꾼다. 1세트가 끝나면 가장 작은 수가 맨 앞으로 온다. 다음 세트부터는 맨 앞의 숫자를 빼고 비교를 해준다. (이미 가장 작은 수이기 때문) 📔 선택 정렬(selection sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i in range(len(numbers))..