링크: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 아이디어 dp 배열 2개를 만들어 각 지점에서 우측 좌측 '가장 긴 증가하는 수열' 문제에서 사용한 점화식을 적용 두 dp배열을 모두 만들어준 후 합쳐주어 바이토닉 부분 수열의 길이를 구함 구현 import sys input = sys.stdin.readline n = int(input()) s = list(map(int, input().split())) dp_left = [1]*n dp_right = [1]..
링크: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 아이디어 가로 새로 크기만큼 배열 생성 입력된 좌표를 1로 변경 이중 for문을 돌며 1인 좌표에서 bfs 탐색 진행 탐색을 마친 좌표는 0으로 변경 from collections import deque import sys input = sys.stdin.readline dx = [0,0,1,-1] dy = [1,-1,0,0] t = int(input()) def bfs(graph, a, b): que..
링크: https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 아이디어 첫째날 둘째날을 a, b로 두고 D와 K를 가지고 점화식을 만들어 보자 예) D가 4면 a, b, a+b, a+2b, 2a+3b, 3a+5b=> K=a+2b DP배열을 2차원배열로 만들어 a에 곱해지는 값과 b의 곱해지는 값을 저장함 구현 D, K = map(int, input().split()) d = [0] * 31 d[1] = (1,0) # 첫째날 1a + b d[2..
링크: https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어1 (시간초과) 일단 단순하게 b번 반복하며 a 곱하기 파이썬은 자동으로 동적할당이 되어 너무 큰 수가 나오면 메모리초과가 나올 수 있음 a를 곱하고 c로 바로바로 나눠주며 메모리초과 방지 import sys input= sys.stdin.readline a, b, c = map(int, input().split()) for i in range(b): a *= a a %= c print(a) 단순히 반복하는 로직은 답이 아닌듯 하다. 아이디어 2 ..
링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 아이디어 익은 토마토(1)의 좌표들를 q에 넣고 bfs 숨바꼭질과 동일하게 방문처리와 깊이 저장을 동시에 진행 (이건 토마토 배열 안에서 해도 될듯) 상하좌우 확인 0이면 1로 변경 후 큐에 넣기, 1이면 무시, -1이어도 무시 모든 토마토가 익었는지와 며칠이 걸렸는지는 배열을 돌며 확인 0인 부분이 있으면 -1출력 자료구조 토마토: int[][] Queue(BFS) 코드구..
링크: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 수빈이의 시작점을 시작으로 bfs x-1, x+1, 2*x 이 3가지 방향으로 이어지는 그래프로 생각 방문했던 수는 방문처리를 해주어 탐색하지 않기 몇번째 층인지 확인은 방문 처리와 동시에 이루어짐 전 요소의 방문 인덱스에 +1한 값을 현재 요소의 방문 인덱스에 저장 동생의 위치에 도착하는 경우가 발생하면 그 요소의 층을 따로 저장 다음 층 탐..
링크: https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 아이디어 2중 for문 => 값이1 && 방문x => BFS / 그림개수 +1 BFS 돌면서 방문처리 / 그림 넓이 최대값 갱신 시간복잡도 BFS의 시간복잡도 => O(E+V) E+V = (m*n) + (4*E) (V는 넉넉하게 잡아줌) 5*500*500 = 125만 가능! 자료구조 그래프 전체 지도: int[][] 방문 : bool[][] Queue(BFS) 코드 구현 import sys in..
링크: https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 +기를 기준으로 리스트를 나눠서 계산해보면 쉽게 풀리지 않을까? 스택을 이용해 문자열을 돌며 올바르게 입력된 괄호인지 판단하자 돌다가 스택의 크기가 0되기 전에는 곱하기 0이 되면 곱한 것들을 따로 result와 더하고 result에 저장 다시 계속 반복 모든 문자열을 돌았으면 result가 답? 위의 구조로 코드를 짜봄 import sys input = sys.stdin.rea..
