목록전체 글 (447)
For Programmer
7-2. 이진탐색 문제
1. 떡볶이 떡 만들기 문제 정답 코드 #떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n,m = list(map(int,input().split())) #각 떡의 개별 높이 정보를 입력 array = list(map(int,input().split())) #이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(array) result = 0 #이진 탐색 수행(반복적) while(start mid: total += x - mid #떡의 양이 부족할 경우 더 많이 자르기(왼쪽 부분 탐색) if total < m: end = mid -1 #떡의 양이 충분할 경우 덜 자르기(오른쪽 부분 탐색) else: result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기서 result 기록..
7. 이진탐색
이진탐색 알고리즘 소스코드 이진탐색 재귀적 구현 #이진 탐색 소스코드 구현(재귀함수) def binary_search(array,target,start,end): if start > end: return None mid = (start + end) // 2 #찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array,target,start,mid-1) #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: return binary_search(array,target,mid+1,end) #n(원소의 개수)과..
6-2. 정렬 문제
소스코드 나의 코드 n,k = map(int,input().split()) arrayA = list(map(int,input().split())) arrayB = list(map(int,input().split())) arrayA.sort() arrayB.sort(reverse=True) for i in range(k): if(arrayA[i] break 문을 빼먹음 정답 코드 import builtins n,k = map(int,input().split()) a = list(map(int,input().split())) b = list(map(int,input()...
6-1. 정렬(선택정렬,삽입정렬,퀵정렬,계수정렬)
1. 선택정렬 선택정렬 코드 선택정렬 시간복잡도 삽입정렬 삽입 정렬 소스코드 array = [7,5,9,0,3,1,6,2,4,8] for i in range(1,len(array)): for j in range(i,0,-1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법 if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동 array[j],array[j-1] = array[j-1],array[j] else: #앞쪽은 이미 정렬이 되어있기 때문에 자기보다 작은 데이터 만나면 그자리에서 멈춤 break print(array) 삽입정렬 시간 복잡도 퀵 정렬 소스코드 array = [5,7,9,0,3,1,6,2,4,8] def quick_sort(array,start,end): if ..
5-2. DFS&BFS 문제
#N,M을 공백을 기준으로 구분하여 입력받기 n,m = map(int,input().split()) #2차원 리스트의 맵 정보 입력 받기 graph=[] for i in range(n): graph.append(list(map(int,input()))) #DPS로 특정 노드를 방문하고 연결된 모든 노드들도 방문 def dfs(x,y): #주어진 범위를 벗어나는 경우에는 즉시 종료 if x= n or y =m: return False #현재 노드를 방문하지 않았다면 if graph[x][y] == 0: #해당 노드 방문 처리 graph[x][y] = 1 #상 하 좌 우의 위치들도 재귀적으로 호출 dfs(x-1,y) dfs(x,y-1) dfs(x+1,y) dfs(x,y+1) return True return..
5. DFS,BFS 이론
dfs 동작 예시 DFS 소스코드 예제 #DFS 메서드 정의 def dfs(graph,v,visited): #현재 노드를 방문 처리 visited[v] = True print(v,end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드가 연결된 정보를 표현(2차원 리스트) graph = [ [], #1부터 시작하기 위해 0인덱스는 빈리스트 [2,3,8], #1번과 인접한 노드 [1,7], #2번과 인접한 노드 [1,4,5], #3번과 인접한 노드 [3,5], #4번과 인접한 노드 [3,4], #5번과 인접한 노드 [7], #6번과 인접한 노드 [2,6,8], #7번과 인접한 노드..
