본문 바로가기

알고리즘

재귀 부터 어떻게좀 해보자 제발 재귀 진짜 난 왤케 재귀가 어렵지? 원래 재귀가 더 쉽고 간단하다는데 진짜 열받네 아오아오아오. 재귀 당연히 그냥 지가 지부르면 재귀이다. 재귀는 패턴이 있다고 한다. 그냥 인자로 들어오는거 변화시켜서 다시 본인함수를 호출해주는것이다. 예시1 def function(인자): if 인자 > 일정값: #인자가 일정 값 이상이면 return function(인자 -1) # 인자를 변화시킴 else: return 특정값 예시2 def function(인자): if 인자 더보기
DFS BFS 컨닝페이퍼 bfs를 처음으로 접하고 bfs를 쭉풀고 아직 dfs를 많이 안풀어서그런지 bfs가 훨씬 편하고 익숙하다. 하지만 알고리즘왕 문명주 말로는 dfs를 꼭 이용해야 풀수있는 문제들이 있다고한다 억울하다 그래도 왠만해서 둘다 풀리는거 같긴하다. 일단 둘의 팁은 bfs든 dfs든 그 원리 생각해서 문제마다 맞게 하나하나 꺼내서 넣고 이런거 적용하면되는데 시간복잡도 너무 생각안하면 문제생길수있다 다른조건에서 막 3중for문 돌리고 이러면 시간초과 걍나는거다 그리고 조건을 매우 잘봐야한다 한번도 bfs던 dfs던 안돌고 끝나는것도있고 자연스럽게 큐에 뭐가 안들어가서 끝나는경우도 있으니 끝나고 난다음에 조건을 판단해보는것도 생각하고 그리고 일수는 리스트로 묶어서 그걸 하루치로 큐에 넣는것도 있다 어쨋든 잘응용해야 할.. 더보기
dfs 제대로 정리 단순 탐색의 방식만 달라질뿐이지 어짜피 모든 정점을 탐색하는것은 같다. 한마리도 bfs는 need_visited 큐와 visited큐가 있었는데 그것중 need visited 를 스택으로 바꿔주면 되는것이다. 동작 방식은 bfs랑 유사하다. 원래 큐에서 빼는 방식이 스택으로 뺴는 방식으로 바뀌었을뿐 그리고 중복검사도 visited 큐에 담을떄 해주는것도 똑같다. 스택에 넣을떄도 들어가있는 즉 연결되어있는 방향 어디로 탐색할지 상관없다 그냥 탐색하면된다. 즉 그냥 스택에 물려있는 노드들 넣어주면됨 그냥 진짜 큐가 스택으로 바뀐거 빼고는 다른거 하나 없음 바로 코드 구현으로 해보자. dfs는 스택 쓴다는걸 알면되는데 스택 자체가 그냥 원래 컴퓨터 구조상 스택으로 돌아가기 떄문에 그냥 재귀만들어서 쭉열어주면 .. 더보기
BFS 제대로 정리 BFS: 너비우선 탐색 그래프를 맹목적으로 탐색하는것이다 시간복잡도는 노드수:V 간선수: E 이떄시간복잡도는 O(V+E) 이다. ->단순 탐색방법으로 문제에 어떻게 적용하는가가 중요하다. 사용하는 문제유형 그래프의 모든 정점을 방문할시 최단거리 문제의 경우 BFS -> 최단거리 DFS 쓰면 최단거리 아닐수있음 BFS가 DFS보다 더빠름 대체적으로 BFS가 더 복잡함 일단 근데 그래프 자료구조 뭐로 쓰는데? ->뭐 어쩌구 저꺼구 제끼고 파이썬에서는 걍 딕셔너리 자료형에 리스트를 넣어서 구현한다. -> 인접 리스트 기반 그래프 key value A B C B A D C A G H I D B E F E D F D G C H C I C J J I 요렇게 하면됨 key 값이 각 노드들 그리고 그 value 값으로.. 더보기
이진탐색 컨닝페이퍼 이진탐색 일단 기본개념으로 lower bound,upper bound arr = [1, 2, 3, 3, 5, 6, 6, 8, 9, 10] left, right = 0, 9 target = 8 answer = -1 while left = target: #요기 >=를 >로 바꾸면 upper bound answer = mid right = mid - 1 else: left = mid + 1 print(answer) # 7 lower bound 코드다 -> >= 를 >로 바꾸면 upper bound 이분탐색 쓸거같은 냄새나는거 일단 이분탐색 그냥 뭐 큰숫자 찾는 이런 개념이아니라 그냥 탐색할때 대체적으로 많이 적용할수있는거같음 -> 이런거는 근데 아직까지 쉽게 적용을 못해봄 근데 이분탐색 자체가 시간복잡도가 O.. 더보기
그리디(greedy) 컨닝페이퍼 greedy라 아주 맘에 드는 이름이다.-> 내 식성과 비슷한거같다 후후후 근데 뭔가 이름이 거창하지만 진짜 별거 없는거같다 그리고 이따구로 푸는게 맞나싶다 그냥 기도 메타랑 다를께 뭔데 그냥 단계단계별로 최고 좋은 조건 고르고 최적해와 맞기를 기도하는거다 그래서 최적해가 아닐수있고 정확히 말하자면 최적해임을 검증하는 과정이 필요하다. 그래서 근사값을 뽑아낼수있는 하나의 전략이라고 보면된다. 근데 우리는 풀기만 하면 장땡이니까 좀 애매하면 써봐서 풀리면 좋은거지뭐 그리디 알고리즘의 특징은 극단적인걸 좋아하는데 -> 무조건 큰경우부터 , 무조건 작은 경우부터, 무조건 긴 경우 부터, 무조건 짧은 경우부터 이런식으로 문제를 접근할때 극단적인 시각으로 접근하면된다 . 그래서 정렬과 함께 사용하는 경우가 많다... 더보기
Bruteforce를 위한 순열,조합 컨닝페이퍼 자 이제 짐승같이 문제를 풀기위하여 Bruteforce를 하는데 일단 많이 나오는 순열,조합,중복순열,중복조합 각각 무슨라이브러리 임포트 해야하는지 어느건지 한줄 설명 간다. -> 이거 안하면 맨날 잊어버려 ㅠㅠ 아 맞다 시간복잡도 까지해서 n몇 넘으면 박살나는지도 적어야겠다 순열 뭐써야하는가? -> permutations import itertools a = [1,2,3,4] res = itertools.permutations(a, 2) 순서를 고려해서 뽑는 경우의수 -> 서로다른 n개에서 r개를 택하여 일렬로 나열하는 경우의 수. -> 이거는 앞뒤 순서 관계까지 고려한거 ex)(1,2) (2,1) 이 다른거 5개에서 3개 뽑는다면 5x4x3 = 60 임 123에서 2개 뽑는경우 (1, 2) (1, 3.. 더보기
파이썬 자료구조 컨닝페이퍼 각 자료구조들 파이썬의 무엇을 이용해서 구현하는지에 대한 간단한 컨닝페이퍼다. 각 자료구조의 기본 함수들의 시간복잡도도 정리했다(어디서 가져왔다) 배열 그냥 당연히 List 써라 파이썬 공부하면 알꺼아냐 딕셔너리 dictionary 쓰면 될것이다. 링크드 리스트 파이썬은 링크드 리스트 그냥 쓰면된다 리스트 자체가 배열의 단점 (크기 고정) 이런거 다 해결되어있다 -> 배열 이어붙이기,중간삽입,삭제 이제 트리 같은거 만드려고 node 같은거 쓰는 것들은 나중에 정리해야겠다. 리스트 쓴다면 위의 시간복잡도 참고하면 될것이다. 스택 그냥 push,pop,top 가 빠르면 스택으로 쓰면되고 파이썬에서는 리스트 쓰면된다 -> 파이썬의 리스트 시간복잡도 찹고해보자 각 기능에대한 파이썬 함수 큐 collections.. 더보기

티스토리툴바