본문 바로가기

Tech

 (580)
[Python] 모든 지점에서의 최단경로를 찾는 플로이드 워셜(Floyd-Warshall) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 또 다른 최단 경로 알고리즘인 플로이드 워셜 알고리즘에 대해 알아보려고 한다. 저번 포스팅에서 배운 다익스트라(Dijkstra) 알고리즘은 특정 노드라는 시작 노드 1개를 지정하고 그 시작 노드에서 다른 노드들 까지의 최단거리를 구하는 방법이었다. 하지만 플로이드 워셜 알고리즘은 시작 노드를..
[Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 저번 시간에 배웠던 다익스트라 알고리즘의 간단한 구현 방법에 이어 이를 개선한 우선순위 큐 즉, heapq를 활용한 개선된 다익스트라 알고리즘에 대해 알아보려고 한다. 다익스트라의 구현 개념에 대해서는 거의 유사하므로 해당 포스팅에서는 우선순위 큐를 어떤 부분에 활용하고 Python으로 구현..
[Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의' '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 최단 경로를 찾는 데 자주 사용되는 다익스트라(Dijkstra) 알고리즘 개념에 대해 알아보고 Python으로 구현하는 방법에 대해 알아보려고 한다. 다익스트라 알고리즘은 최단 경로 알고리즘 종류 중 하나이다. 말 그대로 특정 지점에서 다른 특정 지점까지의 최단 경로를 구한다거나 모든 지점..
[Docker] 내가 만든 image를 Docker Hub에 Push시켜 공유하자 🔊 해당 포스팅은 이고잉님의 생활코딩 오픈튜토리얼의 Docker 입문 수업을 듣고 제 개인적으로 정리하는 목적하에 작성되는 포스팅입니다. 보다 자세한 강의는 여기를 참고해주세요. 이번 포스팅에서는 내가 만든 이미지를 Docker Hub이라는 레지스트리 사이트에 Push 시켜서 공유하는 방법에 대해 알아보자. Docker Hub은 Docker 포스팅 초반에도 소개했다시피 누구나 자기만의 이미지를 만들어 공유할 수 있고 pull해서 다운로드 받을 수 있는 사이트이다. 마치 Github의 public 레포지토리 처럼 말이다. 가장 먼저 해야할 것은 Docker Hub 사이트로 가서 회원가입을 하고 Repository 탭에 들어가서 내가만든 이미지를 push 시킬 개인 레포지토리를 생성한다. 이 때 모두가 볼 ..
[Docker] build와 Dockerfile로 나만의 이미지를 만들어보자 🔊 해당 포스팅은 이고잉님의 생활코딩 오픈튜토리얼의 Docker 입문 수업을 듣고 제 개인적으로 정리하는 목적하에 작성되는 포스팅입니다. 보다 자세한 강의는 여기를 참고해주세요. 저번 포스팅 말미에서 잠깐 소개한 build 명령어와 Dockerfile 파일로 내가 만든 컨테이너를 나만의 이미지로 만드는 방법에 대해 소개했었다. 이번 포스팅에서는 그것들에 대한 사용법을 좀 더 자세하게 알아보려고 한다. 그런데 저번 포스팅에서 내가 만든 컨테이너를 나만의 이미지로 생성하는 방법 중 하나로 commit 명령어에 대해 알아보았다. 그렇다면 build 명령어와 Dockerfile을 활용하는 방법과 무슨 차이가 있을까? 가시적인 가장 큰 차이점은 내가 만든 이미지가 어떤 과정 즉, 어떤 프로그램이 설치되고 어떤 ..
[이코테] 구현 - 문자열 재정렬 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이 때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. 예를 들어, K1KA5CB7 이라는 문자열이 주어지면 ABCKK13을 출력한다. 입력조건 첫째 줄에 하나의 문자열 S가 주어진다.(1
[이코테] 그리디 - 곱하기 혹은 더하기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 곱하기 혹은 더하기 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 숫자를 구하는 프로그램을 만들어라. 단, 더하기 보다 곱하기를 먼저 계산하는 일반적인 사칙연산 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다. 예를 들어, 02984라는 문자열이 주어진다면, 만들어질 수 있는 가장 큰 수는 순서대로 0+2 * 9 * 8 * 4 = 576 이다. 또한 만들어질 수 있는 가장 큰 수는 ..
[이코테] 이진탐색 - 정렬된 배열에서 특정 수의 개수 구하기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이 때 이 수열에서 x가 등장하는 횟수를 계산하여라. 예를 들어 수열 [1, 2, 2, 2, 2, 3]이 있을 때, x = 2 라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다. 단, 이 문제는 시간 복잡도 $O(logN)$으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받게 된다. 입력조건 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다.(1
[Python] 알고리즘을 위한 주요 라이브러리와 유의점 이번 포스팅에서는 Python으로 알고리즘 문제를 해결할 때 주로 사용하는 라이브러리와 유의점에 대해 알아보려고 한다. 해당 라이브러리들을 적절히 사용하면 손쉽게 문제를 해결할 때가 종종 있다고 한다. 해당 포스팅에서 소개하는 주요 라이브러리들 이외에는 여기를 참고해서 확인해보자. 이외의 라이브러리들도 사용해서 문제를 해결하는 경우도 자주 있다고 하니 해당 링크를 참고해서 찾아 사용하는 습관을 기르는 것을 권장한다. 1. 내장함수 내장함수란, print 문이나 input 문 같은 기본 입출력 기능부터 sorted 같은 정렬 기능을 포함하는 기본 내장 라이브러리다. 1-1. sum sum 함수는 iterable한 객체(리스트, 딕셔너리, 튜플, 집합자료)가 입력으로 주어졌을 때, 모든 원소의 합을 반환한다..
[이코테] 정렬 - 국영수 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이 때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 만들어라. 국어 점수가 감소하는 순서로(감소 = 내림차순) 국어 점수가 같으면 영어 점수가 증가하는 순서로(증가 = 오름차순) 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로(감소 = 내림차순) 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로(문자열 사전 순으로 증가 = 오름차순) 든, 아스키 코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다) 입력조건 첫째 줄에 도현이네 반..
[이코테] BFS - 특정 거리의 도시 찾기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하여라. 또한 출발 도시 X에서 출발 도시 X로 가는 최단거리는 항상 0이라고 가정한다. 입력조건 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 X가 주어진다.(2
[이코테] 구현 - 럭키 스트레이트 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 이 문제는 쉽게 풀렸지만 필자가 풀이한 방법 2가지, 책에서 제공하는 풀이 1가지 총 3가지 풀이 방법에 대해 소개하려고 한다. 각 풀이에 사용된 문법들이 다른 어려운 문제에도 분명히 쓰일 수도 있을 것 같아 기록하려고 한다. 문제설명 게임의 아웃복서 캐릭터는 필살기인 '럭키 스트레이트' 기술이 있다. 이 기술은 매우 강력한 대신에 게임 내에서 정수가 특정 조건을 만족할 경우에만 사용이 가능하다. 특정 조건이란, 현재 캐릭터의 점수를 N이라고 할 때, 자릿수를 기준으로 정수 N을 반으로 나누어 왼쪽 부분의 각 자릿수 합과 오른쪽 부분의 자릿수 합..
[이코테] 그리디 - 모험가 길드 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정하는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. 동빈이는 최대한 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. 동빈이를 위해 N명의 모험가에 대한 정보가 주어질 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하여라. ..
[ML] 정규분포, Xaiver, He 파라미터 초기화 방법 이번 포스팅에서는 딥러닝 모델에서 파라미터를 초기화 하는 방법으로서 정규분포 방법, Xaiver, He 방법에 대해 알아보기로 하자. 파라미터 초기화하는 방법을 어떻게 하느냐에 따라 딥러닝 모델에서 Gradient 소실 또는 발산 문제를 발생시키는지 여부를 결정할 만큼 중요하다. 먼저 정규분포 또는 표준정규분포 방식으로 파라미터를 초기화하는 방법에 대해 알아보자. 1. 표준정규분포로 파라미터 초기화 하기 표준정규분포는 알다시피 정규분포를 평균이 0, 분산이 1인 분포로 변환하는 방법이다. 수치형 값들을 스케일링하는 방법에도 자주 활용된다. 이러한 표준정규분포 방법을 활용해 파라미터를 초기화시킬 수 있다. 그런데 표준정규분포를 활용해 파라미터를 초기화 하면 어떻게 될까? 우선 표준정규분포로 파라미터를 초기..
[Docker] 내가 만든 Container를 image로 만들자!(commit, build, Dockerfile 활용하기) 🔊 해당 포스팅은 이고잉님의 생활코딩 오픈튜토리얼의 Docker 입문 수업을 듣고 제 개인적으로 정리하는 목적하에 작성되는 포스팅입니다. 보다 자세한 강의는 여기를 참고해주세요. 이번 포스팅에서는 Docker를 활용해 내가 만든 컨테이너를 이미지로 만드는 방법인 commit 활용방법에 대해 알아보려고 한다. Docker 관련 명령어의 관계를 도식화 하게되면 다음과 같다. 우리는 보통 Docker Hub에서 누군가가 만들어 놓은 이미지를 pull 해서 그 이미지에서 컨테이너를 내 맘대로 생성해 사용한다. 그렇다면 우리도 우리만의 이미지를 만들 수 있지 않을까? 예를 들어, 우리가 ubuntu 라는 리눅스 이미지를 pull 해서 컨테이너를 생성 후 생성한 컨테이너 안에 Python이나 git을 설치했다. 그..
[이코테] 다이나믹프로그래밍 - 효율적인 화폐 구성 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 N가지 종류의 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록하려고 한다. 이 때 각 화폐는 몇 개라도 사용가능하며 사용한 화폐의 구성은 같지만 순서가 다른 것은 같은 경우로 구분한다. 입력조건 첫째 줄에 N, M이 주어진다.(1
[이코테] 다이나믹프로그래밍 - 바닥 공사 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하여라. 입력조건 첫째 줄에 N이 주어진다.(1
[이코테] 다이나믹프로그래밍 - 개미 전사 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려 한다. 메뚜기 마을엔 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식랴창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해..
[이코테] 다이나믹프로그래밍 - 1로 만들기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. X가 5로 나누어 떨어지면 5로 나눈다. X가 3으로 나누어 떨어지면 3으로 나눈다. X가 2로 나누어 떨어지면 2로 나눈다. X에서 1을 뺀다. 정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오 입력조건 첫째 줄에 정수 X가 주어진다.(1
[이코테] 이진탐색 - 떡볶이 떡 만들기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 동빈이네 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어, 높이가 19, 14, 10, 17 cm인 떡이 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 그리고 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm가 된다. 이 때 손님은 잘린 떡의 길이의 총 합인 6cm의 ..

티스토리툴바