Dalin's Archive

문제로 가기! 처음에는 윗칸의 수를 고르고 그 아래 칸의 수를 보고, 각자 set에 넣어서 두 set이 같은지 다른지 판단해주고.. 같으면 또 다른 (윗칸) 수를 골라보고... 다르면 그 아래칸의 수를 윗칸 수로 하는 수를 찾고... 그런 식으로 생각을 해서 코드를 짜긴 했는데, 틀렸다. 질문 검색에서 다른 분들이 주신 반례를 보고, 그림을 그려보니까 문제가 좀 더 잘 이해되었다. 방향이 있는 그래프(윗 칸 -> 아랫 칸)로 보고, 인접 리스트로 입력을 받았다. DFS로 탐색을 하면서 사이클이 발생한 것을 다 더하면 되는 문제였다. 나는 set을 활용해서 윗 칸의 수들의 집합, 아랫 칸의 수들의 집합이 일치하는지 보았다. 만약 일치하면 일치하는 집합을(윗 칸 수들의 집합이든 아랫 칸 수들의 집합이든 같으..

문제로 가기~ BFS로 풀었다. 쭉~ 보면서 아직 방문 안한 곳이면 bfs로 상하좌우 4방향을 본다. 출발한 곳의 색깔과 같으면 개수를 더한다. 그래서 몇 명의 병사가 뭉쳐있는지 세고, 해당하는 팀에 힘(뭉친 수의 제곱!)을 더한다. 이미 센 병사는 또 세면 안 되니까 방문 체크 import collections import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(list(input().strip()) for _ in range(M)) dir_x, dir_y = [0, 0, -1, 1], [-1, 1, 0, 0] def bfs(i, j, color): cnt = 1 q = collections.deque() v..

문제로 가기! 처음에는 어떻게 풀지 감도 잡히지 않았다. 문제 분류가 BFS라는데,, 이게 왜 BFS인지... 뭔가 수학적인 개념이나 그리디로 접근해야 하는 거 아닌가..? 하는 생각도 들었다. 그러다 스터디에서 다른 분의 설명을 듣고 나서 풀었다! BFS로 풀었다. 매번 K개 뒤집기를 해야 하는데, 이때 뒷면으로 뒤집어진 동전을 0~K개를 뒤집었을 때 어떻게 되는지 본다. 만약에 지금 뒷면인 동전이 5개인데, 7개 뒤집는 것은 말이 안되니까 그런 경우는 제외하고! 가능한 경우를 봤을 때, N개 동전 모두 뒷면이라면 그때까지 K-뒤집기를 한 횟수를 리턴하면 된다. 그게 아니라면, deque에 그 상태에서 뒷면인 동전 개수와 그때까지 뒤집기 횟수를 넣어주었다. visited 체크를 한 후에 deque에 넣..

문제 보러 가기! DFS로 풀었다. 그대로 직진하거나, 방향을 바꾸거나!! 이때 시계방향이든 반시계방향이든 한 방향으로 돌아봐야 한다~ 대각선 방향으로 가야 하고, 두 개(카페, 디저트)의 방문 체크를 고려하는 게 특이했다~ # 대각선 방향 directions = [(1, 1), (1, -1), (-1, -1), (-1, 1)] def dfs(i, j, direction_type, dessert_cnt): global ans # 직진 or 꺾기 if direction_type < 3: tmp = direction_type + 2 else: tmp = direction_type + 1 for k in range(direction_type, tmp): ni = i + directions[k][0] nj = ..

문제 보러 가기 문제에 나와있는 뿌요 뿌요 룰을 그대로 구현하면 된다. 쭉 보면서 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있는지 보고 그런 그룹이 있으면, 뿌요들 터지게 하기 (단, 여러 그룹이 터져도 한 번의 연쇄만 추가됨) 남은 뿌요들이 중력의 영향을 받아서 떨어지게 하기 또 다시 1번으로 돌아가기 같은 색 뿌요가 상하좌우 4개 이상 연결되어 있는지 보는 것은 BFS로 했다. 중력의 영향받아서 잘 떨어지게 하는 것을 구현하는 게 어려웠다.ㅠ if와 while들을 이용해서 구현했다. 좀 복잡한 시뮬레이션, 구현도 연습해야겠다. 전에 풀었던 10703: 유성 문제가 떠올라서 비슷하게 하려고 했으나, 다른 점이 많아서 참고만 한 것 같다. import collections import sys inp..

백준 문제 보러가기! 코드 N = int(input()) tiles = [0]*81 tiles[1] = 1 tiles[2] = 1 def fibo(n): if tiles[n]!=0: return tiles[n] tiles[n] = fibo(n-1)+fibo(n-2) return tiles[n] if N == 1: print(4) else: print(fibo(N)*4 + fibo(N-1)*2)설명 타일 한 변의 길이는 피보나치 수열로 증가한다. 타일 각 변의 길이를 한번 구하면, 그것을 tiles에 저장한다. 타일의 개수 N(1 ≤ N ≤ 80)라는 조건이 있어서 tiles = [0] * 81로 했다. 타일의 변 길이가 필요하고, 그것을 이미 구한 적이 있다면 return tiles[n]으로 꺼내온다! ..

백준 문제 보러 가기~! 코드😎 n = int(input()) dy = [0]*(n+1) if n == 3: print(n) else: dy[1] = 1 dy[2] = 2 for i in range(3,n+1): dy[i] = dy[i-1]+dy[i-2] print(dy[n]%10007)설명😊 다이나믹 프로그래밍!! 일단 n이 1이라면, 당연히 답은 1이다. 세로로만 세울 수 있다. n이 2라면 답은 2이다. 세로로 두개 혹은, 가로로 두개가 가능하다. n이 3이라면 두 가지 경우로 나눌 수 있다. 맨 끝 부분에서, 세로로 하나인 경우, 그러면 그 안쪽부분은 2개가 있다. 그럴 때 안쪽 2개를 배치하는 방법은 n=2일 때 경우의 수와 같다. 맨 끝 부분에서 가로로 두개를 둘 경우, 안쪽에는 하나만 남았다..

import sys input = sys.stdin.readline N = int(input()) stones = list(tuple(map(int, input().split())) for _ in range(N - 1)) stones = [0] + stones K = int(input()) arr = [] def dfs(idx, use_bigbig_jump, energy_sum): if idx == N: # 최종 돌까지 갔을 때 든 에너지 총합을 arr에 저장 후 리턴 arr.append(energy_sum) return elif idx > N: # 최종 돌을 넘어가면 리턴 return if use_bigbig_jump == False: # 매우 큰 점프 안했는지 체크한 후, 매우 큰 점프 사용 dfs..

문제 보러 가기~ ㅠㅠㅠ 그리디 문제는 아이디어 떠올리기가 어려워서 다른 분들 것을 참고할 때가 많았다.. 그러다가 오랜만에 스스로 푼 문제..!! 접근 일단 문제에서 구할 것은 &#39;우울함의 합&#39;을 최소화하자는 것이다. 우울함은 기분 0 미만인 날에서 (기분)^2이다. 약속의 순서는 바꿀 수가 없이 언제 할지 배치하는 것이다. 일단 기분이 0 이상이면 괜찮은 상황이다. => 모든 날의 기분이 0 이상일 수 있으면 정답은 0이다. => 모든 날의 기분이 0 이상일 수 없으면, 약속이 몰려 있어서 외로움이 극대화되는 것보다는 (약속이 쭉 있다가 약속 없는 날이 연속 4일이 되는 경우에, 외로움은 1의 제곱+ 2의 제곱+ 3의 제곱+ 4의 제곱이 된다.) 기분의 제곱을 해서 우울함 수치를 구하니까..

문제 보러 가기! 접근 전에 트리를 배우고 이 문제도 풀고 싶었다.. 문제는 간단하지만 어떻게 풀지 몰랐다가 스터디에서 이 문제를 다뤘다. 트리의 지름을 찾고 싶으면, 임의의 정점 x를 잡고 거기에서 가장 먼 정점 y를 찾으라고 했다. 그리고 y에서 가장 먼 정점 z가 있을 텐데, y와 z 사이의 거리가 트리의 지름이라고 하셨다. 뭔가 수학적으로도 설명해주셨고 쉽게 원그림으로도 설명해주셨다. 원 안의 어떤 점 x를 잡고 거기에서 젤 먼 점 y를 잡으면 어떻게 될까? x에서 원의 중심을 지나서 원의 호가 y가 될 것이다. 그리고 y에서 가장 먼 점 z를 찾으면, 원의 어떤 호에서 중심을 지나서 다른 호로 갈 것이다. 그럼 그게 원의 지름이 된다. 이 아이디어를 구현해봤다! 코드 import sys inpu..