흙금이네 블로그

BOJ에서 총 1,000문제를 해결했습니다. 작년 초에 SSAFY를 하면서 뭐라도 한번 꾸준히 해보자는 마음으로 시작했던 1일 1알고리즘. 매일 알고리즘 문제를 풀기 시작한 지도 어느덧 1년 6개월이 지났습니다. 많이 성장한 부분도 있고 뿌듯하기도 하지만 회의감이 들기도 합니다. 알고리즘 문제만 풀어온 것 같은 데다 아직 잘 풀지 못하는 어려운 문제들이 많기 때문입니다. 그렇지만 지금까지 해왔던 만큼, 앞으로도 문제는 매일 꾸준히 풀어보려고 합니다. 어려운 문제도 쉽게 풀어내는 그날까지 계속해서 파이팅!!

아이디어 회문인 문자열을 구성하는 문자가 하나라면 -1, 두 문자 이상이라면 문자열의 길이보다 1 작은 값을 출력한다. 풀이 #1 (Python) def solution(): S = input() N = len(S) if S[:N//2] != S[N//2+N%2:][::-1]: print(N) elif S != S[0]*N: print(N-1) else: print(-1) solution() 풀이 #2 (JavaScript) const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().split('\n'); function solution() { function isPalindrome() { for (let i=0; i

아이디어 재귀 호출로 규칙에 따라 별을 만든 후 출력한다. 풀이 #1 (Python) def solution(): def star(n): if n

아이디어 BFS로 고슴도치가 비버의 굴로 이동하는 최소 시간을 구한다. 풀이 #1 (Python) import sys input = sys.stdin.readline def solution(): R, C = map(int, input().split()) board = [[*input().rstrip()] for _ in range(R)] delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] queue = [] for r in range(R): for c in range(C): if board[r][c] == 'S': board[r][c] = 1 queue.append((r, c, 1)) elif board[r][c] == '*': queue.append((r, c, 0)) queu..

아이디어 BFS로 수의 한 자리만 숫자를 바꾼 다른 소수로 변환해 나가며 변환에 필요한 최소 횟수를 구한다. 풀이 #1 (Python) import sys input = sys.stdin.readline def solution(): P = [True]*10000 for i in range(2, 101): if P[i]: for j in range(i*2, 10000, i): P[j] = False for i in range(1000): P[i] = False T = int(input()) for _ in range(T): A, B = map(int, input().split()) visited = [0]*10000 visited[A] = 1 queue = [A] while queue: num = queu..

아이디어 BFS와 정렬로 s를 t로 바꾸는 최소 연산 방법을 구한다. 풀이 #1 (Python) s와 t는 모두 1 이상이므로 수를 0으로 만드는 - 연산은 사용하지 않는다. def solution(): s, t = map(int, input().split()) if s == t: print(0) return stack = [(t, '')] exps = [] while stack: n, exp = stack.pop() if n == s: exps.append(exp) continue elif n == 1: exps.append('/'+exp) continue if int(n**0.5)**2 == n: stack.append((int(n**0.5), '*'+exp)) if n%2 == 0: stack.ap..

아이디어 트리를 중위 순회하여 노드들의 열 위치를 파악한 후, 각 레벨에서의 너비를 구한다. 풀이 #1 (Python) import sys input = sys.stdin.readline def solution(): def inorder(u, d): nonlocal cnt, D if D 0: inorder(left, d+1) cnt += 1 graph[d].append(cnt) if right > 0: inorder(right, d+1) N = int(input()) children = dict() is_root = [1]*(N+2) for _ in range(N): num, left, right = map(int, input().split()) is_root[left] = is_root[right] =..

아이디어 브루트포스와 백트래킹으로 에너지 구슬을 제거해 나가며 에너지 양의 최댓값을 구한다. 풀이 #1 (Python) def solution(): def max_energy(total, n): nonlocal res if n res: res = total return for i in range(1, n-1): temp = W[i] del W[i] max_energy(total+W[i-1]*W[i], n-1) W.insert(i, temp) N = int(input()) W = list(map(int, input().split())) res = 0 max_energy(0, N) print(res) solution() 풀이 #2 (JavaScript) const fs = require('fs'); cons..

아이디어 세그먼트 트리로 구간 내 최솟값과 인덱스를 저장해두고 변경이나 출력이 필요한 구간에 대해 빠르게 처리한다. 풀이 #1 (Python) import sys input = sys.stdin.readline INF = int(1e9) def solution(): def minimum(s, e): min_val = tree[s] while s >= 1 e >>= 1 return min_val[1] def modify(idx): while idx > 1: if tree[idx] >1] = tree[idx] else: tree[idx>>1] = tree[idx^1] idx >>= 1 N = int(input()) n = 1 while n < N: n *= 2 tr..

아이디어 세그먼트 트리로 구간 내 최솟값을 저장해두고 변경이나 출력이 필요한 구간에 대해 빠르게 처리한다. 풀이 #1 (Python) import sys input = sys.stdin.readline INF = int(1e9) def solution(): def minimum(s, e): min_val = tree[s] while s >= 1 e >>= 1 return min_val def modify(idx): while idx > 1: if tree[idx] >1] = tree[idx] else: tree[idx>>1] = tree[idx^1] idx >>= 1 N = int(input()) n = 1 while n < N: n *= 2 tree = [IN..