1. 회문 찾기

• 회문 : 순서대로 읽어도, 거꾸로 읽어도 그 내용이 같은 단어나 문장

1) 회문 찾기 알고리즘

• 큐, 스택 이용 : 큐에서 꺼낸 문자와 스택에서 꺼낸 문자들이 모두 같다면 그 문장은 회문임.

def palindrome(s):
    st = []
    qu = []

    for x in s:
        if x.isalpha():
            qu.append(x.lower())
            st.append(x.lower())

    while qu:
        if qu.pop(0) != st.pop():
            return False
    return True

print(palindrome("Madam, I’m Adam."))

• if qu.pop(0) != st.pop(): : 큐와 스택에서 꺼낸 문자 비교

2) 큐와 스택 미이용한 회문 찾기 알고리즘

def palin(s):
    i = 0
    j = len(s) - 1
    
    while i < j:
        if s[i].isalpha() == False:
            i += 1
        elif s[j].isalpha() == False:
            j -= 1
        elif s[i].lower() != s[j].lower():
            return False
        else:
            i += 1
            j -= 1
    return True

• while i < j: : 알파벳 중간까지만 검사
• if s[i].isalpha() == False: i+=1 : i 위치의 문자가 알파벳이 아닌 경우 한 칸 넘어감
• elif s[i].lower() != s[j].lower():: 두 위치에 알파벳이 있으면 비교 후 다를 경우 False
• else: i += 1; j -= 1; : 두 위치의 알파벳이 같은 경우 다음 알파벳 탐색

2. 동명이인 찾기 : 딕셔너리

• 딕셔너리 : 정보를 찾는 기준이 되는 key, 그 키에 연결된 값 value의 대응관계를 저장하는 자료구조

1) 딕셔너리

d = {"Justin": 13, "John": 10, "Mike": 9}
d["Justin"] #13
# 키값을 이용하여 값 찾기

d = {} # 빈 딕셔너리 생성
d = dict()

 d["Summer"] = 1 # 새 값 추가
 d["Summer"] = 2 # 키는 중복되지 않음. 새로 덮어씀
 
 s_info = {
    1: "김민준",
    2: "이유진",
    3: "박승규"
}

del s_info[3] # 삭제

"Summer" in d   # True

s = {1, 2, 3} #집합
d = {1:2, 3:4} #딕셔너리

• len(a) : 딕셔너리 개수
• d[key] : 딕셔너리에서 키에 해당하는 값을 읽음
• d[key]=value: 키에 값 저장. 없으면 새로 만들고 있으면 덮어씀
• del d[key] : 키에 해당하는 값 삭제
• key in d : 키가 딕셔너리 안에 있는지 확인

2) 동명이인 찾기 알고리즘

딕셔너리 =
{
    "이름 1": 이름 1이 등장한 횟수,
    "이름 2": 이름 2가 등장한 횟수,
    "이름 3": 이름 3이 등장한 횟수
}

def find_name(a):
    name_dict = {}
    for name in a:
        if name in name_dict:
            name_dict[name] += 1
        else:
            name_dict[name] = 1
        
    result = set()

    for name in name_dict:
        if name_dict[name] >= 2:
            result.add(name)
    
    return result

name2 = ["Tom", "Jerry", "Mike", "Tom", "Mike"]
print(find_name(name2))

• if name in name_dict: name_dict[name] += 1 : 이름이 name_dict에 있다면 해당 name(key)의 value값 1개 추가
• else: name_dict[name] = 1 : 아닌 경우 처음 등장이므로 해당 name값의 value는 1로 설정함.

계산복잡도 : O(n)

• for문 중복 없이 2번 돌기 때문

def find_some(d, x):
    if x in d:
        return d[x]

    return -1

• 키값을 통해 value값을 찾는 알고리즘

3. 친구의 친구 찾기 알고리즘 : 그래프

1) 파이썬으로 그래프 표현하기

fr_info = {
    'Summer': ['John', 'Justin', 'Mike'],
    'John': ['Summer', 'Justin'],
    'Justin': ['John', 'Summer', 'Mike', 'May'],
    'Mike': ['Summer', 'Justin'],
    'May': ['Justin', 'Kim'],
    'Kim': ['May'],
    'Tom': ['Jerry'],
    'Jerry': ['Tom']
}

• 각 키에 대한 값을 리스트로 받아서 키로 들어오는 선들 표현

2) 알고리즘 원리

1) 앞으로 처리할 사람을 저장하는 큐 생성
2) 이미 큐에 추가한 사람을 저장하는 집합 생성
3) 검색에 출발점이 될 사람을 큐와 집합에 저장
4) 큐에 사람이 남아있다면 큐에서 처리할 사람을 꺼냄
5) 꺼낸 사람 출력
6) 꺼낸 사람의 친구들 중 아직 큐에 추가된 적 없는 사람이라면 큐와 집합에 저장
7) 큐에 처리할 사람이 남아있다면 4번부터 반복 수행

3) 친구 찾기 알고리즘

def print_all_friend(g, start):
    qu = []
    done = set()

    qu.append(start)
    done.add(start)

    while qu:
        p = qu.pop(0)
        print(p)
        for x in g[p]:
            if x not in done:
                qu.append(x)
                done.add(x)

fr_info = {
    'Summer': ['John', 'Justin', 'Mike'],
    'John': ['Summer', 'Justin'],
    'Justin': ['John', 'Summer', 'Mike', 'May'],
    'Mike': ['Summer', 'Justin'],
    'May': ['Justin', 'Kim'],
    'Kim': ['May'],
    'Tom': ['Jerry'],
    'Jerry': ['Tom']
}

print_all_friend(fr_info, 'Summer')
print()
print_all_friend(fr_info, 'Jerry')

4) 친밀도 계산 알고리즘

• 어떤 사람들을 큐에 넣을때마다 친밀도 +1

튜플 : 순서쌍 (x, y)로 표현

t = (3, 7)
t[0] #3
t[1] #7
(x, y) = t #튜플의 값을 각각 변수 x, y에 저장
x #3
y #7

def print_all_friends(g, start):
    qu = []
    done = set()

    qu.append((start, 0))
    done.add(start)

    while qu:
        (p, d) = qu.pop(0)
        print(p, d)
        for x in g[p]:
            if x not in done:
                qu.append((x, d+1))
                done.add(x)

5) 그래프 탐색 : 너비우선탐색(BFS)

def bfs(g, start):
    q = []
    d = set()

    q.append(start)
    d.add(start)
    while q:
        p = q.pop(0)
        print(p)
        for p in g[p]:
            if p not in d:
                q.append(p)
                d.add(p)


g = {
    1 : [2, 3],
    2 : [1, 4, 5],
    3 : [1],
    4 : [2],
    5 : [2]
}

print(bfs(g, 1))