TIL (2022.03.30)

1. iterator

c++
STL (표준 템플릿 라이브러리)로 정의되어 있는 자료구조 = 컨테이너. 이 컨테이너 안의 원소들을 순회하는 것 iterator

예를 들어, 벡터에서는

vector<int>::iterator it;
for(it=v.begin();it!=v.end();it++){
	cout<<*it<<endl;
}

it는 각 원소의 주소를 가리키게 되기 때문에, *를 붙여야함

2. 해싱

• 해싱은 데이터가 들어온 순서와 상관없이 삽입, 삭제, 검색이 자주 발생하는 경우에 사용하기 좋음
• 해시 충돌을 해결할 수 있는 가장 간단한 방법 : 연결리스트 사용하기
• 일반적인 경우의 시간 복잡도 : O(1)
• 최악의 경우 (예를 들어 충돌) : O(n)

프로그래머스 문제 ) 완주하지 못한 선수 (python)
자바에서는 getorDefault를 사용해서 풀었었는데,
이와 비슷하게 풀 수 있는 방법이 없나 검색을 해보았다.

dictionary의 get()을 쓰면 되는 것 같았다.
get(x)를 하면 x라는 키에 대응되는 value를 돌려준다.
get(x,y)를 하게 되면, x라는 키가 존재하지 않을 경우, y라는 디폴트 값을 대신 가져오게 하는 것이다.

def solution(participant, completion):
	answer=''
    dic={}
    
    for p in participant:
    	dic[p]=dic.get(p,0)+1
    for c in completion:
    	dic[c]=dic.get(c,0)-1
    
    for par,com in dic.items():
    	if com!=0:
        	return par
            
완주하면 값이 0이 될테니까, 0이 아닌 값들은 다 미완주

프로그래머스 문제 ) 전화번호 목록 (python)

def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            answer=False
    return answer

3. 거품정렬

가장 단순한 정렬 알고리즘. 첫번째와 두번째 비교, 두번째와 세번째 비교 ... 이런 식으로 양옆의 것을 비교해서 자리를 바꿔나가는 것. 비효율적이다.

n=int(input())
arr=list(map(int,input().split()))

def bubble_sort():
    isSorted=False
    while not isSorted:
        isSorted=True
        for i in range(n-1):
            if arr[i]>arr[i+1]:
                arr[i],arr[i+1]=arr[i+1],arr[i]
                isSorted=False


bubble_sort()

for elem in arr:
    print(elem,end=" ")