삶을 낙원으로

📚 문제 링크 : 집합 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 🔍 문제 이해 add, remove 등의 명령이 주어질 때 그에 알맞는 연산을 수행하는 문제다. 파이썬 집합 연산 set : 집합 선언 add : 집합에 원하는 요소 추가 discard : 원하는 요소 제거 - 집합 내에 해당 요소가 없더라도 오류 발생하지 않음 remove : 원하는 요소 제거 - 집합 내에 해당 요소 없을 경우 오류 발생 🔑 해결 코드 import sys m = int(input()) s = set() for i in range(m): line = list..

📚 문제 링크 : 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔍 문제 이해 기본적인 DP : 동적프로그래밍 문제다. 연산은 총 3개다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 🔑 해결 코드 x = int(input()) # 최소 연산 횟수를 저장하는 배열 d = [0] * (x+1) # 2부터 x까지 모든 숫자에 대한 최소 연산 횟수 계산 for i in range(2, x+1): # 1을 뺀 경우를 고려 d[i] = d[i-1] + 1 # 3으로 나눠지면 3으로 나눈 연산 고려 if i % 3 == 0: # 현재까지 계산된 최소횟수와 3으로 ..

📚 문제 링크 : 폴리오미노 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 🔍 문제 이해 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하는 문제다. '.'와 'X'로 이루어진 보드판이 주어졌을 때, 'X'를 모두 폴리오미노로 덮고 '.'는 폴리오미노로 덮으면 안 된다. AAAA와 BB 폴리오미노로 덮는게 불가능할 경우 -1을 출력한다. 🔑 해결 코드 board = input() result = '' # 정답을 저장할 문자열 i = 0 while i < len(board): if board[i:i + 4] == 'XXXX': result += 'AAAA' i += 4 elif board[i:i+2] =..

📌 Transformer 기존의 Seq2Seq with Attention 모델은 decoder의 각 time step에서부터 encoder의 hidden state vector들 중 원하는 정보를 가져가 사용하는 attention module로 구성 encoder, decoder는 RNN기반의 model로 구성 transformer에서는 attention module이 encoder, decoder에 사용되는 sequence 자체를 encoding하는 역할 수행 Q. 기존 RNN을 이용해 sequence data 처리할 때 문제점 A. Long-term Dependency 여러 time step에 걸쳐 전달되면서 gradient 정보가 변질되어 학습이 잘 이뤄지지 않는 문제 발생 그래서 바로 필요한 정보..

📚 문제 링크 : 트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔍 문제 이해 트리 알고리즘을 이용해 노드의 부모 노드 번호를 출력하는 문제다. 🔑 해결 코드 import sys # 재귀 깊이 늘려주기 sys.setrecursionlimit(10**9) n = int(input()) graph = [[] for _ in range(n + 1)] parent = [0] * (n + 1) # 그래프, 간선 생성 for i in range(n - 1): x, y = map(int, sys.stdin.readline().split()) graph[x].appen..

📚 문제 링크 : 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 🔍 문제 이해 트리 알고리즘을 사용하는 문제다. 컴퓨터가 노드를 의미하고 1번 컴퓨터(노드)에 연결된 컴퓨터의 수를 구하는 문제다. 🔑 해결 코드 import sys n = int(input()) # 컴퓨터(노드) 수 입력 m = int(input()) # 간선 수 입력 # 그래프 생성, 방문 여부 리스트 초기화 graph = [[] for _ in range(n + 1)] visit = [0] * (n + 1) # 그래프 생성 for i ..

📌 Recurrent Neural Networks sequence data에 특화된 형태를 띈다. 시간에 따라 변화하는 신호가 순차적으로 돌아온다고 한다. 시간 t에서 입력 신호 : x_t 그 이전 시간 t-1에서 RNN function이 계산했던 Hidden state vector : h_t-1 위 두 가지를 입력으로 받아 현재 time step에 RNN module의 output인 h_t, current state vector를 만듦. 매 time step마다 동일한 function인 f_w를 반복적으로 수행 prediction을 해야하는 time step의 경우 RNN의 현재 time step의 output인 Hidden state vector, h_t를 다시 입력으로 output layer에 전달..

📌 Basic Idea of ConvNets 모든 요소들을 규정해서 특성을 정의하는 것이 아니다. 일관되게 나타나는 부분, 부분 별로의 특징들을 검출하고 조합해서 인식하는 방식으로 동작한다. 2012년부터 AlexNet이후 이미지 분류 성능이 빠르게 향상 2015년부터는 사람의 물체 인식 성능보다 더 좋아지는 양상을 보임 📌 How ConvNet Works 예) 이미지가 X인지 O인지 구분하는 task X와 O 이미지는 한가운데 정석적으로 주어질 수도 있으나 아래와 같이 정석적이지 않은 이미지에 대해서도 잘 분류 가능해야 한다. Q. 표준화된 형태의 X와 변형된 형태의 X가 같은 class에 속한다는 것을 어떻게 구분하나?? 위 그림과 같이 하얀 픽셀을 1, 어두운 픽셀을 -1이라 했을 때 위 두 그림을..

📚 문제 링크 : 상근이의 여행 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 🔍 문제 이해 국가의 수, 비행기 종류가 주어질 때 타야하는 최소 비행기의 수를 구하는 문제다. 비행기의 종류 = 간선의 수 국가의 수 = 노드 수 라고 볼 수 있는 트리 문제다. 🔑 해결 코드 import sys def DFS(graph, node, visit, cnt): visit[node] = 1 for adjacent in graph[node]: if visit[adjacent] == ..

DFS와 BFS 모두 그래프를 탐색하는 방법이다. 📌 DFS (Depth First Search) : 깊이 우선 탐색 스택, 재귀 사용해 구현 검색 속도는 BFS 보다 느림 현재 노드에서 갈 수 있는 노드까지 계속 탐색 경로마다 특징 저장할 필요 있을 때 사용 구현 방법 탐색 시작 노드를 스택에 삽입, 방문 처리 스택의 가장 위 노드에 방문하지 않은 노드 있을 경우 해당 노드를 스택에 삽입 후 방문 처리, 방문하지 않은 노드 없을 경우 가장 위 노드 꺼내기 위 두 과정을 수행할 수 없을 때까지 반복 📌 BFS (Breadth First Search) : 너비 우선 탐색 큐 사용해 구현 선입선출 현재 노드에서 가까운 노드부터 탐색 최단거리 구할 때 사용 구현 방법 탐색 시작 노드를 큐에 삽입, 방문 처리 ..