결국 빛나리라

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net > 큐 각 큐의 원소와 원소에 해당하는 순서를 함께 튜플로 묶어 큐에 추가함으로써 찾고자 하는 원소가 어디에 위치하는지 알 수 있도록 하는 것이 중요한 키포인트였다. 그리고 큐의 첫번째에 나와있는 튜플이 큐의 최댓값과 같다면 해당 튜플을 큐에서 빼주고 순서를 하나씩 증가시키면서 반복문을 진행하다가 찾고자 하는 원소가 나오면 반복문을 중단한다. 해당 원소가 몇번째에 큐에서 나오게됐는지를 알려주는 순서를..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net > 동적계획법 문제의 원리만 깨우치면 코드 작성은 그렇게 복잡하지 않은 문제였다. 4개의 타일로 만들 수 있는 모든 가짓수를 세려본다고 할 때 우리는 다음 그림과 같이 바로 이전 3개 타일의 경우의 수에 1을 붙이는 경우와 그 이전 2개 타일의 경우의 수에 00을 붙이는 경우를 생각해볼 수 있다. 단 숫자를 추가할 땐 뒤쪽에만 숫자를 붙여야 중복되는 수가 나오지 않는다는 것을 기억하자. 결과적으로 4개..

https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net > 정렬 정렬 기본 개념을 묻는 문제로 sort함수와 join을 사용해 해결가능하다.

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net > dfs 활용 연결되어있는 격자들에 방문처리하고 개수를 카운트한다는 점에서 dfs 알고리즘을 사용하였다. 먼저 격자 정보들을 2차원 배열형태로 입력한다. 아래 코드로 값을 입력받으면 숫자들이 모두 문자형태로 들어간다는 것을 기억하자. 그리고 격자에 방문했는지 여부를 보여주는 visited 배열과 격자의 상하좌우로 움직이기 위한 dx, dy 배열도 선언해준다. 행, 열 정보를 파라미터로 넣은 dfs..

1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net > 다이나믹 프로그래밍 7부터 시작하여 아래 그래프로 내려가며 최대가 되는 수를 찾는 문제이다. 위부터 아래로 내려오며 더한 값들이 최대가 되도록 하는 방법을 사용했다. 더한 값들이 최대가 되기 위해선 수에 더할 윗 값들 중 더 큰 수를 더할 수 있을 것이다. 한 행에서 맨 앞에 위치한 수나 맨 마지막에 위치한 수의 경우 위의 줄에서 더할 수 있는 수가 하나밖에 없으므로 다음 그림과 같이 그릴 수 있다. 해당 그림대로 수를 더해보면 다음과 같다. 맨 아래 줄에서 최대값인 30이 7에서..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net > 큐 활용 큐의 기본 개념을 묻는 문제이다. 마지막 원소가 남을 때 까지(큐의 길이가 1보다 클 때까지) popleft와 append를 반복한다.

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net > 이분 탐색 활용 탐색하는데 사용되는 시간효율성을 위해 이분탐색방법을 활용하였다. 기본 이분 탐색 개념에 중복되는 수의 개수를 카운트하는 아이디어만 생각할 수 있다면 풀 수 있는 문제였다. 먼저 입력값들을 받아오고 가지고 있는 카드들의 개수 정보를 담은 딕셔너리를 선언한다. 기본 이분 탐색 알고리즘에 중간값이 타겟과 같은 수 일 때 반환하는 값부분만 수정해주었다..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net > 정렬 알고리즘 이전 포스팅에 정리한 내용을 참고하면 파이썬의 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)의 시간복잡도를 보장한다. 해당 문제에서는 N의 최대개수가 100만이므로 NlogN은 약 600만이다. 파이썬에선 1초에 2000만번의 연산을 수행할 수 있다고 생각하면 정렬 알고리즘을 사용하여 충분히 해결가능하다.

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net > 스택 활용 리스트를 사용하여 스택 자료구조를 간단하게 구현할 수 있다.

파이토치로 배우는 자연어처리 책을 참고하여 작성했습니다. 이전 포스팅에선 임베딩의 개념에 대해서 정리해보았다. 이번 포스팅에선 사전 훈련된 임베딩 GloVe와 CNN모델을 활용하여 뉴스 카테고리를 분류하는 모델을 구축하는 코드를 리뷰해보고자 한다. 코드리뷰는 참고한 책에서 추가 보충 설명을 달아놓고 이해를 높이기 위함이므로 전체 코드를 보고 싶다면 코드 원본 출처에서 보도록 하자. ▶ 분석 개요 분석에 사용할 데이터는 AG 뉴스 데이터 셋으로 2005년에 수집한 뉴스 기사 모음이다. 해당 분석에서는 네가지 범주로 균등하게 분할된 뉴스 기사 12만개에서 뉴스 제목을 대상으로 카테고리를 예측하는 분류모델을 만들었다. ▶ 분석 과정 분석과정은 다음 그림과 같다. - 우선 텍스트를 정수로 매핑하기 위해 voca..