문자열 재정렬 [문제] 알파벳 대문자와 숫자 (0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 예를 들어 K1KA5CB7이 입력으로 들어오면, ABCKK13을 출력합니다. [입력] K1KA5CB7 [출력] ABCKK13 [입력] FDSARQWER13579 [출력] ADEFQRRSW25 내 풀이 arr = list(input()) arr.sort() idx, digit = 0, 0 if any(map(str.isdigit, arr)): for i in arr: if i.isdigit(): idx += 1 digit += int(i) arr = arr[idx:] arr.append(digit)..

최단 경로 알고리즘 문제 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘 원론적 구현 import sys input = sys.stdin.readline() INF = int(1e9) # 무한을 의미하는 값으로 10억 설정 # 노드의 개수, 간선의 개수 입력 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for _ in range(n + 1)] # 방문한 적이 있는지 체크하는 목적의 리스트 생성 visited = [False] * (n + 1) # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1..

다이나믹 프로그래밍 문제 다이나믹 프로그래밍 조건 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다 전형적으로 보텀업(상향식) 방식을 사용 피보나치 수 단순 재귀형 O(2^n) def fibonacci(x): if x == 1 or x == 2: return 1 else: return fibonacci(x - 1) + fibonacci(x - 2) print(fibonacci(30)) DP 탑다운 O(n) # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 n = int(input()) d = [0] * (n + 1) # 피보나치 함수를 재귀함수로 구현 (탑다운 형식..

이진 탐색 알고리즘 문제 이진 탐색 알고리즘 def binary_search_recursive(arr, target, stt, end): if stt > end: return None mid = (stt + end) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return binary_search_recursive(arr, target, stt, mid - 1) else: return binary_search_recursive(arr, target, mid + 1, end) def binary_search_loop(arr, target, stt, end): while stt target: end = mid - 1 else: stt = m..

정렬 알고리즘 문제 정렬 알고리즘 선택 정렬 # 선택 정렬 arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index = i for j in range(i + 1, len(arr)): if arr[min_index] > arr[j]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] print("선택 정렬 :", arr) 삽입 정렬 # 삽입 정렬 arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(arr)): # i-1까지는 정렬되어 있다고 가정 for j in range(i, 0, -1): if arr[j] < arr[..

DFS / BFS 탐색 알고리즘 문제 깊이 우선탐색 graph = [[0], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]] visited = [False] * 9 def dfs(v, graph, visited): visited[v] = True print(v, end=" ") for node in graph[v]: if not visited[node]: dfs(node, graph, visited) dfs(1, graph, visited) 너비 우선탐색 from collections import deque visited = [False] * 9 graph = [[0], [2, 3, 8], [1, 7], [1, 4, 5], [3..