이것저것 기록

* 의 문제 03를 정리한 내용입니다. 1. 동명이인 찾기 알고리즘 설명: 집합(set)을 사용하여 중복된 값을 찾는 문제이다. 입력으로는 n명의 이름이 있는 리스트가 들어가고, 이 중 중복되는 이름을 제외하고 unique 이름만 집합으로 반환해야한다. 주의 해야하는 포인트: 비교할 이름을 뽑은 다음에는 순서상 뒤에 이름들 하고만 비교하면 된다. 순서상 앞에 있는 이름들 하고는 비교할 필요가 없다. 리스트의 마지막 이름을 기준으로는 비교하지 않아도 된다. 마지막보다 한 번째 앞의 이름과 이미 비교가 끝났다. 같은 이름을 찾으면 결과(result) 집합에 해당 이름을 추가한다. 사용하는 함수: 함수 설명 len(s) 집합의 길이를 구함 add(x) 집합에 x라는 자료를 추가함 discard(x) 집합에 자..

1. O (빅 오) 표기법 알고리즘의 대략적인 성능을 표시하는 방법 입력 크기 n과 필요한 계산 횟수와의 관계에 주목하는 표현 방법 계산 복잡도는 특별한 언급이 없다면 시간 복잡도를 의미하는 것이지만 본래 계산 복잡도는 시간 복잡도(time complexity), 공간 복잡도(space complexity)로 두가지가 있음 시간 복잡도 (Time Complexity): 특정한 크기의 입력에 대해서 알고리즘이 소요하는 시간이 얼마나 되는가? 공간 복잡도 (Space Complexity): 특정한 크기의 입력에 대해서 알고리즘이 사용하는 컴퓨터 자원(메모리)이 얼마나 되는가? 2. O(n) & O(1) 0부터 n까지의 총 합을 구한다고 가정해보자. 두 가지 방법이 있다. 0+1+2+ ... + n 과 같이 ..