흙금이네 블로그

피연산자는 연산자가 연산을 수행하는 대상으로, 인수라고 불리기도 한다. 단항 연산자는 피연산자를 하나만 받는 연산자이고, 이항 연산자는 두 개의 피연산자를 받는 연산자다. 단항 마이너스 연산자와 이항 마이너스 연산자는 사용하는 기호는 같으나 수행하는 연산이 다르다. 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..

아이디어 DFS과 백트래킹으로 남은 포지션에 선수들을 채워 나가며 능력치 합의 최댓값을 찾는다. 풀이 #1 (Python) 각각의 테스트 케이스에 대해 선수들의 능력치를 리스트 S에 입력 받는다. 메모리 절약과 DFS에서 빠른 접근을 위해 능력치가 0이 아닌 선수들만 인덱스와 능력치를 추가해 나간다. 포지션 할당 표시를 위해 0으로 채워진 리스트 visited를 생성하고 함수 dfs를 호출한다. 함수 dfs에서는 차례로 i 번째 선수를 적합한 포지션 중 남은 포지션에 배치하여 할당 표시 후, 현재 선수의 능력치 a를 능력치 합 total에 더하여 다음 선수로 함수를 재귀 호출한다. 배치가 끝나면 결과값 res와 능력치 합 total을 비교해 결과값을 능력치 합의 최댓값으로 갱신해 나간다. import s..

아이디어 DFS로 넴모들을 격자판에 배치하고 2×2 사각형 칸에 모두 넴모가 배치된 경우는 더 탐색하지 않는다. 풀이 #1 (Python) N이나 M이 1인 경우 2×2 사각형 칸이 존재할 수 없으므로 격자판에서 넴모를 배치하는 모든 경우의 수를 출력한다. 그렇지 않으면 넴모 배치를 위한 2차원 리스트 visited를 만드는데, 인덱스 에러 방지를 위해 행과 열 크기를 1씩 늘린다. (1, 1)을 시작점으로 하여 방문 표시 후 함수 dfs를 호출하고, 시작점 방문 표시를 지우고 다시 함수 dfs를 호출한다. 함수 dfs에서는 현재 칸을 기준으로 현재 칸, 위쪽 칸, 왼쪽 칸, 좌상단 칸에 모두 넴모가 배치되면 백트래킹으로 종료한다. 격자판 한 행씩 왼쪽에서 오른쪽으로 넴모들을 배치해 나가고, 종료 없이 ..

아이디어 DFS로 주어진 연산자로 가능한 식을 만들어 그 최댓값과 최솟값을 찾는다. 풀이 #1 (Python) 덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 람다식들을 리스트 cal에 저장한다. 리스트 operator에 각 연산자의 개수를 저장하고, 최댓값과 최솟값을 저장하는 리스트 res를 생성한다. 함수 dfs에서는 재귀 호출로 주어진 연산자를 사용하여 식을 만들고, 식을 모두 만들면 결과값과 비교하여 갱신해 나간다. cal = [lambda a, b: a+b, lambda a, b: a-b, lambda a, b: a*b, lambda a, b: a//b if a > 0 else -(-a//b)] def dfs(idx, total, a, s, m, d): global res if idx >= N: if t..

아이디어 DFS로 가능한 순열 순서를 탐색하되, 백트래킹으로 중간에 500 미만이 되는 순서는 더 탐색하지 않는다. 풀이 #1 (Python) 운동 키트 중량 증가량을 리스트 A에 저장하고, 방문 표시를 위해 리스트 visited를 생성한 후 함수 dfs를 호출한다. 함수 dfs에서는 사용하지 않은 운동 키트들에 대해 visited에 표시한 후, 재귀 호출로 중량 total을 갱신하며 탐색해 나간다. 중간에 중량이 500 미만이 되면 현재 탐색을 종료하고 되돌아가고, 운동 일수 day가 N이 되면 결과값 res를 1 증가시킨다. def dfs(day, total): global res if total = N: res += 1 return for i in range(..

아이디어 플로이드-워셜 알고리즘으로 모든 건물 간 거리를 구한 후, 왕복 시간을 최소로 하는 두 건물의 조합을 찾는다. 풀이 #1 (Python) 건물 개수 N은 100 이하이므로 모든 건물 간 거리를 저장하는 2차원 리스트 D를 생성하여 100으로 채운다. 같은 건물 간 거리는 0으로 저장하고, 입력 받은 도로 정보를 D에 반영한다. 플로이드-워셜로 건물 i에서 j로 가는 시간을 건물 k를 경유하여 가는 시간과 비교해 최솟값으로 갱신해 나간다. 양방향 도로이므로 건물 j에서 건물 i에서 가는 시간도 같은 값으로 저장하며, j는 i보다 큰 번호부터 시작하도록 한다. 모든 건물 간 거리를 구한 후, 이중 for문에서 건물 i와 j를 선택했을 때의 왕복 시간 합을 구해 결과값을 갱신한다. import sys..

아이디어 표에서 조건에 맞게 칸을 이동하며 만들 수 있는 숫자들 중 가장 큰 완전 제곱수를 구한다. 풀이 #1 (Python) 표를 입력 받아 2차원 리스트 table에 저장하고, 만들 수 있는 숫자들을 저장하는 세트 numbers를 생성한다. 차례로 표의 i행 j열에 있는 숫자를 numbers에 추가하고, 행과 열의 공차 di, dj로 함수 make_number를 호출한다. 이때 행과 열의 공차가 모두 0이면 무한 루프에 빠지므로 둘 중 하나라도 0이 아닐 때 함수를 호출하도록 한다. 함수 make_numbers는 인덱스를 벗어나지 않는 범위에서 재귀 호출로 공차에 따라 칸을 이동하며 숫자를 이어 붙인다. 이어 붙인 숫자들을 numbers에 추가하며, 공차가 음수인 숫자들을 저장하기 위해 역순으로 이어..

아이디어 #1 라그랑주에 의해 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명되었으므로 7453번 - 합이 0인 네 정수처럼 두 제곱수를 더한 값들에서 투 포인터로 합이 n이 되는 네 제곱수를 찾는다. 풀이 #1 (Python) 딕셔너리 cnt_dict에 두 제곱수 합을 키로, 0이 아닌 제곱수의 개수를 값으로 저장한다. 입력 n이 50,000 이하로 주어지므로 제곱수의 제곱근은 223 이하로 설정하고, 0은 제곱수가 아닌 것으로 본다. 세트 numbers에 두 제곱수 합들을 저장한 후 numbers를 오름차순으로 정렬한 리스트로 대체한다. 투 포인터를 이용해 numbers에서 네 제곱수 합이 n인 경우를 찾아 최소 제곱수 개수를 갱신해 나간다. n = int(input()) c..

아이디어 가능한 세 자릿수에서 각 질문에 대한 대답에 따라 불가능한 경우를 제외해 나간다. 풀이 #1 (Python) 세트 numbers에 1~9의 숫자 중 서로 다른 숫자 세 개로 구성된 세 자릿수를 문자열로 저장한다. 질문마다 질문한 숫자는 문자열로 Q에, 스트라이크 개수와 볼 개수는 정수로 strike와 ball에 저장한다. numbers에 있는 수를 구성하는 각 숫자가 Q와 자릿값까지 같으면 s를, 그렇지 않고 Q에 포함되면 b를 증가시킨다. 해당 숫자의 s와 b가 각각 strike와 ball에 같다면 temp에 추가하고, for문 종료 후에 기존의 numbers를 temp로 대체한다. import sys input = sys.stdin.readline def solution(): numbers ..