홍시홍의 프로그래밍

요구사항 N(1 ≤ N ≤ 10,000,000)개의 숫자를 정렬하라 참고 1. 정렬의 하한은 NlonN 이다 -> 정렬로 구성할 수 있는 결정트리를 만들게 되면 리프 노드의 개수가 logN! = NlonN인 결정 트리를 만들 수 있다 -> 그 중에 하나가 정렬된 상태이다 -> 그러므로 NlogN이 정렬이 하한이다 2. 10,000,000을 정렬의 하한을 적용시켜 보면 제한시간안에 문제를 풀 수 없다 ->그러므로 정렬이 아닌 다른 방법으로 풀이를 진행하여야 한다 3. 주어진 숫자의 범위가 작으니깐 각 숫자가 몇번 나왔는지 출력한다 풀이 import sys input= sys.stdin.readline n=int(input()) arr= list(range(10010)) #입력을 받을 때 마다 해당 arr을..

요구사항 수의 개수가 1 ≤ N ≤ 1,000,000개 일 때, 정렬하기 참고 퀵 정렬 구현하여 문제 풀이를 진행하였다. 퀵 정렬은 피벗을 기준으로 왼쪽에는 작은 값 오른족에는 큰 값을 오게 만들어 재귀를 통해 정렬하는 것이다 풀이 import sys arr=[] n=int(input()) for i in range(n): arr.append(int(sys.stdin.readline().rstrip())) def QuickSort(left, right, arr): #left 가 클 경우 종료 if(left>=right): return i = left j = right pivot = arr[(left+right)//2] #i, j가 교차 하면 종료 while(i 교환해야함 while(arr[i] 교환해야함..

개념 그래프 내에서 시작 정점 부터 원하는 정점까지 이동가능한지 알아보는 알고리즘이다 하나의 분기에 도달했다면 그 분기에 대해서는 탐색할 수 있는 모든 경로를 탐색하고 넘어가는 알고리즘이다 사용하는 곳 A에서 B로의 이동 가능 여부 전자회로에서 연결 여부 시간 복잡도 인접 행렬의 경우 O(n^2) 인접 리스트의 경우 O(n+m) 구현방법 백트래킹을 사용해 구현한다 특징 너무 깊을 경우에는 모든 정점을 다 깊게 탐색하므로 다른 알고리즘을 사용하는것이 현명하다

요구사항 대문자 문자열 가져오기 참고 구현 string 풀이 문자열 입력을 받은 후, 특정 문자를 기준으로 리스트로 바꾼다 문자열 -> 리스트 첫번째 문자는 대문자라는 조건이 있으니 첫번째 문자만 출력해준다 n= list(input().split('-')) ans='' for i in n: ans+=i[0] print(ans)