정보 기술 놀이터

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net def solution(x): for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) return d[x] d = [0] * 1000000 x = 10 print(solution(x))# 3 DP 테이블인 리스트 d를 10^6만큼 초기화합니다. 그리고 사용 가능한 연산 기능 세 가지 중 가장 작은 값(최소 연산 값)을 ..

현실 세계에는 컴퓨터를 활용하더라도 최적의 해를 구하기에 시간이나 메모리 공간이 매우 많이 필요한 문제가 있습니다. 따라서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 합니다. 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 향상시킬 수 있는 방법이 있습니다. 그 중 하나가 바로 다이나믹 프로그래밍(Dynamic Programming)입니다. 다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(Top-Down)과 보텀엄(Bottom-Up) 2가지 방식이 있습니다. 다이나믹 프로그래밍은 다음의 조건을 만족하는 문제를 해..

이진 탐색(Binary Search)는 말 그대로 반으로 쪼개면서 탐색하는 방법입니다. 이 때, 이진 탐색 대상(리스트은 반드시 정렬되어 있어야만 사용할 수 있습니다. 이진 탐색은 순차 탐색과 달리 시작점, 끝점, 중간점 변수 3개를 이용합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정입니다. 정렬된 데이터에서 이진 탐색 방법으로 숫자 4를 찾는 과정은 다음과 같습니다. 순차 탐색은 처음부터 끝까지 탐색하기 때문에 시간복잡도는 O(N)이지만, 이진 탐색은 단계마다 2로 나누므로 시간복잡도는 O(LogN)입니다. 코딩테스트에서는 보통 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해야 주어진 시간안에 해결할 수 있습니다. 이..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def search(n, times, mid): cnt = 0 for t in times: cnt += mid // t return True if cnt >= n else False def solution(n, times): start = 0 end = min(times) * n mid = start while mid + 1 != end: mid = (start + end) // 2 if sear..

torchvision의 maskrcnn_resnet50_fpn을 이용하여 인스턴스 분할을 해보겠습니다. 시맨틱 분할, 인스턴스 분할에 대한 내용은 이곳을 확인해 주세요. torchvision은 파이토치에서 제공하는 데이터셋과 모델 패키지입니다. maskrcnn_resnet50_fpn은 말 그대로 ResNet50기반의 FCN 입니다. maskrcnn_resnet50_fpn은 pre-trained model이기 때문에 따로 학습할 필요가 없습니다. __prediction()은 Mask R-CNN 모델의 출력(masks, labels, boxes, scores)을 입력된 confidence에 따라 리턴합니다. __get_coloured_mask()는 입력 이미지(mask)에서 인스턴스의 색을 랜덤으로 설정하여..

torchvision의 fcn_resnet101을 이용하여 시맨틱 분할을 해보겠습니다. 시맨틱 분할에 대한 내용은 이곳을 확인해 주세요. torchvision은 파이토치에서 제공하는 데이터셋과 모델 패키지입니다. fcn_resnet101은 말 그대로 ResNet101 기반의 FCN 입니다. fcn_resnet101은 pre-trained model이기 때문에 따로 학습할 필요가 없습니다. 사용 방법은 간단합니다. 모델 출력의 'out'을 softmax를 이용하여 class를 분류하고 그 값을 픽셀값으로 사용하면 됩니다. 아래는 전체 코드입니다. [fcn.py] import torch import torchvision import torchvision.transforms as transforms from ..

torchvision의 fasterrcnn_resnet50_fpn을 이용하여 객체 탐지를 해보겠습니다. 객체 탐지에 대한 내용은 이곳을 확인해 주세요. torchvision은 파이토치에서 제공하는 데이터셋과 모델 패키지입니다. fasterrcnn_resnet50_fpn은 말 그대로 ResNet50 기반의 Faster R-CNN 입니다. fasterrcnn_resnet50_fpn은 pre-trained model이기 때문에 따로 학습할 필요가 없습니다. predictions의 boxes는 x, y, w, h 좌표이며 labels은 class index 값입니다. (0, 1, 2, ...) 마지막으로 scores는 probability으로, 기본적으로 값이 높은 순으로 정렬된 값을 얻을 수 있습니다. 위에 ..

정렬(Sorting)은 데이터를 어떠한 기준에 따라서 순서대로 나열하는 것입니다. 정렬 알고리즘은 가장 기본이 되는 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort)부터 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 계수 정렬(Count Sort) 등 매우 다양합니다. 코딩테스트에서는 Python 기본 정렬 라이브러리를 사용하면 충분히 빠른 시간내에(O(NlogN)) 정렬을 수행할 수 있습니다. 따라서, 정렬 라이브러리 사용 예제 몇 가지를 확인해 보겠습니다. def solution(arr): sorted_arr = arr.copy() sorted_arr.sort() # sorted_arr.sort(reverse=Tru..

탐색(Search)은 보통 많은 양의 데이터중에서 원하는 데이터를 찾는 것을 의미합니다. 프로그래밍에서는 그래프, 트리 등의 자료구조(Data structure)를 이용하여 탐색을 구현합니다. 탐색 방법 중 대표적인 것이 바로 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)입니다. DFS와 BFS를 구현하는 자료구조인 스택(Stack), 큐(Queue), 그래프(Graph)와 재귀 함수(Recursive Function)에 대한 설명은 생략하겠습니다. DFS는 그래프 탐색 과정에서 최대한 깊숙이 들어가서 노드를 방문한 후(리프 노드까지), 다시 돌아가 탐색하는 알고리즘입니다. DFS의 동작 과정은 다음과 같습니다. 1. 탐색 ..

객체 탐지는 경계 박스를 이용해 객체의 목록을 예측하는 것이었습니다. 하지만 경계 박스에는 객체 이외의 다른 객체가 중복될 수 있습니다. 특정 작업에서 이것은 중요한 문제가 될 수 있습니다. 시맨틱 분할(Semantic Segmentation)은 객체 탐지와 다르게 픽셀 단위로 레이블을 예측하는 방법입니다. 객체 탐지와 다른점은 같은 객체는 같은 색으로 분류된다는 점입니다. (양은 모두 주황색) 이와 유사하게 인스턴스 분할(Instance segmentation)은 각 객체를 따로 표현한것으로, 객체 탐지와 시맨틱 분할이 결합된 것입니다. 여기서 실제 픽셀값은 class값으로 예측됩니다. 이러한 시맨틱 분할은 의학 사진이나 자율 주행, 위성 이미지 등에서 많이 사용됩니다. 시맨틱 분할, 인스턴스 분할 모..