패스트터틀

https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 www.acmicpc.net 최대 2500개의 문자를 50번 확인해야된다. for( ){ for( ){ } } 최대 105000번을 검색해야한다. 이렇게 무식하게 검..

https://www.acmicpc.net/problem/1969 1969번: DNA 문제 DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 www.acmicpc.net 대충 생각해보았을때 전부다 분석하는데 걸리는 시간은 어림잡아 O(n^2) 로 예상된다. for(){ for(){ } } 가장 차이가 적다는..

https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다. www.acmicpc.net 민호는 궁금한게 많은가보다 이런걸 다 궁금해하고.. 민호가 궁금한건 자신이 각 도시마다 다른도시로 갈때 최소비용을 계산했는데 그것에 따라 최소한의 도로만 건설을 하고싶은것이다. 도시계획에 있어서도 도로건설을 어떻게 하느냐에 최소한의 예산을 사용하고 싶은경우도 있을텐데 그럴때도 이런 계획은 필요하지 않을까 싶다. A에서 ..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - Dijkstra - Floyd warshall - - Dijkstra A -> B 로 갈때 최단 경로의 수를 구하는 알고리즘이다. 우선 그전에 가중치에 대해서 알아야한다. 가중치란 꼭짓점과 꼭짓점 사이에 존재하는 변으로 그 위에 비용을 적은 숫자를 말한다. 쉽게 말해서 X에서 Y로 갈때 드는 시간, 돈, 에너지와 같이 소모될 비용에 대한 것이다. 그리고 이것을 바탕으로 X에서 Y로 가는 가중치에 대하여 최소한의 가중치를 구하는것이 다익스트라 알고리즘이다. 쉽게 말해 가장 최단 노선으로 갈경우의 비용을 계산하는것이다. 알고리즘 - 1) 가장 비용이 저렴한 정..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 www.acmicpc.net 초반에 내가 풀었던 코드이다. package GreedyAlgorithm; import java.util.Scanner; publi..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 오름차순으로 정렬후에 시작한다.(이거 안했다가 한번 틀렸다.) 복잡하게 생각할거 없이 왼쪽부터 차례대로 붙힌다고 생각하면 된다. 왼쪽부터 차례대로 붙히면서 테이프가 닿지 않으면 개수를 하나 추가하고 그다음거에서부터 다시 테이프를 붙힌다. 위의 과정처럼 너무 어렵게 생각했었지만 그냥 함정이였다. 이게 왜 그리디 알고리즘인지 모르겠다. package GreedyAlg..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30 www.acmicpc.net = weight[] = 3 1 6 2 7 30 1 1) 우선 오름차순으로 정렬을한다. = 1 1 2 3 6 7 30 2) 숫자 1이 들어있지..

https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net N>=3,M>=7이상부터는 1. 2칸 위로, 1칸 오른쪽 2. 2칸 아래로, 1칸 오른쪽 이 두방법으로 왔다갔다 하는것이 최댓값이다. 모르면 그림그려가면서 경우의수 따져보면 바로나온다. 이게 왜 그리디 알고리즘인지 모르겠다. 다들 if문으로 풀었다. package GreedyAlgorithm; import java.util.Scanner; public class _1783 { static int night_max(int n,int m){ if(n==1) retu..