그리디 그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 방법으로 불리는 알고리즘 패러다임이다. 최적해를 구하기 위해 전후 단계에서의 선택은 고려하지 않고 각 단계마다 정해진 기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다. 그리디 방법을 적용하면...

해시 테이블 해시 테이블은 각 위치(슬롯)마다 주소가 부여되어 있는 저장공간으로 기본적으로는 배열의 형태로 볼 수 있다. 탐색 키값을 활요하여 해시 테이블의 주소를 계산하면, 이 주소를 통해 원하는 데이터를 해시 테이블에서 직접적이고 빠르게 탐색할 수 있다. 해시 테이블은 평균적으로 O(1)의 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있기 때...

AWS

스터디 시작 정글을 마치고 무엇을 하면 좋을지 몰라 스터디를 모집해봤다. 다행히 같이 하겠다는 사람들이 꽤 있어서 모집은 순탄했으나, 스터디를 해본 적이 없어서(…) 관련 자료들을 찾다가 애를 먹었다. 스터디에서 사람들이 기대하는 효과가 무엇일까? 어떤 방식으로 진행해야 하는가? 무슨 내용을 집중적으로 공부해야 할까? 등등의 고민들을 안고 인터넷...

동적 프로그래밍 우선 전혀 동적이지 않다. 옛날 수학자인 벨만이라는 사람이 고안해낸 기법인데, 그저 단어가 멋있어서(?) 연구비를 위해 선택했다는 일화가 있다(…). 동적 프로그래밍(Dynamic Programming)은 최적화 이론의 한 기술이며, 복잡한 문제를 쪼개어 간단한 부분 문제로 나눈 후에 답을 구하고, 이를 사용해 더 큰 문제의 답을 ...

분할 정복 분할 정복 방법은 하나의 크고 어려운 문제를 두 개 이상의 작고 간단한 하위 문제들로 재귀적으로 분할하고, 이렇게 분할된 문제들을 각각 해결한 후에 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 알고리즘 패러다임이다. 각 호출 시마다 다음과 같은 세 단계의 작업이 이루어진다: 분할(divide) : 주어진 문제를 여러 개의 ...

탐색 컴퓨터 과학에서 탐색이란 여러 개의 원소로 구성된 데이터가 주어졌을 때, 그중에서 원하는 값을 갖는 원소를 찾는 것을 말한다. 데이터의 형태는 리스트, 트리, 그래프 등 다양한 형태가 가능하다. 이진 탐색 이진 탐색, 또는 이분 탐색이란 정렬된 형태로 주어진 원소에 대해 탐색 대상의 크기를 절반씩 줄여 가면서 탐색 키를 가진 원소를 찾는 방...

문제 설명 문제 링크 문제를 살펴보면 제목이 제시하듯 버블 소트 코드가 주어지고, 출력되는 것은 for문이 실행된 횟수이다. 이에 따라 버블정렬 코드를 아래와 같이 작성해보았으나, 시간 초과가 떴다… 코드 import sys input = sys.stdin.readline def bubbleSort(arr, start): for ...

정의 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태 교착상태와 기아상태의 차이 교착상태 영원히 멈춰있다 기아상태 언젠가는 시행될 가능성이 있다 교착상태의 특성 필요조건 상호배제 점유대기 비선점 환형대기 (순환대기) 네 가지 조건이 ...

생산자-소비자 문제 정의 두 협력 프로세스 사이에 버퍼를 두고 생산자와 소비자의 상황을 다루는 문제 생산자: 데이터를 넣는 프로세스 소비자: 데이터를 꺼내는 프로세스 조건 버퍼에 여러 프로세스에 동시에 접근할 수 없음 버퍼에 데이터를 넣는 동안에는 데이터를 꺼낼 수 없다. 버퍼에서 데이터를 ...