awesomeCarrot awesomeCarrot

문자열 알고리즘문자열 알고리즘은 기술 면접에 가장 자주 나오는 알고리즘입니다.문자열 알고리즘에서 가장 많이 나오는 주제로는애너그램 찾기팰린드롬 찾기마지막 숫자시저의 암호등이 있습니다. 이번 블로그에서는 애너그램 찾기와 팬린드롬 찾기 알고리즘에 대해 공부해보겠습니다.애너그램 찾기애너그램이란 숫서와 대소에 관계없이 똑같은 문자로 구성된 두 문자열을 의미합니다. 예를 들어 Car와 arc는 애너그램입니다.  먼저 s1과 s2가 애너그램인지 아닌지를 판별해주는 함수를 작성해보겠습니다.먼저 s1, s2를 인자로 받습니다.s1 ,s2 둘 다 띄어쓰기를 없애고 대문자를 소문자로 바꿉니다.둘 다 정렬을 한 상태로 같은지 비교합니다.두 인자가 같다면 True, 다르다면 False를 리턴합니다.시간 복잡도👉애너그램을 찾..

정렬 알고리즘데이터 정렬이란 데이터를 일정한 순서로 배치하는 것을 말합니다. 정렬 알고리즘에는 다양한 방법이 있으며, 버블 정렬, 삽입 정렬, 병합 정렬 등이 있습니다.  대표적인 정렬 알고리즘으로 세 가지 알고리즘이 있습니다.버블 정렬삽입 정렬병합 정렬삽입 정렬 삽입 정렬은 카드 묶음을 정렬하는 것과 비슷한 알고리즘 입니다. 먼저 카드 묶음에는 정렬된 카드, 정렬되지 않은 카드들이 있습니다. 정렬되어 있지 않은 카드들의 묶음에서 카드를 하나씩 빼서 정렬된 카드 묶음에 올바른 위치에 넣는 알고리즘을 삽입 정렬이라고 합니다.  삽입 정렬 코드를 보겠습니다. 먼저 N과 n_list에 입력받을 리스트의 길이와 리스트의 요소들을 입력받습니다.insertion_sort라는 함수를 선언합니다.먼저 1부터 a_lis..

정렬 알고리즘데이터 정렬이란 데이터를 일정한 순서로 배치하는 것을 말합니다. 정렬 알고리즘에는 다양한 방법이 있으며, 버블 정렬, 삽입 정렬, 병합 정렬 등이 있습니다.  대표적인 정렬 알고리즘으로 세 가지 알고리즘이 있습니다.버블 정렬삽입 정렬병합 정렬 버블 정렬  버블 정렬은 숫자 리스트를 순회하면서 각 숫자를 다음과 비교하며, 순서가 올바르지 않으면 둘의 위치는 바꾸는 알고리즘 입니다.  먼저 버블 정렬 코드를 보겠습니다. 먼저 N 과 n_list에 리스트에 들어갈 원소의 개수, 리스트에 들어갈 숫자들을 입력받습니다.bubble_sort함수 안에서는 이중포문을 사용하여 정렬을 합니다.먼저 n_list의 길이만큼 반복하는 반복문 안에, 0부터 len((n_list)-i-1만큼 반복하는 반복문을 넣습니..

1.먼저 N, n_list, M, 그리고 m_list에 각각의 정수와 리스트를 입력 받습니다. 2. 이중탐색을 사용할 것이므로, n_list를 먼저 정렬시켜줍니다.(.sort()사용)python 함수 - bisect_right & bisect_left그리고 여기서 사용하는 핵심 함수는 바로 bisect_right와 bisect_left입니다. bisect_right와 bisect_left는 파이썬 함수로서 이분탐색을 더 쉽게 만들어줍니다. bisect_left(list, n)n이 list에서 처음 등장하는 인덱스를 반환합니다.bisect_right(list, n)n이 list에서 마지막으로 등장한 다음 위치를 반환합니다.따라서 여기서 특정 숫자가 n_list에서 몇 번 나오는지를 확인하기 위해서는 bis..

먼저 지방의 수를 의미하는 정수 N, N 개의 정수를 a라는 리스트에 그리고 지방 예산을 M이라는 변수에 입력받는다.a 리스트를 정렬하고 모든 요청을 배정할 수 있는 경우와 그렇지 않은 경우로 나눈다. (if 문 사용)만약 배정 가능하다면 max(a)를 사용하여 상한액을 출력한다.만약 그렇지 않다면 포문을 돌려 a리스트에 있는 지방 예산들이 상한액을 넘는지 안 넘는지를 확인한다.상한액을 넘지 않는다면 M에서 그 지방 예산을 빼고 count 값을 올린다.a리스트의 상한액을 넘지 않는 지방 예산들을 모두 빼고나서는(즉 상한액을 넘는 지방 예산들만 모아서) 그 지방 수 만큼 나누어 평균(value)를 낸다면 그 값이 상한액이 될 것이다.

탐색 알고리즘탐색 알고리즘으로 데이터 세트에서 데이터를 검색하는데, 여기서 데이터 세트는 데이터의 모음을 말합니다. 대표적인 탐색 알고리즘으로 두 가지 알고리즘이 있습니다.선형 탐색이진 탐색선형 탐색 선형 탐색은 데이터 세트에 들어있는 모든 데이터를 하나하나 비교하면서 원하는 데이터를 찾는 탐색 방식입니다. 처음부터 끝까지 모든 요소를 검사하는 알고리즘이므로 순차 탐색이라고 부르기도 합니다.  먼저 선형탐색의 예시를 한 번 들어보겠습니다. a_list 라는 리스트가 있고 91이 리스트에 있는지 없는지 확인하는 linear_search 라는 함수를 만들어내야합니다. 위의 linear_search함수를 보자면먼저 인자로 리스트와 n이라는 변수에 하나의 값을 받습니다. 그리고 포문을 이용해서 그 리스트에 있는..

반복 알고리즘반복 알고리즘은 동일한 루프를 반복해 문제를 해결하는 알고리즘 입니다.  반복 알고리즘은 밑의 세가지 법칙을 따릅니다.반드시 종료 조건이 있어야 한다.반드시 자기 자신의 상태를 변경하면서 종료 조건에 가까워져야 한다.반드시 자기 자신을 재귀적으로(다시 돌아와) 호출해야 한다.반복 알고리즘의 예시로는 팩토리얼이 있다. https://www.acmicpc.net/problem/10872위의 코드를 설명해보자면일단 N 이라는 함수에 정수를 입력받는다.factorial이라는 함수를 선언 후, 앞에서 입력받은 정수 N을 인수로 받는다.만약 N의 값이 1보다 크다면 N과 factorial(N-1)의 값을 곱한다.여기서 factorial(N-1)이 다시 호출되고(자기 자신을 재귀적으로 호출), N-1의 ..