전체 글

[백준-11399] ATM 파이썬, 탐욕알고리즘을 이용한 최적해 찾기

# 문제 # 풀이 탐욕 알고리즘(Greedy Algorithim)을 이용해서 최적해를 구하는 방법의 문제라고 생각했다. 탐욕 알고리즘은 현재 상황이 가장 최적이라고 생각하고 문제를 풀어나가는 방법인데, 항상 최적의 해를 구하는 것은 아니다. 때때로는 근사한 값을 구할 수 있다. 위와 같이 6이 최적이라고 판단했지만 사실은 17->23으로 가는 것이 더 최대값을 구할 수 있는 경우가 생기기 때문이다. 이번 문제에서는 위와 같은 경우는 고려하지 않았도 됐기 때문에 그냥 풀었다. for문을 두 번 돌려서 풀면 당연히 편하겠지만 시간복잡도가 O(n^2)으로 늘어나기 때문에 O(n)으로 풀 수 있는 방법이 있을까 고민했고 아래와 같이 반복문을 한번만 돌려서 정답을 구 할 수 있었다. # 코드 import sys ..

[알고리즘] DFS(깊이 우선 탐색) 파이썬

[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기 # 내용 그래프에서 많이쓰이는 넓이 우선탐색 방법(BFS) 시작 노드로부터 갈 수 있는 노드들을 차례로 방문예정 큐에 넣은 후, 방문완료 큐에 넣는다. 방문예정큐로부터 뽑아 방문하지 않았다면, devforyou.tistory.com # 내용 BFS와 같이 탐색을 하지만, DFS는 말 그대로 깊이 우선탐색이다. 노드들을 계속 타고 타고 타고 들어가는 것이라고 생각하면 된다. 재귀함수로도 구현이 가능하다는 생각이 들었다. 근데 재귀로 짜면 끝에서부터 찾아오는 느낌이 될거 같다. 물론 구현은 가능하겠지만, 적합하지는 않을거 같다는 생각이 들었다. BFS와 매우 유사하지만, 방문해야할 노드들을 스택으로 표현하냐 큐로 표현하냐에 ..

[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기

# 내용 그래프에서 많이쓰이는 넓이 우선탐색 방법(BFS) 시작 노드로부터 갈 수 있는 노드들을 차례로 방문예정 큐에 넣은 후, 방문완료 큐에 넣는다. 방문예정큐로부터 뽑아 방문하지 않았다면, 해당 노드에서 갈 수 있는 노드들을 뽑고, 방문완료 큐에 넣는 과정을 계속해서 반복하며, 더이상 방문할 노드가 없으면 끝이다. 파이썬에서는 그래프를 딕셔너리로 편하게 표현 할 수 있다. 큐를 사용해도 되고, 파이썬의 강력한 list를 사용해 큐처럼 활용 가능하다. 파이썬의 리스트가 제공하는 extend를 사용하면 리스트를 맨뒤에 연장시켜준다. # 사용 그래프 # 코드 # bfs ( 넓이 우선 탐색 ) def make_graph() : graph = dict() graph["A"] = ["B","C","D"] gra..

[백준-1920] 수 찾기 파이썬, 파이썬 한줄 입력받기 및 정수형 리스트 변환, 리스트 슬라이스 시간복잡도

# 문제 # 실패한풀이 ## 선형 탐색 선형탐색 알고리즘으로 찾았을 시에는 시간초과 오류 발생 ## 이진탐색 [알고리즘] 이진탐색 파이썬 및 시간복잡도 # 내용 정렬된 데이터 셋에서 탐색을 시도함 함수가 실행될때마다 탐색하는 범위가 반토막이 되기 때문에 순차탐색에 비해 월등히 속도가 빠름 # 코드 # 이진탐색은 데이터셋이 정렬되어 있어야 devforyou.tistory.com 저번에 정리한 내용으로 풀었으나 시간초과 오류 발생, 원인을 분석했을때 재귀함수가 호출할때 리스트를 슬라이싱해주는데 여기서 시간이 초과되는거 같았다. 리스트를 넘겨주지 않고 기존에 데이터를 활용하고 인덱스만 바꿔주는 방법으로 재시도했다. # 성공한 풀이 이진탐색을 똑같이 활용 했으나, 기존 리스트를 그대로 넘겨주는 방법을 사용했다...

[알고리즘] 순차탐색 파이썬 시간복잡도

# 내용 첫 인덱스부터 끝까지 하나하나 검사해가면서 탐색함. 만약 탐색되면 즉시 반환 끝까지 탐색했는데도 값이 없으면 False반환 # 코드 import random def seq_search(list,target): for i in range(len(list)) : if list[i] == target : return True return False if __name__ == '__main__': list = random.sample(range(30),10) target = 10 print(f"{list} target {target}") answer = seq_search(list,target) print(answer) # 시간복잡도 최악의 경우 n번 순회해야 하기 때문에 O(n)