알고리즘 코드 카타
itertools 에서 combination 이용해 봄
완전 탐색 brute-force - 2차원 배열
완전 탐색 복습 : 가능한 경우의 수를 일일히 나열하면서 찾는 방식
※ 2차원 배열
map(), split() 등을 이용함.
map(함수, 리스트)
--> 함수를 돌아가면서 리스트에 적용한다.
문자열.split('구분자')
--> 구분자를 기준으로 문자열을 나누어 줌※ 백준 문제 풀이 관련 입력 받기
따라서 백준에서 예제 입력을 할 때 문자열로 받아 재구성 해주어야 함
input()으로 받아서
input().split() 으로 나누어 리스트화.
map(int, input().split()) 해서 문자열의 리스트를 int화
list(map(int, input().split())) 해서 int화한 것을 리스트화
OR map(int, input().split()) = n1, n2, ..., nm 해서 각 nm 에 int를 넣어줌⇒ 적용한 예시
#이진 탐색 Binary Search
선형 탐색 linear search 할 경우 시간이 지나치게 오래 걸림. 시간복잡도: O(n)
따라서 이진 탐색을 통해서 반씩 나누어 탐색하면서 시간을 줄임 시간복잡도: O(logn)
이를 그래프로 나타내면👇👇
좋은 예로 UP&DOWN 게임에서 50의 결과가 UP/DOWN 인지에 따라 나머지 반은 탐색하지 않아도 됨.
이진 탐색에서 중요한 부분은 정렬이 되어있어야 한다는 점.
리스트.sort()
sorted(리스트)
를 통해서 정렬을 할 수 있다.
sort() 함수의 경우 None을 리턴하기 때문에 사용하려면
list.sort()
print(list)
sorted() 함수의 경우 정렬된 리스트를 리턴하기 때문에
result = sorted(list)
print(list)
추가적으로 key parameter 를 사용하여 정렬하는 방법
두 번째 문자로 정렬하는 방법
def sort_key_func(item):
return item[1]
>> 예: list = ["1b", "2c", "3a"] 에서 두 번째 문자를 기준으로(a,b,c) 정렬
1. sort() 를 사용하는 경우
list.sort(key=sort_key_func)
2.sorted() 를 사용하는 경우
result = sorted(list, key=sort_key_funct)이외에도 lambda 를 사용할 수 있고 (권장하지 않음), itemgetter 라이브러리를 사용 가능함.
알고리즘 백준 문제 풀이 (스쿼드 공부방)
Today I Thought
코드 카타는 풀만 한데.. 더 나은 방법이 없을까? 하는 생각이 든다. 그런데 그걸 생각해 볼 시간이 없다는 것이 아쉬움...
2차원 배열 입력부터 막혀서 백준 문제는 최댓값 일부만 풀 수 있었고 그것마저도 선형 탐색에 가까운 방법으로 풀었다. 각 알고리즘에서 주로 쓸 수 있는 풀이 방법을 정리해두어야겠다. 그리고 2차원 배열에 대해서 좀 더 익숙해져야 할 듯.
튜터님께서 설명을 잘 해주셔서 이해도 잘 됐고, map 함수 등 잘 모르던 함수들도 파악할 수 있었는데 문제에 적용하기가 너무 어렵다. 풀어나갈 수 있는 방법을 적극적으로 찾아야겠다.
발전 중...