조용하지않는개발Blog

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 작은 값과 큰 값을 비교해서 최소 값을 찾는 문제인데 양쪽의 포인트를 두고 천천히 내려가며 비교하면 끝이 나는 문제이다. 처음에 먼저 정렬을 진행하고 오른쪽과 왼쪽 변수를 만든다. 최대값은 제일 먼저 선택한 오른쪽 왼쪽이라고 가정하고 진행하였다. 이후 왼쪽이 오른쪽을 넘어가기 전까지 반복하며 값을 계산한다. 합이 음수이면 왼쪽을..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 이해하면 좀 쉽게 풀리는 문제인데. dp 문제로 길게 증가하는 dp1와 감소하는 dp2두개를 만들어서 그 둘을 합치고 겹치는 구간 1을 빼면 쉽게 풀리는 문제이다. dp2를 구하기 위해서 list를 역순으로 뒤집어서 쉽게 계산했다. 나온 결과를 다시 reverse 시키고 dp1과 더하면 끝이 난다. import sys input= sys.stdin.readline n= in..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 dp 문제로 처음을 1을 가지고 있는 dp를 만들고 이어서 자기자신보다 큰 값이 나오면 +1 하고 dp의 위치와 비교하여 큰 값을 입력하는 형식으로 풀면 쉽게 풀린다. import sys input= sys.stdin.readline n= int(input()) n_list=list(ma..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=804 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 조건이 많아서 어떻게 시작을 해야할까 고민하면서 시작을 하게 되었다. 먼저 5x5의 그래프를 만드는 것을 먼저 하였다. 조건에 나와있듯이 같은 단어는 제외를 시키고 처음부터 하나씩 적고 빈칸은 남은 알파벳을 넣으면 된다. set을 통해서 같은 알파벳을 제외 시키고 남은 알파벳을 넣어 주었다. 그리고 graph 리스트를 만들어 놓았다. 행열이 바뀐 row_graph 도 만들어 놓았다. 다음으로는 메세지의 글을 2글자씩 만드는 작업을 진행하였다. 리스트에서 pop을 하는 형식으로..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 친구와 친구 등으로 연결되어있는 것으로 보아 그래프 문제라고 생각들며 이미 들린 곳은 다시 들리지 않게 하면 될듯하다. 또한 BFS를 통해서 총 몇번을 안으로 들어가는지 확인하면 쉽게 풀릴 수 있는 문제이다. import sys from collections import deque input = sys.stdin.readline n = int(input()) g..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제는 길지만 이해하면 쉽게 풀 수 있는 문제 톱니바퀴는 8개로 되어있다. [1,0,1,1,1,1,1,0] 로 되어있다고 가정하자 총 4개의 톱니 바퀴가 존재하고 반시계방향(-1)으로 움직일때는 맨앞에 수를 맨뒤로 보내고, 시계방향(1)으로 움직이면 맨뒤를 맨 앞으로 보내주면 된다. 리스트에서 pop.append, insert를 활용하면 충분히 움직일수있다..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=390 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 시간 복잡도를 확인해보면 N이 N^2인 경우에도 10^8안에 있는 것을 알수있다. 부르트포스(완전 탐색) 문제로 풀면 쉽게 풀릴것이다. 또한 각 돌들을 이동 수를 가질수있게 dp를 활용한다. 입력 예제를 예시로 보자면 a의 리스트를 0부터 4까지 천천히 증가하며 비교하는데 a[0]은 3이므로 3에 갈수있는 곳은 1밖에 없다 이를 dp[0]에 넣어준다. a[1]은 2이고 이보다 작았던 a값을 확인한다. 아쉽게도 작은 값은 없다. a[2]은 1이고 이보다 작았던 a값을 확인한다...

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 LCS -> 최장 공통 부분 수열을 찾는 문제이다. 이는 DP를 활용하여 푸는 것이 빠르게 답을 찾을 수 있다. 최장 공통 수열을 구글에 검색해보면 위키 백과에 어떻게 이용하는지 알수있다. 그 중 하나의 이미지를 가져왔는데 위 그림 처럼 1. 행과 열이 같은 경우 이전에 행, 열에 있던 값에 1을 더하는 형식 2. 비..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=391 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 이전에 풀었던 바이러스 문제를 좀더 어렵게 만든 문제인데.. 이전에 이미 분할 정복으로 풀어서 똑같이 풀면.. 해결된다.. 하하;; 문제만 보면 단순하게 생각할수있다. k*(p^10n)이 답이기 때문이다. 하지만 입력값의 최대인 10의 8승은 엄청나게 많아서 계산하기에는 많은 시간이 걸린다. 이를 분할 정복을 이용하여 O(nlogn)으로 줄일 수 있다. import sys input= sys.stdin.readline k,p,n = map(int,input().split())..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 bfs 형식으로 문제를 풀어가면 되며 X초 마다 상하좌우 방향 전환하는 것과 사과 존재에 따라 꼬리 변화 그리고 벽이나 자기자신을 부딪히는 조건을 찾아서 멈추기만 하면 끝나는문제 저 두가지 조건만 빠르게 구현하면 쉽게 풀수있다. import sys from collections import deque input= sys.stdin.readline count=1 n = ..