본문 바로가기

Tech

 (580)
[인프런] 최대 선 연결하기 문제설명 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 한다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지면 서로 선이 겹치지 않고 최대 몇 개의 선을 연결할 수 있는지 구하라 위 그림은 오른쪽 번호 정보가 4, 1, 2, 3, 9, 8. 5, 6, 10, 8로 입력되었을 때 선이 서로 겹치지 않고 연결할 수 있는 최대 선을 개수 6으로 구한 경우이다. 입력조건 첫 줄에 자연수 N(1
[인프런] 피자 배달 거리 문제설명 N by N 크기의 도시지도가 있다. 도시지도는 1 by 1 크기의 격자칸으로 이루어져 있다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 격자칸은 좌표(행번호, 열번호)로 표현된다. 행,열 번호 모두 1부터 N번까지 이다. 도시에는 각 집마다 '피자배달거리'가 있는데, 각 집의 피자배달거리는 해당 집과 도시에 존재하는 피자집들과의 거리 중 최솟값을 해당 집의 '피자배달거리'라고 한다. 집과 피자집의 피자배달거리는 $|x_1 -x_2| + |y_1 - y_2| $이다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 한다. 시장은 살리고자 하는 피자집 M개를 선택..
[인프런] 사다리 타기 문제설명 현수와 친구들은 과자를 사먹기 위해 사다리 타기를 한다. 사다리 표현은 2차원 배열로 되어 있으며, 0은 평면을 의미하고, 사다리는 1로 표현한다. 현수는 특정 도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고 싶다. 특정 도착지점은 2로 표시된다. 주어지는 지도의 크기는 10 by 10이다. 입력조건 10 by 10의 사다리 지도가 주어진다. 출력조건 출발지 열 번호를 출력한다. 사고과정 스스로 풀 때 위에서 출발해야 한다는 것 떄문에 0행의 모든 열에서 DFS 탐색을 수행하면서 마지막 행에서 도착지점이면 출력하도록 했다. 그런데 이렇게 구현하려 하니 방문 체크용 테이블을 구현하는 데 살짝 애를 먹었따.. 결국 구현은 했다. 풀이를 보니, 역발상으로 도착지점에서 역으로 올라갔..
[인프런] 토마토 문제설명 현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있ㅏ. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상..
[밑시딥] 단어의 분산을 표현하는 또 다른 기법, word2vec 🔊 해당 포스팅은 밑바닥부터 시작하는 딥러닝 2권의 교재 내용을 기반으로 자연어처리 딥러닝 신경망을 Tensorflow, Pytorch와 같은 딥러닝 프레임워크를 사용하지 않고 순수한 Numpy로 구현하면서 자연어 처리의 기초를 탄탄히 하고자 하는 목적 하에 게시되는 포스팅입니다. 내용은 주로 필자가 중요하다고 생각되는 내용 위주로 작성되었음을 알려드립니다. 이번 포스팅에서는 단어의 분산을 표현하는 또 다른 방법으로 신경망을 사용하는 추론 기법인 word2vec에 대해 배워본다. word2vec를 구현하기 위한 신경망 모델의 종류 중 하나로 CBOW 모델에 대해 알아보고 이를 넘파이로 구현하는 방법도 알아보자. 1. 추론 기법의 등장 단어의 분산을 표현하는 또 다른 방법으로 추론 기법이 등장했다. 그런데..
[인프런] 안전영역 문제설명 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한 후 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어지는지를 조사하려고 한다. 이 때, 문제를 간단하게 하기 위해, 장마철에 내리는 비의 양에 따라 일저한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표..
[인프런] 섬나라 아일랜드 문제설명 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하라. 입력조건 첫 줄에 자연수 N(3
[인프런] 단지 번호 붙이기 문제설명 그림1과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌,우 혹은 아래,위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 그림 2는 그림1을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성해라. 입력조건 첫 줄에는 지도의 크기 N(5
[인프런] 등산경로 문제설명 등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있다. 마을 뒷산의 형태를 나타낸 지도는 N by N 구역으로 나누어져 있으며, 각 구역에는 높이가 함께 나타나 있다. 만약 N=5 라면, 아래와 같이 표현된다. 어떤 구역에서 다른 구역으로 등산할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 한다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳이다. 출발지와 목적지는 유일하다. 지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 있는지 구하는 프로그램을 작성해라. 입려조건 첫 줄에 N(5
[인프런] 미로탐색 문제설명 7 by 7 격자판 미로를 탈출하는 경로의 총 가지수를 출력하는 프로그램을 작성해라. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7) 좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상,하,좌,우로만 움직인다. 미로가 다음과 같다면, 위 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 총 8가지이다. 입력조건 7 by 7의 격자판이 주어진다. 출력조건 첫 줄에 경로의 가지수를 출력한다. 사고과정 경로의 총 가지수를 구하는 것이므로 DFS를 활용해야 한다. 처음에 입력 인풋을 잘 못 넣어서 시간을 낭비했다...윾 어쩄건 백 트래킹을 활용해서 잘 구현해주었다! 풀이 arr = [list(map(int, input().split())) for _ in ra..
[인프런] 미로의 최단거리 통로 문제설명 7 by 7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성해라. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7) 좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상,하,좌,우로만 움직인다. 미로가 다음과 같다면, 위와 같은 경로가 최단 경로이며, 경로 수는 12이다. 입력조건 7 by 7 격자판의 정보가 주어진다. 출력조건 첫 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1을 출력한다. 사고과정 최솟값을 출력하라고 한 것에서 BFS를 캐치했어야 한다. 전형적인 BFS 문제로, 방문테이블을 새로 정의하여 방문하는 노드를 테이블에 체크해주어야 한다. 도달할 수 ..
[인프런] 사과나무(BFS로 풀기) 문제설명 저번에 구현 유형으로 풀어본 사과나무 문제랑 동일하다. 하지만 BFS로 풀어야 한다. https://techblog-history-younghunjo1.tistory.com/377 [인프런] 사과나무(다이아몬드) 문제설명 위 그림과 같이 N*N처럼 5*5로 사과나무가 존재할 때, 색깔로 칠해진 사과나무에 존재하는 사과들의 개수 합을 구하여라. 사과들의 개수는 한 칸 내에 있는 값을 의미한다. 사고과정 처 techblog-history-younghunjo1.tistory.com 사고과정 문제에서 요구하는 영역을 어떻게 상태트리로 만들어야 할지 도저히 몰랐다. 그래서 강의를 보고 아이디어만 보고 어느정도 구현은 했는데, BFS하는 레벨을 도중에 중간에 멈추는 것을 어떤 방식으로 해야할지에서 또 막..
[인프런] 송아지 찾기 문제설명 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성해라. 입력조건 첫줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력조건 점프의 최소횟수를 구한다. 사고과정 그동안 매번 DFS를 풀다가 이 문제를 풀 때도 자연스레 DFS로 풀려고 했다. 하지만 BFS로 풀어야 햇던 문제이다.. 아직 BFS에 대해서는 많이 ..
[밑시딥] 오직! Numpy로 단어의 분산 표현하기 🔊 해당 포스팅은 밑바닥부터 시작하는 딥러닝 2권의 교재 내용을 기반으로 자연어처리 딥러닝 신경망을 Tensorflow, Pytorch와 같은 딥러닝 프레임워크를 사용하지 않고 순수한 Numpy로 구현하면서 자연어 처리의 기초를 탄탄히 하고자 하는 목적 하에 게시되는 포스팅입니다. 내용은 주로 필자가 중요하다고 생각되는 내용 위주로 작성되었음을 알려드립니다. 이번 포스팅에서는 자연어 처리의 가장 기본인 단어의 분산 표현에 대해 알아보고 이를 넘파이로 구현하는 방법에 대해 알아보자. 1. 단어의 의미를 표현하는 방법 최근에는 대부분 딥러닝으로 단어의 의미를 표현하지만 딥러닝이 등장하기 이전에도 단어의 의미를 표현하는 방법들이 존재했다. 단어의 의미를 표현하는 방법에는 크게 3가지 방법이 존재한다. 시소러스..
[인프런] 알파코드 문제설명 철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암호화를 할 것인지 논의하고 있다. 영희는 알파벳 A를 1로, B는 2로, ..., Z는 26으로 할당해서 번호를 보내기로 하자고 제안한다. 하지만 철수는 이에 반대한다. 왜냐하면 만약 BEAN을 보내서 암호화하면 25114 이다. 그러면 이를 다시 알파벳으로 복원할 때는 많은 방법이 존재한다고 한다. 즉, 25114를 분할하는 여러가지 방법을 생각해보자. 2/5/1/1/4, 2/5/1/14, 2/5/11/4 ,... 등등.. 만약 호화된 코드가 주어지면 그것을 영희가 제안한 방법으로 알파벳으로 복원하는 데 얼마나 많은 방법이 있는지 구하라. 입력조건 첫줄에 숫자로 암호화된 코드가 입력된다. 단, 코드는 0으로..
[인프런] 동전 분배하기 문제설명 N개의 동전을 A, B, C 세명에게 나누어 주려고 한다. 세명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 하자. 단 세사람의 총액은 서로 달라야 한다. 입력조건 첫줄에는 동전의 개수 N(3
[인프런] 동전 바꿔주기 문제설명 명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각 $n_1, n_2, ..., n_k$개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꾸어 주려고 한다. 이 때, 동전 교환 방법은 여러가지가 있을 수 있다. 예를 들어, 10원, 5원, 1원 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다. 20 = 10원 x 2개 20 = 10원 x 1개 + 5원 x 2개 20 = 10원 x 1개 + 5원 x 1개 + 1원 x 5개 20 = 5원 x 3개 + 1원 x 5개 입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의 금액 $p_i$와 개수 $n_i$가 주어질때 지폐를 동전으로 교환하는 방법의 가지 수를 계산해라...
[인프런] 양팔저울 문제설명 무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울은 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, 아래 표의 사각형은 그릇을 나타낸다. 만약 추의 무게가 {1, 5, 7} 이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담..
[밑시딥] 오직! Numpy로 구현했던 딥러닝 신경망 복습 🔊 해당 포스팅은 밑바닥부터 시작하는 딥러닝 2권의 교재 내용을 기반으로 자연어처리 딥러닝 신경망을 Tensorflow, Pytorch와 같은 딥러닝 프레임워크를 사용하지 않고 순수한 Numpy로 구현하면서 자연어 처리의 기초를 탄탄히 하고자 하는 목적 하에 게시되는 포스팅입니다. 내용은 주로 필자가 중요하다고 생각되는 내용 위주로 작성되었음을 알려드립니다. 이번 포스팅부터는 밑바닥부터 시작하는 딥러닝 2권을 학습하면서 배운 내용을 기록해보려 한다. 2권은 주로 자연어 처리에 관련된 내용이다. 필자는 개인적으로 Weekly NLP를 통해서 자연어 처리에 입문했었는데, 그 때는 이론적인 측면에서 접근했다고 한다면 이번엔 이론을 더 깊게 파보면서 넘파이로 구현하는 과정까지 어떻게 신경망으로 자연어 처리를 할..
[인프런] 퇴사 문제설명 저번에 다이나믹 프로그래밍으로 풀어본 퇴사 문제이다. 이번에 브루트포스(완전탐색)인 DFS를 활용해 해당 문제를 풀어보자. https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 사고과정 스스로 풀 때 상태트리를 만드려고 하는데, 여러갈래 길로 만들었다.. 1일차를 상담할때, 2일차를 상담할때,, 이런식으로..애써 구현은 했는데, 테스트 케이스 일부가 틀려서 구현 실패했다.. 강의를 보니 두 갈래길로 상태트리를 만들어야 했다. 1일차 상담을 했는지 안했는지로, 만약 했다면 1일차 상담 하는 데 걸린 시간 이후의 k일차의 상담으로 이동해서 탐색한다. 만약 1일차 상담하지 않았다면 ..

티스토리툴바