코딩못하는사람

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 1.접근 바이러스가 퍼진다는 것을 보면 DFS를 쓰면 되겠다는 생각이 든다. 조건으로 0인 부분에 벽을 3개 세워야 한다고 하니 itertools의 combination을 이용해서 0인 부분으로 3개의 모든 조합을 만들고 모든 상황을 DFS 해보고 제일 바이러스가 적게 퍼지는 상황을 구하면 되겠다. 2.풀이 우선 배열을 입력받고 행과열 양끝에 벽이 있는 것처럼 1로 입력을 감싸준다. 다음으로 배열을 돌면서 0인 부분과 2..

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 1.접근 문제에서 요구하는 것은 원래의 최단경로를 제외한 길에서의 최단경로이다 따라서 다익스트라를 활용하여 최단경로를 구한 후 그 경로들을 제거해준후 다익스트라를 다시 돌리면 될것이다. 2.풀이 문제풀이 방법을 생각보다 간단하고 구현에서 시간이 걸린다. 접근에서 말한 것 처럼 다익스트라로 최단경로를 구해준다. 근데 여기서 중요한 것은 최단경로가 여러개 있을 수 있다는 것이다. ..

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1.접근 문제의 표를 보면 꼬리를 무는 사이클을 찾아야하는 것을 알 수 있다. 따라서 DFS나 while문을 통해 돌면서 사이클이 생기는 곳을 체크해주면 되겠다. 2.풀이 문제의 사이클에 대해서 생각해보자. 어느 부분에서라도 DFS를 통해 들어갔을때 꼬리를 물어서 사이클이 생기지 않는다면 방문했던 곳들은 어디서 들어가도 사이클이 생기지 않을 것이다. 하지만 어느 부분에서라도 사이클이 생기는 곳이라면 들어갔을 때 자기..

위상정렬 (Topological Sort) 위상정렬은 순서가 정해져있는 작업을 수행할 때 그 순서를 결정해주기 위해서 사용되는 알고리즘이다. 순서가 정해져있다는 말은 조건이 걸린다고 생각하면 편하다. 어떠한 작업은 어떠한 이전작업들이 수행되야 수행된다라는 순서가 정해져있는 것이다. 그림을 생각해야 이해가 편하므로 그림을 보자. 각 정점들은 자신을 가르키고 있는 모든 정점들이 수행된 후에 실행될 수 있다. 가르켜 지고있는 수를 차수(degree)라고 하자. 예를들어 정점2는 정점1 하나가 가르키고 있으므로 차수는 1이다.6번은 4,5로 인해 2이고 1번은 0이 될 것이다. 그렇다면 가능한 순서를 임의로 정해보자 1->2->3->4->5->6->7도 가능할 것이고 1->2->3->5->4->6->7 등등 순..

18809 Gaaaaaaaaaarden www.acmicpc.net/problem/18809 1.접근 초록색과 빨간색 조합을 써야하므로 itertools 모듈에 combination을 써주고 경우의 수가 너무 많으므로 백트래킹을 활용한 BFS로 최대 꽃개수를 구해보자 2.풀이 combination을 사용해서 해볼 경우의수를 모두 BFS함수에 넣는다. BFS를 초록색을 돌리는 큐와 빨강색을 돌리는 두개의 큐로 나눠서 풀었다. 우선 방문한곳을 체크하는 visited함수를 -1로 초기화하고 몇번째날에 들어가는지(cnt)로 갱신한다. 우선 초록색을 돌리면 큐에서 꺼낸좌표가 flower이면 continue 좌표가 n,m범위에 있고 바다가 아니며 visited가 -1이면 언제 방문했는지 visited에 cnt를 넣..

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리가 검색을 할 때 자동으로 완성시켜주는 단어들을 보면 트라이가 사용된 예입니다. 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간복잡도를 갖고 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이의 형태 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"} 가 존재할 때 트라이의 예입니다. 다음과 같은 모양으로 트리를 만들어서 연산을 문자열의 길이만큼하는 시간복잡도를 갖게하는 것입니다. 이에 따라 트리의 특징은 시간이 O(M)..

KMP 알고리즘이란? 우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다. 알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는 N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다. 하지만 KMP알고리즘은 O(N+M)정도로 줄여준다 KMP알고리즘에는 두가지 함수가 필요하다 전처리 테이블 KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다 접두사와 접미사 같을때의 최대길이를 저장해주는 것이다 코드로 구현하면 다음과 같다. KMP 함수구현 이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다 그림으로 보면 3번 인덱..

CCW ( Counterclockwise) 말 그대로 시계 반대 방향이다. 외적을 이용하여 유도할 수 있다. CCW알고리즘을 이용하여 세점의 방향성을 알 수 있다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 출처: https://jason9319.tistory.com/358 [ACM-ICPC 상 탈 사람] 각각의 점을 A(x1, y1) , B(x2, y2), C(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면, CCW 함수의 return값은 x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 이 된다.(신발끈 공식과 같다) RETURN값이 음수이면 시계방향. 양수이면 반시계방향. 0이면 세점이 평행하다. 이 알고리즘을 이용하여..

플로이드-와샬 알고리즘 다익스트라 알고리즘이 한 정점에서 모든 정점까지의 최단거리를 구해주는 알고리즘이라면 플로이드-와샬 알고리즘은 모든정점에서 모든정점으로의 최단거리를 구해주는 알고리즘이다. 다이나믹 프로그래밍을 기반으로 거쳐가는 정점을 기준으로 한다는 특징이 있다. 다익스트라와 다른점은 다익스트라는 힙을 이용하여 일차원 배열에 값을 나타냈으므로 입력을 받을 때 adj[시작점]=(가중치,목적지)를 받았다면 플로이드는 2차원배열 adj[시작점][목적지]=가중치로 저장한다는 차이가 있다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. 식으로 설명해보자면 현재의..

벨만-포드 알고리즘 다익스트라와 마찬가지로 SSP알고리즘인 벨만-포드 알고리즘은 음의 가중치를 다룰 수 있다. 그런데 다음과 같이 음의 가중치로 인해 순환 구조를 가진다면 최단경로를 구할 수 없다. 따라서 벨만-포드 알고리즘은 최단경로를 구하는 것과 이 그래프에서 최단경로를 구할 수 있는지 없는지를 판별하는 과정 두 과정으로 나눠진다. 벨만 포드 알고리즘은 V-1번 모든 간선을 Relax하는 작업을 수행한다. 최단경로구하기 동작과정은 각 정점들을 돌아 가면서 모든 간선들을 탐색한다, 단 맨 처음은 시작점부터 탐색한다( 처음 이후에는 순서 상관없음) D(s,v)=D(s,u)+w(u,v) 이 과정을 V-1번 탐색하는 이유는 s에서 v까지 가는 경우에서 v를 뺀 모든 경로가 각각 최단거리일 수 있기 때문이다(..