흙금이네 블로그

아이디어 동적 계획법으로 각 칸에서 만들 수 있는 정사각형 한 변의 크기를 저장해 나간다. 풀이 #1 리스트 dp에 배열 첫 줄을 입력 받고, 결과값을 저장하는 변수 res에 배열 첫 줄에서 가장 큰 값을 저장한다. for문에서 arr에 배열을 한 줄씩 입력 받고, 차례로 arr에서 1로 된 칸들에 왼쪽 칸, 위쪽 칸, 좌상단 칸 중 최솟값을 더한다. 위쪽 칸과 현재 칸은 각각 다음 칸에서 좌상단 칸과 왼쪽 칸이 되므로 하나라도 0인 경우 두 칸을 건너뛰도록 한다. res를 현재 줄의 최댓값과 비교해 갱신하고, 다음 for문을 위해 dp를 arr로 대체한다. res는 정사각형 한 변의 길이를 나타내므로 마지막에 res를 제곱하여 출력한다. import sys input = sys.stdin.readlin..

피연산자는 연산자가 연산을 수행하는 대상으로, 인수라고 불리기도 한다. 단항 연산자는 피연산자를 하나만 받는 연산자이고, 이항 연산자는 두 개의 피연산자를 받는 연산자다. 단항 마이너스 연산자와 이항 마이너스 연산자는 사용하는 기호는 같으나 수행하는 연산이 다르다. let x = 1; alert(-x); // -1 (단항 마이너스 연산자는 부호를 뒤집음) let x = 1, y = 2; alert(y-x); // 1 (이항 마이너스 연산자는 뺄셈을 함) 자바스크립트에서 지원하는 수학 연산자는 덧셈(+), 뺄셈(-), 곱셈(*), 나눗셈(/), 나머지(%), 거듭제곱 연산자(**)가 있다. 거듭제곱 연산자는 정수가 아닌 숫자에 대해서도 동작한다. alert(1+2); // 3 alert(1-2); // -..

아이디어 백트래킹으로 가장 작은 수의 좋은 수열을 찾는다. 풀이 #1 (Python) 좋은 수열 중 가장 작은 수는 1로 시작하게 되므로 리스트 stack에 길이 1과 문자열 1을 튜플로 저장한다. while문에서 DFS로 문자열 길이 l과 문자열 s를 꺼내 슬라이싱으로 인접한 두 부분 수열 중 같은 쌍을 찾는다. 같은 쌍이 존재하면 break로 다음 값을 꺼내고, 그렇지 않으면 길이가 N인지 비교하고 N이면 출력 후 종료한다. N이 아니면 stack에 다음 길이와 문자열을 추가하는데, stack은 마지막 값부터 꺼내므로 숫자가 큰 순서대로 넣는다. 가장 먼저 찾은 좋은 수열이 가장 작은 수의 좋은 수열이므로 좋은 수열을 찾으면 결과값 출력 후 while문을 종료한다. N = int(input()) st..