Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 그리드분할
- STL
- GIS
- 지하철역좌표
- MESH
- geojson
- pyvista
- 도커 레이어
- 데이터입수
- osmnx
- Set
- geopandas
- Python
- 귀여운고래
- 3d
- 도커
- docker
- 이미지빌드
- 컨테이너
- GNN
- 3d데이터
- 폴더조사
- python최단거리
- 파이썬
- 패치분할
- 알고리즘
- GCN
- 동명이인찾기
- graph
- 좌표거리
Archives
- Today
- Total
이것저것 기록
[알고리즘] 동명이인 찾기 알고리즘 (set) 본문
* <모두의 알고리즘 with 파이썬>의 문제 03를 정리한 내용입니다.
1. 동명이인 찾기 알고리즘
- 설명: 집합(set)을 사용하여 중복된 값을 찾는 문제이다. 입력으로는 n명의 이름이 있는 리스트가 들어가고, 이 중 중복되는 이름을 제외하고 unique 이름만 집합으로 반환해야한다.
- 주의 해야하는 포인트:
- 비교할 이름을 뽑은 다음에는 순서상 뒤에 이름들 하고만 비교하면 된다. 순서상 앞에 있는 이름들 하고는 비교할 필요가 없다.
- 리스트의 마지막 이름을 기준으로는 비교하지 않아도 된다. 마지막보다 한 번째 앞의 이름과 이미 비교가 끝났다.
- 같은 이름을 찾으면 결과(result) 집합에 해당 이름을 추가한다.
- 사용하는 함수:
함수 | 설명 |
len(s) | 집합의 길이를 구함 |
add(x) | 집합에 x라는 자료를 추가함 |
discard(x) | 집합에 자료 x가 들어있다면 삭제함 |
clear | 집합의 모든 자료를 지움 |
x in s | 어떤 자료 x가 집합 s에 들어있는지 확인함 |
update(x) | 집합에 여러 개의 값을 한꺼번에 추가함 |
remove(x) | 집합에 자료 x가 들어있다면 제거함 |
2. 집합 (set)
- 이 문제에서 사용하는 집합 자료형은 크게 두 가지 특징이 있다. 첫 번째, 중복을 허용하지 않는다. 두 번째, 순서가 없다. 중복을 허용하지 않는다는 점에서 딕셔너리와 유사한 면이 있다. 이러한 특징 때문에 중복을 제거하기 위한 필터 역할로 종종 사용하는 자료형이다.
- 하지만 순서가 없기 때문에, set 자료형에 저장된 값을 인덱싱으로 접근하려면 튜플이나 리스트로 변환 후 사용해야한다.
3. 알고리즘 풀이
3.1 동명이인을 찾는 알고리즘
def find_same_name(a):
n = len(a)
result = set()
for i in range(0, n-1):
for j in range(i+1, n):
if a[i] == a[j]:
result.add(a[i])
return result
name = ['Tom', 'Jerry', 'Mike', 'Tom']
print(find_same_name(name))
3.2 두 명을 뽑아 짝을 짓는 알고리즘
- n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘
def pair_name(a):
n = len(a)
result = set()
for i in range(0, n-1):
for j in range(i+1, n):
result.add((a[i], a[j]))
return result
name = ['Tom', 'Jerry', 'Mike', 'Tom']
print(pair_name(name))
'코린이 > 코딩 기초 & 알고리즘 공부' 카테고리의 다른 글
[알고리즘] 재귀함수 - 최대공약수, 피보나치 수열 (0) | 2021.07.17 |
---|---|
[알고리즘] 재귀함수 - 팩토리얼 구하기 (0) | 2021.06.20 |
[알고리즘] 최댓값, 최댓값 위치를 찾는 알고리즘 (0) | 2021.06.13 |
[알고리즘] 계산 복잡도(시간 복잡도)란? (0) | 2021.06.13 |
[python] exec()을 사용하여 동적 코드 실행하기 (0) | 2021.05.01 |
Comments