조용하지않는개발Blog

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 1. 방향성이 없음(양쪽을 다 갈수있음) 2. 1에서 n까지의 최단 거리를 알고싶어함. 3. 이동간의 거리가 존재한다. 4. 정해진 2곳을 지나가야한다. 1과 3번을 통해서 다익스트라 알고리즘을 이용하면 된다는 것을 알수있다. 4번을 통해서 다익스트라를 2번더 반복해서 최소 거리를 찾으면 해결되는 문제이다. 기본 다익..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=414 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 dp 문제라고 생각하고 접근하였다. p의 로봇의 위치는 dp에 True로 변경하고 k만큼 왼쪽에서 오른쪽으로 dp가 False인 경우에 dp를 True로 바꾸면서 count를 1씩 증가시키면 끝이 나는 문제이다. input= sys.stdin.readline n,k= map(int,input().split()) dp = [False]*n n_list = list(input().strip()) # print(n_list) for i in range(len(n_lis..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 재귀함수에서 출력위치를 어떻게 하냐에 따라서 전위, 중위, 후위로 나오게 할수있다. 전위는 시작과 동시에 출력을 하고, 중위는 가운데에서 왼쪽후에 출력을 하고 후위는 오른쪽까지 간 후에 출력을 한다. import sys input = sys.stdin.readline n = int(input()) n_list={} for i in range(n): t..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 그래프, 각 비용이 존재하고 최소 비용을 구하는 문제이면 힙큐를 사용한 다익스트라 알고리즘을 이용해서 푸는 문제일 확률이 높음. 이를 참고 하여 문제를 풀면 통과할 것입니다. import sys import heapq INF = sys.maxsize input = sys.stdin.readline def solve(): n = ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 처음 풀었을때 dfs, bfs로 접근하면 되겠구나 라는 생각은 들었다. 접근은 잘했지만 정점 1부터 n까지 반복하여 돌리면 시간 초과가 나온다. 이것을 통해 뭔가 다른 조건이 하나 더 있겠구나! 라는 생각이 들었다. 이 조건을 찾기 위해서는 https://blog.myungwoo.kr/112 이 블로그를 참고했다. 블로그에서는 임이의 정점..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 조합을 구현하는 문제이다. 이 문제를 재귀함수로 들어가서 문제를 풀면 시간초과가 나와서 틀리게 될것이다. 다른 사람들 틀린 답을 보니 dfs형식으로 풀었다가 틀린것을 확인했다. 다이나믹 프로그래밍으로 풀면 어렵지 않게 풀 수 있다. 아니면 결과 값만 계속 가지게 있고 풀면 쉽게 풀 수 있다. 예를 들어 n 이 5 이고 m이 2이면 분자는 5*4, 분모는 2*1 로 계산을 하고 분자/분모로 나누면 답이다. 이렇게 하면 재귀함수없이 수학적 계산만하기에 빨리 결과를 뽑을 수 있다. ..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 이해하면 쉽게 풀 수 있는 문제입니다. 입력을 통해 총 사람 수 50, 파티 수 50 , 파티 하나 당 50명씩 있다고 해도 총 50*50 =2500번이 돌아간다. 추가적으로 50번씩 돌리게 해도 총 125000번 돌기에 문제를 통과하기에는 충분한 시간이다. 먼저 진실을 알수밖에 없는 수를 만들면 되는데 처음 2번째 줄에서 나오는 진실의 사람을 체크 한다. 이후 파..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=389 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 단순하게 구간만 찾아서 평균내면 되는 문제이다. 이게 왜 레벨 3이지? 하는 생각이 들었다. 아마 반복문 2번 돌리면 안풀리기 때문인가? 파이썬으로 풀었다면 리스트 자체를 시작 끝을 찾아내기만 하면 되기에 정말 쉽게 풀 수 있다. import sys input = sys.stdin.readline n,k = map(int,input().split()) n_list = list(map(int,input().split())) for i in range(k): start,end =..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 이해하고 주사위의 특징을 생각하면서 문제를 풀면 조금이나마 쉽게 풀린다. 주사위의 최소 값을 총 3개로 볼수있는데 1개만 보이는 경우, 2개가 보이는 경우, 3개가 보이는 경우이다. 이때 2,3개는 주사위가 붙어 있다는 조건이 있다. 2개의 경우 붙어있는 2개의 경우의 수를 찾아서 최소 값을 준비한다. 3개의 경우 A,F 중 한개,..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 엄청 단순하게 풀면 시간 초과가 나올것이라는 생각이 들었지만 역시 그렇게 푸니 시간초과가 나왔다. 효율적으로 풀 방법을 찾다보니 문제에 같은 문자를 2개 이상 포함 되어있지 않다가 조금의 힌트가 되는 것같다. 한문자씩 리스트에 쌓으면 진행하고 그때 폭발 문자열의 마지막 문자가 같은 경우 그때의 쌓인 문자를 비교해서 같은 경우 제거하는 형식으로 문제..