안녕하세요! 뤀카입니다. 오늘은 심화 기하학 알고리즘인 볼록 껍질(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번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출..

안녕하세요? 오늘은 기초 알고리즘 중 하나인 DFS(깊이 우선 탐색)을 알아보도록하겠습니다. dfs는 백트래킹의 사용되는 알고리즘으로 스택(리스트)를 필수적으로사용해야 합니다. dfs는 한마디로 루트노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.쉽게 말하면 미로 찾기를 할 때 한 방향으로만 가다가 벽이 나오면 이전에 있는 갈림길 중 가장 가까운 갈림길로다시 돌아가는 것을 의미합니다.  다음은 예시 코드입니다. step 1 : 함수 정의def dfs(now): # 함수정의. now = 현재 정점 print(now,end=' ') #현재 정점 프린트 visited[now] = 1 # 무한 루프 돌지 않게 방문 채크 for ..