1. 개요 오늘도 어김없이 알고리즘 문제를 풀이하였다. 딕셔너리를 이용해 동명이인을 찾는 문제와 큐를 이용해 모든 친구를 찾고 친밀도를 계산하는 문제를 풀이하였다. 오늘부로 엘카데미 챌린지가 종료되었다. 3주간 알차게 학습한 것 같다. 앞으로도 포스팅은 계속 이어나갈 것이다. 2. 문제 1) 딕셔너리를 이용해 동명이인을 찾는 알고리즘 n명의 사람 이름 중에 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 생각해 보자. 리스트 s를 매개 변수로 받아 딕셔너리에서 등장 횟수가 2 이상인 것들 결과에 추가하여 집합 result에 저장해 반환하는 함수 find_same_name을 작성하라. 풀이 1. 각 이름이 등장하는 횟수를 저장할 빈 딕셔너리(name_dict) 생성 2. 입력으로 주어진 리스트에서 각..
1. 개요 오늘은 이분 탐색 알고리즘과 회문 찾기 알고리즘을 풀이하였다. 회문(Palindrome)은 앞으로 읽으나 뒤로 읽으나 동일한 단어, 구절, 문장 등을 말한다. 예를 들면 한글로는 토마토, 기러기, 영어로는 madam, wow 등이 있겠다. 점점 생각할거리가 많아지는 문제들이 빈번하게 나타나고 있다. 또 알고리즘을 풀이하는데 사용된 자료구조의 개념을 간단하게 정리하였다. 2. 문제 1) 이분 탐색 알고리즘 리스트 a와 비교값인 변수 x를 받아 리스트 a의 원소와 x와 같다면 x를 반환하고 아닐 경우 -1를 반환하는 함수 binary_search를 작성하세요. 풀이 1. 중간 위치를 찾는다. 2. 찾는 값과 중간 위치 값을 비교 3. 같다면 원하는 값을 찾은 것이므로 위치 번호를 결괏값으로 반환 ..
1. 개요 오늘은 병합 정렬 알고리즘과 퀵 정렬 알고리즘 문제를 풀이하였다. 알고리즘을 이제 막 입문하다보니 생각보다 시간이 꽤 걸린 것 같다. 알면 알수록 고려해야할 부분이 굉장히 많은 것 같다. 2. 문제 1) 쉽게 설명한 병합 정렬 알고리즘 리스트 a를 매개 변수로 받아 병합 정렬을 하여 리스트 result에 저장해 반환하는 함수 merge_sort를 작성하세요. 풀이 병합 정렬을 사용하여 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 알고리즘을 생각해 보면, 1. 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없다. 2. 전체 리스트를 절반으로 나눠 각각 재귀 호출을 통해 병합 정렬을 한다. 3. 두 그룹의 첫 번째 값을 비교하여 작은 값을 빼내 결과 리스트에 넣는 과정을 반..
1. 개요 오늘은 어제 쉽게 설명한 선택 정렬 알고리즘을 더 효율적으로 구현하는 방법에 대해 고민해보았고, 삽입 정렬 알고리즘 문제를 풀이하였다. 2. 문제 1) 일반적인 선택 정렬 알고리즘 어제 쉽게 구현한 선택 정렬 알고리즘을 효율적으로 구현할 수 있는 일반적인 알고리즘을 구현해 보자. 리스트 a를 매개 변수로 받아 자료 값중 가장 최솟값을 차례대로 정렬해주는 함수 sel_sort를 작성하라. 풀이 일반적인 선택 정렬 알고리즘은 입력으로 주어진 리스트 a안에서 직접 자료의 위치를 정렬시키는 알고리즘이다. 처리할 대상 범위에서 최솟값을 찾아 그 값과 범위의 맨 앞에 있는 값을 서로 바꾸는 과정을 반복한다. 이 과정이 한 번 끝날 때마다 범위 안의 맨 앞에 있는 값은 정렬이 끝난 것이므로 정렬 대상 범위..
1. 개요 오늘은 정렬 알고리즘을 풀이하였다. 2. 문제 1) 순차 탐색 알고리즘 순차 탐색 알고리즘을 활용하여 리스트 a와 비교값인 변수 x를 받아 리스트 a의 원소와 x와 같다면 x를 반환하고 아닐 경우 -1를 반환하는 함수 search_list를 작성하세요. 풀이 def search_list(a, x): for i in range(len(a)): if a[i] == x: return i return -1 # 테스트 예시 v = [17, 92, 18, 33, 58, 7, 33, 42] print(search_list(v, 18)) # 2(순서상 세 번째지만, 위치 번호는 2) print(search_list(v, 33)) # 3(33은 리스트에 두 번 나오지만 처음 나온 위치만 출력) print(se..
1. 서론 오늘은 for문을 통해 구현할 수 있는 알고리즘을 재귀 호출을 이용해 구현해 보았고, 어떤 게 더 효율적인지 생각해보았다. 2. 문제 1) for문을 사용하여 1부터 n까지 곱을 반환하는 알고리즘 for문을 사용하여 변수 n을 입력받아 1부터 n까지의 곱을 반환하는 함수 fact을 작성하세요. 풀이 def fact(n): result = 1 for i in range(1, n + 1): result *= i return result print(fact(1)) print(fact(5)) print(fact(10)) 2) 재귀 호출을 사용하여 1부터 n까지 곱을 반환하는 알고리즘 재귀 호출 알고리즘을 사용하여 변수 n을 입력받아 1부터 n까지의 곱을 반환하는 함수 fact을 작성하세요. 풀이 de..
1. 서론 파이썬 알고리즘 풀이 2일차. 강의는 '모두의 알고리즘 with 파이썬'이다. 챌린지를 진행한지도 2주가 지났다. 오늘도 분발. 2. 문제 동명이인을 찾는 알고리즘 동명이인을 찾는 알고리즘을 만들어 봅시다. 첫 번째 Tom을 뒤에 있는 Jerry, Mike, Tom과 차례로 비교합니다. 첫 번째 Tom과 마지막 Tom이 같으므로 동명이인입니다(동명이인: Tom). 두 번째 Jerry를 뒤에 있는 Mike, Tom과 비교합니다(앞에 있는 Tom과는 이미 비교했음). 세 번째 Mike를 뒤에 있는 Tom과 비교합니다. 마지막 Tom은 비교하지 않아도 됩니다(이미 앞에서 비교했음). 같은 이름은 Tom 하나뿐입니다. 이 알고리즘에서 주의할 점은 다음과 같습니다. 이번에 비교할 이름을 뽑은 다음에는 ..
1. 서론 엘카데미에 [모두의 알고리즘 with 파이썬] 강의를 시작하였다. 파이썬 알고리즘 기초를 예제 형식으로 실습할 수 있는 강의이다. 오늘 푼 알고리즘 문제를 정리하였다. 2. 문제 *1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 변수 n을 입력받아 1부터 n까지 연속한 숫자의 합을 반환하는 함수 sum_n을 작성하라. 풀이 두 가지 방법이 있었다. 첫번째 풀이는 단순 반복 합을 하였고 두번째 풀이는 가우스 덧셈 공식을 이용하였다. # 첫번째 풀이 def sum_n(a): sum = 0 for i in range(1, a + 1): sum = sum + i a = a + 1 return sum result = sum_n(10) print(result) result = sum_n(100) pri..
