안녕하세요! 다시 돌아온 뤀카입니다.이번 포스팅은 제목만 보셔도 아셨겠지만 너비 우선 탐색에 대해서 다룰껍니다!아 참고로 dfs는 저번 포스팅을 참고해 주세요. https://luca1234.tistory.com/1 DFS 알고리즘안녕하세요? 오늘은 기초 알고리즘 중 하나인 DFS(깊이 우선 탐색)을 알아보도록하겠습니다. dfs는 백트래킹의 사용되는 알고리즘으로 스택(리스트)를 필수적으로사용해야 합니다. dfs는 한마디로luca1234.tistory.com bfs는 dfs랑 비슷하지만, 조금 다릅니다.어트케 다르냐면....dfs는 한놈만 끝까지 패는 애고, bfs는 골고루 한명씩 다 패는 애입니다.물론 결국 다 패는건 똑같죠 ;;그리고 직접 구현할때도 방식이 다른데요, dfs는 재귀함수를 쓰지만, bfs..

안녕하세요! 뤀카입니다. 오늘은 또다른 기초 알고리즘 '이분탐색' 에 대해서 알아보겠습니다! 어려운건 언제하냐고요? 기초가 어느정도 끝나면 고난이도 ps랑 고급 알고리즘 알려드릴테니까 걱정 마십쇼. 그나저나, 이분탐색 알고리즘은 탐색 횟수를 줄이는 시간초과 개선용이라고 해야되나? 암튼 시간 단축에 유용한 알고리즘입니다. 이 알고리즘은 후에 고난이도 문제에도 많이 나오므로 마스터를 하셔야 편합니다. 자 어떻게 하냐고요? 예시로 1부터 100까지 아무 수나 골랐다 칩시다 (저희가 맞춰야 해요). 그럼 부르트 포스로 하면 최악의 경우 100번이나 하게 될것입니다. 이제 이걸 이분탐색을 쓴다고 하면, 범위를 50 → 25 → 12 → 6 → 3 → 2 → 1순으로 비교를 하게됩니다. 그니까 전체에서 절..

투 포인터란? 배열에서 두 개의 인덱스를 사용하여 원하는 조건을 만족하는 구간이나 쌍을 찾는 알고리즘 기법입니다. 보통 정렬된 배열에서 많이 사용되며, 시간복잡도를 O(n^2) → O(n)이나 O(n log n) 수준으로 줄일 수 있습니다. 예시 문제로는 백준의 2470번 두 용액이 있는데요, 한번 풀이를 보면서 익혀 보시죠.🔗 문제 링크 풀이는 총 3단계로 나눌 수 있는데요,요약하면 다음과 같습니다. 풀이 핵심 요약배열을 정렬양쪽 포인터 사용: 왼쪽 + 오른쪽 값을 비교하며 움직임절댓값이 작은 쪽으로 갱신무슨 소리냐고요?좀 더 쉽게 알려드릴게요.배열을 정렬하고, 쭉 돌면서 왼쪽이랑 오른쪽 값을 비교하면 되요.그리고, 더 작은 쪽을 한칸 앞으로 옮기는거죠.그렇게 해서 두개가 서로 만나면 종료!참 쉽죠잉..

안녕하세요! 뤀카입니다. 오늘은 심화 기하학 알고리즘인 볼록 껍질(Convex Hull) 알고리즘에 대해서 알려드리겠습니다.볼록 껍질은 주어진 점들을 이어서 가장 큰 도형을 만드는 알고리즘입니다. 쉬워 보인다고요? 안 쉽다니까요 직접 해보세요쉽진 않습니다. 어느 정도 난이도냐면 최저가 P5이고요, 최고는... R1입니다. 참고:파이썬 설명이 많이 없더라고요. 그래서 파이썬으로 배우느라 고생해서....파이썬으로 글 쓰는 거입니다. c++은 나중에 올려드릴게요. 자 이제 본격적인 설명 하겠습니다.자 대표적으로는 그라함 스캔이 있는데요, 다음은 시뮬레이션 영상입니다.https://www.youtube.com/watch?v=Ps1idzOx6LA 어떻게 저렇게 하냐고요?ccw를 사용하면 됩니다. CCW는 점 A..

이 알고리즘은 "값의 변경이 없을때" 빠르게 구간합을 구하기 위한 알고리즘으로 시간 복잡도는 O(N) 입니다.일단 배열 a를 받아 줍니다. 예시)a = [0] + list(map(int,input().split())) #zero index사용 x 그 후, 1부터 a의 길이 번 반복하여 전에있는 값을 더해 줍니다. 예시)a = [0] + list(map(int,input().split())) #zero index 사용 xfor i in range(1,len(a)): #index error을 방지 하기 위하여 1부터 시작 a[i] += a[i-1] # 자신에다가 뒤에 닜는 값을 더함 이때 a가 [1,2,3,4,5]라고 가정하면, 다음과 같이 변경 됩니다.[1,3,6,10,15] 이제 이걸로 구간합을 구하..

문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출..