조용하지않는개발Blog

https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 먼저 y축 정렬 후에 같은 경우 x축 정렬을 해주면 된다. Arrays.sort를 이용하여 정렬을 시도하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보고 조합 문제겠구나 생각했다. 하지만 조합을 정확히 모르면 풀수없는 문제이기에.. 수학공부를 해야겠다. 싶었다. 각 종류 별 옷이 기에 n+1C1 의 조합으로 곱해주면 된다. 예시를 통해 보면 headgear:hat, turban eyewear: sungl..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 모든 노드의 최단 거리를 알아내는 문제이다. 이문제는 플로이드 워셜 알고리즘을 이용하면 쉽게 풀 수 있었다. 그래서 문제이름도 플로이드? 하지만 플로이드 워셜을 몰라도 풀수는 있겠지만 알고있으면 좀더 쉽게 풀 수 있을것으로 생각이 든다. 이것도 알고리즘에 작성할 필요가 있다. import sys input = sys.stdin.readline n = int..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 스택을 이용하여 풀수있는 단순한 문제였다. 다만 구현하면서 어떻게 구현을 해야하는지 생각을 많이 해야해서 골드 5이지 않을까 생각이 든다. import sys input= sys.stdin.readline n = int(input()) n_list = list(map(int,input().split())) stack=[] result = [0]*n for..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 통해서 겹치는 구간을 없애기만 하면 되는 문제이다. 다시 말해서 최장 증가 부분 수열(LIS)로 문제를 풀면 된다. 다음에 관련해서 알고리즘을 작성해놓아야 좋을듯하다. 두가지 방식으로 풀었는데 dp와 이분탐색으로 문제를 해결하였다. import sys input = sys.stdin.readline n = int(input()) n_list = [] for..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체가 짧지만 단순하게 풀면 어렵고 다이나믹 프로그래밍으로 풀면 그나마 쉽게 풀 수 있는 문제이다. 처음에 풀 때, 반복문, 재귀를 이용해야하나 고민했는데 그러면 너무 많은 시간이 걸릴 것 같아서 포기했다. 그래서 dp로 10001이 담긴 리스트를 생성하고 가치가 낮은 동전을 넣고 그다음으로 가치 높은 동전을 넣어가면서 ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제 자체는 어렵지 않은 문제였습니다. 처음에 보고 그래프로 푸는 문제인가?! 하고 생각했는데 보니까 최소값인 치킨집을 선택하고 집에서 거리를 계산하여 최소가 되는 길이를 찾는 형식의 문제였습니다. 또한 n,m의 최대가 50, 13 이여서 반복이 조금 들어가도 시간 초과는 안나겠다는 생각을 가지고 편하게 풀었습니다. 먼저 그래프에서 치킨집과..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 첫번째부터 IOI가 나오는지 비교하면서 있다면 IO만큼 2칸씩 이동한다. 그리고나서 다시 IOI가 나오는지 비교하면서 그때 n의 개수와 IOI 나온 개수가 일치하면 결과값으로 1개씩 추가하고 IOI나왔던 개수를 1개 빼주는 형식으로 진행한다. IOI가 아니면 다시 초기화 해주는 느낌으로 문제를 ..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 딕션너리를 이용하여 찾는 문제이다. 리스트를 이용하여 저장하고 찾게 된다면 2중 for문을 통해 찾아야 하기에 많은 시간이 소모 된다.시간 초과가 나올 가능성이 높음. 하지만 딕션너리를 사용하면 O(n)이기 때문에 빠르게 문제를 풀 수 있다. import sys input= sys.stdin.readline n,m= map(int,..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 전체적으로 읽고 예제 입력, 출력을 보고 이해하고 풀 수 있었던 문제이다. 단순하게 푼다면 정렬을 하면서 풀수있겠지만, 그렇게 푼다면 정렬할때마다 시간이 소요되기에 시간초과가 나올것이다. 그렇기에 값을 넣거나 뺄때 바로 정렬이 되는 heap을 사용하면 해결할수 있는 문제이다. 여기서 약간 문제를 꼬았는데 바로 절대값을 넣어서 조금 어..