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 스택 문제 이긴 하지만 어떻게 풀어도 O(n^2)의 시간복잡도가 나올 거라는 생각에 for문을 2개 사용해서 문제를 해결하고자 했다..! import sys input = sys.stdin.readline n = int(input()) nge_list = list(map(int, input().split())) answer = [] for i in range(n): for j in range(i,n): if..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 폭발 문자열이 있다면 그 문자열은 제거된 상태로 output이 나와야 함 import sys input = sys.stdin.readline word = input() burst = input() stack = [] len_burst = len(burst) for i in word: stack.append(i) if ''.join(stack[-len_burst:]) == burst:..
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전의 종류는 N개이고 각 동전의 개수는 무한개라고 할 때, 가장 적은 동전을 사용하여 가치의 합을 구함 이때, 동전의 개수를 구하기!! 돈으로 나눠주고 나머지를 다음 계산의 입력으로 사용하여 답을 구함 import sys input = sys.stdin.readline n, k = map(int,input().split()) coi..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 나의 풀이 2칸씩 이어서 갈 수 있고, 3칸은 안됨 1칸만 띄어서 갈 수 있고 2칸은 안됨 마지막 계단을 무조건 밟아야 함 최대로 나오는 점수를 return 하면 되는 문제이다. dp에는 각 step에서 선택할 수 있는 가장 큰 수가 저장된다. import sys input = sys.stdin.readline n = int(input()) s=[int(input()) for _ in range(n)] pri..
https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 처음에 사전의 규칙을 파악하는데 시간이 좀 걸렸다. A AA AAA AAAA AAAAA AAAAE AAAAI AAAAO AAAAU AAAE AAAEA AAAEE AAAEI AAAEO AAAEU 다음과 같은 규칙을 가지고 백트래킹을 쓰면 되겠다고 생각했다. word_list를 통해 모든 사전을 구하고 답을 찾는 거라 시간이 오래 걸린다. def solution(word): answer =..
https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 아래와 오른쪽으로만 이동 가능 물 웅덩이는 지나가지 못함 빨 -> 파 -> 초 -> 검 방향으로 갈 수 있는 경우의 수를 체크함 여기서 puddles이 x, y 정렬이 아니라 y, x 정렬이라 반대로 넣어줘야 함 이거 때문에 시간이 오래 걸림 def solution(m, n, puddles): roadmap = [[0]*(m+1) for j in range(n+1)] roadmap[1]..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 나의 풀이 n개의 정수로만 이루어진 임의의 수열이 있을 때 연속된 몇 개의 수를 선택해서 구할 수 있는 가장 큰 합을 구하려고 한다. [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] t-1 + t의 값이 t보다 크다면 해당 연속된 수열의 합이 가장 큰 것이다.라고 생각하고 문제를 풀었다. import sys n = int(sys.stdin.readline()) nums = list(m..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나의 풀이 다음과 같이 나선 모양의 삼각형이 있다고 할 때, 가장 긴 변의 길이를 K라고 한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변(k)의 길이이며 N이 주어졌을 때 p(N)을 구하는 프로그램을 작성하자. 다음과 같이 인덱스가 있다고 하면 p(n)은 p(n-1) + p(n-5)라고 볼 수 있으며 코드로 나타내면 아래와 같다. import sys cnt = int(sys.stdin.read..
