조용하지않는개발Blog

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 세그먼트 트리 공부하면서 풀어본 문제입니다. 이 문제 역시 리스트에 연속적으로 존재하고 특정 범위의 최소,최대를 구하는 문제이기에 세그먼트 트리였습니다. 이전과 다르게 최소, 최대를 위해서 리스트에서 최소 최대를 마지막에 가지고 있게 작업하였습니다. import sys input = sys.stdin.readline def ..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=623 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회사 식당에는 전설처럼 전해 내려오는 비밀 메뉴에 대한 소문이 있다. 소문의 내용은 대강 이러하다. 식권 자판기의 버튼을 특정 순서대로 누르고 결제를 하면, 평소와는 다른 색깔의 식권이 나온다. 이 식권을 배식대에 제출하면, 어떤 비밀 메뉴를 받을 수 있다는 것이다. 물론 이를 실제로 본 사람은 아무도 없어서, 어떤 메뉴가 나오는지는 커녕 눌러야 하는 버튼의 순서조차 알려져 있지 않다. 주방장인 당신은 이 소문의 실체를 알고 있다. 이는 분명한 사실이다! 정해진 버튼 조작법을 사용하면 비밀 메뉴의 식권을 ..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 세그먼트 트리 쪽을 공부하기위해 찾아 풀어본 문제이다. 문제에 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구한다고하면 세그먼트 트리로 풀수있는 문제이다. 2042번 구간 합 구하기 문제 역시 12345와 같이 연속적으로 존재하는 리스트에 2번째 부터 5번째 까지의 합 등으로 되어..

https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 그리디 문제이기에 문제를 통해 해결을 해봐야한다. 먼저 1과 2를 무조건 다 사용하는 경우이니 1과 2의 합인 3을 전체 합에서 3으로 나누어 떨여져야한다. 이제 3까지는 잘 나누어 떨어지니 그 안에 1과 2로 나누어 떨어지는 확인한다. 1은 나누어 떨어지는것을 확인 할 필요가 없으므로 2만을 확인해서 3으로 나누어 떨어진것과 같거나 그보다 많으면 답은 YES가 된다. import sys input = s..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제 자체는 참 간단하게 나와있는데 알고있어야 할 것들이 꽤 있어야 풀 수 있는 문제였다. 먼저 우선순위 큐를 알고있어야 풀수있는 문제이다. 문제를 보면 수업이 끝난 직후 이어서 다음 수업을 시작한다고하는데 이것이 우선적인 순서를 하고 이어서 계속 진행 되기에 우선 순위 큐를 이용해야한다. python에서는 heapq 라이브러리를 알고 있어야 빨리 해결할 수 있는 문제이다. heapq를 통해 데이터를 넣으면 ..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제 제목을 보고 mid를 이용하여 반씩 나누어 재귀 함수형식으로 풀어야겠다는 생각을 했지만 정확히 어떻게 접근을 해야할지 감이 안와서 다른 사람들의 힌트를 얻어 문제를 풀었다. 먼저 루트보다 큰 값이 나오는 값을 찾고 이를 mid로 둔다. 그리고 첫번째 값+1, mid-1 값을 재귀 함수로 돌리고 mid,end 값으로 재귀함수를 돌린다. 마지막으로..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 먼저 pypy3로 푸는 것이 좋다. 실제 확인해보니 python으로 푼사람이 8명도 안된다..;; 문제를 보고 반복 시키기에는 너무 많은 양을 반복해야할듯해서 BFS를 통해 풀면 될듯하다는생각을 가졌다. dfs는 방문을 했는지만 체크하면 확실히 시간을 줄일 수 있다. 이를 유의하여 문제를 풀면 된다. import sys from collections..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 단순하게 S를 T에 맞추어 풀면 틀리는 문제이다. 거꾸로 T를 S에 맞추면 쉽게 풀린다. 왜일까? 내가 생각하기로는 S의 문자열이 계속 커질텐데 계속해서 T를 확인하기위해 작업을 하면 무거워져 시간 초과가 나올수있다. 다음으로는 T의 문자열에서 오른쪽만 보며 A의 경우는 A만 빼주고 B인 경우에는 B를 빼준후 뒤집기만 하기에..

https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 1~6번까지 리스트를 만들고 스택을 이용해서 이전에 누른것 보다 크거나 작거나 확인하면서 append, pop 형식으로 문제를 풀면 된다. 예시: 2번 줄에 8을 누른다. 1 2번 줄에 10을 누른다 2 2번 줄에 12를 누른다. 3 2번 줄에 10을 누르기위해 12를 뗀다. 4 2번 줄에 5번을 누르기 위해 10을 뗀다...

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 'B의 값을 2로 나누고 첫번째 수가 1인 경우를 한칸 줄인다고 되겠다'라고 생각했다. 문제의 조건을 거꾸로 하면 되지 않을까 생각을 했다. 또한 조건으로 0이 아닌때까지만 반복 시키면 되지 않을까 싶었다. 그것의 결과를 리스트에 담고 리스트 안에 A가 있는지 확인하는 코드를 작성하였다. import sys input = sys.stdin.readline a,b = list(map(int,input().split())) result=[b] while True: if resu..