문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 현재 위치의 오른쪽에서 현재 위치의 수보다 큰 값을 저장하고, 정답을 출력하는 간단해 보이는 문제이다. 풀이 1에서는 이중 반복문 구조(O(N^2))로 인한 시간초과가 발생하였다. 풀이 2는 정답을 담는 배열 res, 인덱스를 담는 배열 check를 이용하였다. 현재 값이 arr[check[-1]]보다 크다면 res[check[-1]]의 값을 현재 값으로 한 후, check에 현재 값의 인덱스를 ..
문제 https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 나이가 가장 작은 사람과 나이가 가장 많은 사람의 이름을 출력하는 문제 연, 월, 일, 이름 순으로 데이터를 저장하고 정렬한다. 가장 먼저 태어난 사람이 맨 처음에 있고, 가장 늦게 태어난 사람이 배열 맨 마지막에 있으므로 해당 부분의 이름을 출력한다. 제출 코드 # 2023/01/26 문자열, 정렬 # https://www.acmicpc.net/problem/5635 import sys input = sys.stdin.readline data = [] for _ ..
문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 현재 위치가 1인 경우 자신의 왼쪽, 왼쪽 위의 대각선, 위쪽을 확인하고 최소 값을 현재 값과 더한다. 그 후 max값을 계속 저장한 뒤 제곱한 값을 출력한다. 1의 위치에서 정사각형의 크기를 계속 계산하는 경우는 DP를 수행하는 것보다 높은 복잡도를 가질 것이다. 제출 코드 # 2023/01/25 DP # https://www.acmicpc.net/problem/1915 import sys input = sys.stdin.readline N, M = ma..
문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 현재 위치와 다음 위치를 비교하여 계산하는 문제이다. 처음 풀이는 비용을 pop으로 가져오고, 만약 그 비용이 현재 값보다 더 낮은 경우 이동하고 total_dis 값을 초기화해줬다. 다른 풀이를 찾아봤는데, 이동할 때마다 지불 비용을 비교한 후 낮은 값으로 이동하는 단순한 풀이가 있었다. 제출 코드 # 2023/01/25 그리디 # https://www.acmicpc.n..
문제 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 풀이 주어진 문항에 충실하면 되는 문제, 그대로 구현한 뒤 정답을 출력하면 된다. 모음이 들어가는지 확인 e와 o를 제외한 같은 문자가 반복하는지 확인 자음 및 모음의 개수가 3개 이상인지 확인 위 세가지 항목을 확인하고 정답을 출력한다. 제출 코드 # 2023/01/25 문자열 # https://www.acmicpc.net/problem/4659 import sys input = sy..
