조용하지않는개발Blog

https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 n이 포함될수 있는 좋은 구간을 전부 다! 찾는 문제이다. 단순하게 브루트포스로 풀수있겠다 싶은 문제였다. 그렇기 위해서는 먼저 집합으로 정해진 구간을 정렬해 준다. 이후 n이 포함 되는 구간을 찾는다. 여기서 포함 되는 구간이 끝인 경우와 처음인 경우가 있기에 이를 고려해줘야한다. 안그러면 틀리는 경우가 있을 것이다. 구간을 찾았다면 n을 포함 할 수 있는 모든 경우의 수를 2중 반복문으로 돌려보면 된다. import sys input = sys.stdin.read..

https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보았을때 알수있는 힌트 k개수 만큼 뺐을때 가장 큰수를 만드는 문제이다. 순조부를 이용하여 모든 경우의 수를 이용할수도 있겠지만 제한 조건에 1000000자리 수가 있다고하니.. 순열, 조합을 이용하면 시간 초과가 날것이다. 그렇기에 다른 방식으로 문제를 풀어야한다. 간단하게 스택 구간을 만들고 그 안에 큰 값을 계속 담게 하고 그보다 큰 값이 나오면 변경해주는 식으로 문제를 풀어주면..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보고 조합 형식으로 풀어야하나 했지만 큰값만 잘 찾아놓으면 풀수 있는 그리디 문제였다. 자리수가 큰를 찾아서 리스트로 정리해놓는다. 예를 들어 GCF + ACDEB 라고 하면 ACDEB GCF 여기서 두 값을 더하려 위치에 맞게 값을 넣으면 A = 10000 C = 01010 D = 00100 G = 00100 E = 00010 B = 0000..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제에서 이야기하는 조건과 bfs만 알고 있으면 풀 수 있는 문제이다. 다만 시간을 줄이기 위해서는 여러가지 공부가 필요할듯하다. 문제 내용을 잘 보면 옆의 나라의 인구 차이가 L과 R 사이에 있다면 같이 공유한다고 한다. 이를 생각하여 연결된 모든 국경 인원을 저장하고 나라 수 만큼의 평균을 만들고 기존의 그래프에 저장 시키면 된다. 이를 ..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체는 어렵지 않은 문제였다. 하지만 어떻게 풀면 시간초과도 날수있으니 조금 생각하며 풀어봐야하는 문제였다. 먼저 왼쪽끝에서 오른쪽 끝으로 움직이면서 큰 값만을 이동 시키면 되는 문제이다. 이를 담을 DP를 만들어 주면 된다. 나는 이를 추가한다는 느낌이 들어 stack이라고 정의하고 넣으면서 진행했다. 결과적으로 오른쪽 아래에 도착하게..

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이 담긴 리스트를 생성하고 가치가 낮은 동전을 넣고 그다음으로 가치 높은 동전을 넣어가면서 ..