'🐺 매일 알고리즘' 카테고리의 글 목록 (4 Page)

본문 바로가기

🐺 매일 알고리즘

Sieve of Eratosthenes, 에라토스테네스의 체 에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를 찾기 위한 간단한 알고리즘이다.1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.3. 해당 숫자의 배수들을 집합에서 모두 지운다. 4. 2로 돌아간다. 끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.- 모든 합성수composite number 는 최.. 더보기

코딩테스트에서 요구되는 시간복잡도 어림잡기 온라인 코딩 테스트에서는 제한시간내에 문제의 따른 정확한 값을 반환하는 프로그램을 작성해야한다. 제한시간내에 동작하는 프로그램을 작성하기 위해서 어떻게 해야할까? 컴파일러, 각 컴퓨터의 프로세서의 차이 등이 실행시간에 영향을 끼치겠지만, 컴퓨터는 평균적으로 10**8개의 연산을 1초이내에 수행할 수 있다. 이를 기준으로 시간제한과 주어진 데이터 크기 제한에 따른 시간복잡도를 예측하고 그것에 맞게 답안을 작성하는 편이 더 빠른 솔루션이 있지않을까 고민하는 것 보다 효율적이다. 데이터 크기 제한 예상되는 시간 복잡도 n 더보기

Asymptotic analysis, 점근적 표기법. 알고리즘의 성능을 분석하기위해 점근적 표기법을 이용해 시간복잡도 사용한다. 단순히 특정 입력 값에 따른 실행시간(running time)을 비교하는게 아니라, 입력값이 증가함에 따른 Running time의 rate of growth를 표현한 것이 시간 복잡도(time complexity)이다. Big-theta Running time에 대한 점근적인 한계값을 Big theta라 한다. 즉, 알고리즘의 평균 시간복잡도를 말한다. Big-O 빅오는 running time에 대한 점근적인 상한값을 말한다. 즉, 알고리즘의 최악의 시간 복잡도이다. 보편적으로 ‘시간 복잡도’는 최악의 케이스를 커버하능 빅오를 말한다. Big-omega 빅 오메가는 running time에 대한 점근적인 하한값을 말한다.. 더보기

Binary search, 이진 탐색 리스트 A = [ 0, 1, ,2, 3 ] 이 있을 때, 마지막 원소인 '3'을 찾는다고 해보자. Simple search, 단순 탐색의 경우처음부터 순차적으로 원소 값을 확인한다. 마지막에 위치하고 있는 원소인 '3'을 찾기 위해서는 리스트의 길이와 같은 시간이 걸린다. 리스트의 길이와 같은시간을 O(n), linear time 선형시간 이라고 한다. Binary search, 이진 탐색은리스트의 중간에 있는 원소의 크기에 따라 탐색할 구간(range)를 반씩 줄여나가 O(log n), logarithm time 로그 시간이 걸리는 방식이다. 만약 100개의 원소를 가지고 있는 리스트라면 탐색할 구간이 100 에서 50, 25, 13, 7, 4, 2, 1 순으로 줄어든다. 따라서, A의 중간에 위치한 .. 더보기

완주하지 못한 선수 완주하지 못한 선수문제풀러가기 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.completion의 길이는 participant의 길이보다 1 작습니다.참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.참가자 중에는 동명이인이 있을 수 있습니다. def solution(participant, completion): answer = '' comp = completio.. 더보기

나머지 한 점 나머지 한 점풀어보러가기 직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다. 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요. 단, 직사각형의 각 변은 x축, y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다.제한사항v는 세 점의 좌표가 들어있는 2차원 배열입니다.v의 각 원소는 점의 좌표를 나타내며, 좌표는 [x축 좌표, y축 좌표] 순으로 주어집니다.좌표값은 1 이상 10억 이하의 자연수입니다.직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 [x축 좌표, y축 좌표] 순으로 담아 return 해.. 더보기

프로그래밍 문제풀이과정 분석하기 종만북의 문제해결개관 파트를 읽고 문제풀이시에 실천하기 위해 정리하였습니다. 코딩테스트 또는 프로그래밍 대회의 문제를 잘 풀기 위해 필요한 능력은 알고리즘 & 자료구조 & 사용하는 컴퓨터 언어의 문법과 특징 등에 대한 배경지식, 자신이 아는 것을 이용해 문제를 풀어내는 문제해결능력, 생각해낸 문제해결방법을 정확히 구현해내는 구현력이다. 문제해결능력을 키우기 위해서는 문제를 많이 풀어보아야 한다. 하지만 막연한 시도를 반복하는 것만으로는 부족하다. 문제를 푸는 방식을 연마하기 위해 자신이 문제를 어떻게 풀고 있는지, 어떤 방향으로 개선해야하는지 끊임없이 파악해야한다. 아래와 같이 문제를 푸는 과정을 여러 부분으로 나눠보고 각 과정을 자신이 잘하고 있는지, 어떤 방향으로 개선해야하는지 알아보자. 1. 문제 .. 더보기

Algorithm week 1: Union-Find Algorithms, Part 1: week1 Lecture note: I implemented codes in python3. Steps to developing a usable algorithm.􀉾 Model the problem. ( try to understand the main elements of the problem that needs to be solved. )해결해야하는 요소를 이해하고 문제를 모델링한다.􀉾 Find an algorithm to solve it.문제를 해결할 수 있는 알고리즘을 알아낸다.􀉾 Fast enough? Fits in memory?충분히 빠른지, 메모리 사용량은 적당한지 고려한다.􀉾 If not, figure out why.아니라면, 왜 그런지 알아낸다.􀉾 Fin.. 더보기

이전 1 2 3 4 5 다음

티스토리툴바