Algorithm/이론5

• [파이썬] '그리디' 개념 및 예제 그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 코딩테스트에서의 그리디 유형 - 창의력, 문제를 풀기 위한 최소한의 아이디어 떠올릴 수 있는 능력 요구 특정 문제 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 풀 수 있을 지 파악! ( 코테에서 어떤 문제가 바로 유형을 파악하기 어려우면 그리디 의심! 만약 그리디 해결방법 찾을 수 없다면, 다이나믹이나 그래프 알고리즘으로 해결할 수 있는지 고민) 그리디 알고리즘은 기준에 따라 좋은 것을 선택하므로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. -> 대체로 정렬 알고리즘 사용하면 됨! 짝꿍 :) 간단한 예시 - 거스름돈) n=1260 # 총 거스름돈 count=0 # 큰 단위인 500원 부터.. Algorithm/이론 2021. 2. 23.

• [파이썬] '최단경로' 개념 및 예제 그리디와 다이나믹 프로그래밍이 그대로 적용! 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다, 단순히 최단 거리를 출력하는 문제 많이 출제됨! 최단거리 알고리즘 종류) 1. 다익스트라 최단거리 2. 플로이드 워셜 => 1,2가 많이 출제됨 3. 벨만 포드 1. 다익스트라 - 그래프의 노드 중 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로 구함 - '음의 간선 없어야함' - 그리디 알고리즘에 속함 ( 매번 '가장 비용 적은 노드' 선택하므로) 원리) 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 (무한대로) 3. 방문 안 한 노드 중 최단거리 가장 짧은 노드 선택 ( 우선순위 큐를 사용하여 간단히 가능) 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 .. Algorithm/이론 2021. 2. 9.

• [파이썬] '다이나믹 프로그래밍' 개념 및 예제 다이나믹 프로그래밍 => 한번 계산한 문제는 다시 계산 X !! (중복 줄이기) 언제 사용? 1. 큰 문제를 작은 문제로 나눌 수 있을 때 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 다이나믹 프로그래밍과 분할 정복과의 차이점: 분할은 하지만, 서로 영향을 끼친다 (중복이 있음) ex) 피보나치 수열을 재귀적으로 처리하면 n이 커질수록 수행 시간 너무 커짐. # (재귀) 피보나치 def fibo(X): if x==1 or x==2: return 1 return fibo(x-1)+fibo(x-2) -> 탑다운 (큰 문제 해결을 위해 작은 문제 부름) 한번 구한 결과는 저장해두었다가 그대로 불러오자 ( 메모이제이션 기법 => 캐싱 ) #(재귀-메모이제이션) 피보나치 d= [0]*100.. Algorithm/이론 2021. 1. 6.

• [파이썬] '정렬' 개념 및 예제 이것이 취업을 위한 코딩 테스트다 with 파이썬 강의 참고 1. 선택 정렬 O(N^2) 현재 범위 내에서 가장 작은 데이터 선택해서 맨 앞의 데이터와 변경. (범위 : 앞으로 데이터를 보내면서 남은 만큼) ->제일 작은거 맨앞으로 보내고, 남은 것 중 작은거 앞에서 두번째로 보내고, 남은 것 중 작은거 앞에서 3번째로 .. * 마지막 경우는 처리 안해도 됨. array= [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min=i #가장 작은 원소 인덱스 for j in rnage(i+1 , len(array)): if array[min] > array[j]: min=j array[i],array[min] = array[min], array[i] # swap # .. Algorithm/이론 2021. 1. 6.

• 

  [파이썬] 'DFS/BFS' 개념 및 예제 DFS - 깊이 우선 탐색 (스택 사용) 동작 과정) 1. start 노드 스택에 삽입 후 방문처리 2. 스택 최상단 노드에 방문하지 않은 인접 노드 있다면, 그 인접 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드 없으면, 스택에서 최상단 노드 꺼냄 3. 2번 과정 더이상 수행할 수 없을 때까지 반복 예시) def dfs(graph, v , visited): visited[v] = True # 현재 노드 방문 처리 print(v, end =' ') for i in graph[v]: # 현재 노드와의 인접노드들 재귀적으로 dfs 처리 if not visited[v]: dfs(graph, i , visited) # 각 노드가 연결된 정보를 2차원 리스트로 표현 graph =[ [], [2,3,8],.. Algorithm/이론 2021. 1. 6.