목록알고리즘 (92)
라떼는말이야
문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 N번째 감소하는 수를 출력한다. 나의 풀이 문제에서 0은 0번째, 1은 1번째 감소하는 수라고 했다. 즉, 한 자릿수는 모두 감소하는 수라고 할 수 있다. 2 자릿수 이상부터는 마지막 숫자보다 그 뒤에 붙는 숫자가 작아야 한다. 어떤 리스트에 감..
문제 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, C가 주어진다. 출력 첫째 줄에 공백으로 구분하여 답을 출력한다. 각 ..
월요일이 공휴일이라 안 올라오길래 이번 주에는 문제가 안 올라오나 싶었는데 다시 확인해보니 문제가 올라와있던... 382번째로 풀이했습니다. ( MANGBAAM ) 도움이 되었다면 좋아요 부탁드려요~ 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주..
계수 정렬은 특정한 조건에서 가능한 정렬 알고리즘이다. 특정한 조건만 만족한다면 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠른 알고리즘 중 하나이다. 계수 정렬의 시간 복잡도는 무려 O(N + K)이다. (N: 데이터의 개수, K: 데이터 중 최대값) 계수 정렬의 조건 데이터의 크기 범위가 제한된 경우 ex) 0 ~ 100 까지의 점수를 정렬하는 경우 데이터가 양의 정수인 경우 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않는 경우 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐 계수 정렬의 정렬 방법 계수 정렬은 버블 정렬, 병합 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬 ..
DFS의 용도 깊이 우선 탐색은 BFS와 마찬가지로 그래프를 방문하거나 탐색하는 방법 중 하나이다. 2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현 BFS (너비 우선 탐색, Breadth First Search) 최단 거리, 최소 비용과 같이 최솟값과 관련된 문제 해결에 사용. 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. 모든 경로에 대한 동시 탐색 latte-is-horse.tistory.com DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수 (그래프의 최대 경로)가 정해져 있거나 예측 가능한 경우에 주로 사용한다. DFS의 과정 방문한 정점에..
BFS (너비 우선 탐색, Breadth First Search) 최단 거리, 최소 비용과 같이 최솟값과 관련된 문제 해결에 사용. 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. 모든 경로에 대한 동시 탐색 가능. 최대 경로를 몰라도 사용 가능 → 최단 거리, 최소 비용 등을 구하기 좋다. 큐(Queue) 사용. → FIFO 구조 절차 저장된 정점 중 첫 번째 정점을 선택하여 저장된 정점에서 제거 제거한 정점에서 해야 할 작업 진행 제거한 정점과 연결된 정점 중 방문하지 않은 모든 정점 저장(2, 3번은 순서가 바뀌어도 됨) 저장된 정점에 모든 노드가 제거될 때까지 1~3번 과정 반복 1번 정점 탐색 시작 시작 정점을 저장한 뒤 방문 표시(회색 처리). 첫 번째 단계로 저장된 첫 번째..
투 포인터(two pointer) 배열에서 두 개의 포인터를 이용해 양 끝에서 탐색해 나가며 답을 찾는 방식 Q. 주어진 배열에서 합이 27인 경우를 찾아라 최초에 맨 끝인 1과 28을 가리킨다. 찾아야 하는 값(27)이 29보다 작으므로 오른쪽 포인터를 하나 감소시킨다. (1, 25 가리킴) 찾아야 하는 값(27)이 26보다 크므로 왼쪽 포인터를 하나 증가시킨다. (3, 25) 찾아야 하는 값(27)이 28보다 작으므로 오른쪽 포인터를 하나 감소시킨다. (3, 22) 찾아야 하는 값(27)이 25보다 크므로 왼쪽 포인터를 하나 증가시킨다. (5, 22) 찾아야 하는 값(27)이 두 포인터가 가리키는 값의 합과 같으므로 5와 22를 return 한다. 또 다른 순서쌍이 존재할 수 있으니 계속 진행한다. ..