AIHorizons

선형 탐색 (Linear Search) 순차 검색이라고도 부르며 데이터가 모인 집합의 처음부터 끝까지 하나하나 비교하며 원하는 값을 찾아내는 알고리즘. 데이터 배열이 정렬되어 있지 않아도 가능하고, 난이도가 쉽지만, 데이터의 양이 많아질수록 소요되는 시간이 많아진다. 브루트-포스처럼 모든 케이스를 결국 보는 것과 같다고 생각..? 시간 복잡도는 데이터의 길이 n의 O(n) 이다. def linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i return -1 이진 탐색 (Binary Search) 이분 탐색이라고도 부르며, 반으로 나누어 연산하기 때문에 다음과 같은 이름이 붙었다. 이진 검색은 중간값부터 탐색을 시작하기에 중간값..

사용하는 경우 1차원 배열이 있을 경우 리스트에 순차적으로 접근해야 할 때 두 지점을 설정해 해결하는 것. 예를 들어 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 경우 모든 케이스를 조사하는 경우 시간 복잡도는 O(N^2)이 된다. 하지만 투 포인터를 사용하는 경우 end 포인터가 배열의 끝까지 도달하면 종료되기 때문에 복잡도는 O(N)이다. (시간 복잡도 빅-오 표기법에서는 상수항을 무시하기 때문에 O(2N)같은건 없다!) 과정 위의 케이스에서 M = 5라고 가정하고 배열의 구간 합이 5가 되는 지점을 찾는다고 하자 현재 start = 0 end = 0이며, 합 S = 두 포인터가 같기 때문에 0. end가 뒤로 움직일 때는 새로 포함한 원소를 S에 더하..

오랜만의 문제 풀이 포스팅. 저번에 프로그래머스 lv1을 모두 정복한 이후 lv1 문제들이 약 13개정도 추가되었었는데, 이것도 다 풀고.. 네이버 부스트캠프 1차를 준비하면서 백준,프로그래머스 하위 레벨 문제들을 양치기로 계속 풀다보니 포스팅보다는 빠르게 계속 푸느라 포스팅을 안했었다. 덕분에 1차를 붙었고, 2차 시험을 준비하면서 LV2 문제를 풀고있었다. 근데 이 문제는 포스팅 안해두면 나중에 내 코드를 절대 이해할 수가 없을 것 같아서 포스팅.. 일단 문제가 좀 길다. 카카오 기출같은 느낌.. def solution(n, words): times = [x % n for x in range(len(words))] wrong = "" ans = [] for i in range(len(words)): ..

백준 실4 문제 10828, 스택을 풀다가 깨달은 점들 정리. N = int(input()) stack = [] for _ in range(N): order = input() try: if "push" in order: stack.append(int(order[5:])) elif order == "top": print(stack[-1]) elif order == "size": print(len(stack)) elif order == "pop": print(stack.pop()) elif order == "empty": if len(stack) == 0: print(1) else: print(0) except: print(-1) 1. input()을 솔직히 많은 사람들이 백준에 제출한 결과를 보면 쓰고 있..

문제 설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요. 제한 사항 n은 1,000,000 이하의 자연수 입니다. 입출력 예 nresult 78 83 15 23 입출력 예 설명 입출력 예#1 문제 예시와 같습니다. 입출력 예#2 15(1111)의 다음 큰 숫자는..

처음 프로그래머스 사이트를 알고 1단계 가장 맨 위의 문제였다. 보자마자 빤스런 박았다. 그리고 1단계를 이 문제를 제외하고 모두 풀었다... 부딪혀야지 어쩌겠는가? 그리고 keypad = [[1,2,3],[4,5,6],[7,8,9],['*',0,'#']] def get_index(n): for idx1, i in enumerate(keypad): for idx2, j in enumerate(i): if j == n: return [idx1, idx2] return None def solution(numbers, hand): left = ['*'] right = ['#'] ans = [] for finger in numbers: if finger in [1,4,7]: left.append(finger) ..

풀면서 무언가 깨우쳤거나 혹은 엄청난 고생 끝에 결국 해결 방안을 찾아서 푼 뿌듯한 문제 저장하기. 훗날 코드 다시 읽으면서 이해 못할까봐 말로도 풀어놓는게 좋다고 생각이 됌. 구글링해서 답 보고 푼 문제는 수록 절대 X! 애초에 풀 때 최대한 그러지 않기

전에 한번 오지게 도전했다가 실패했던 문제. 하지만 오늘 문득 오? 싶은 해결 방안이 떠올랐고 그 방법으로 풀이 성공 def solution(answers): ans = [0] * 4 a = [1,2,3,4,5] b = [2,1,2,3,2,4,2,5] c = [3,3,1,1,2,2,4,4,5,5] first = a * (len(answers)//5) + a[:(len(answers)%5)] second = b * (len(answers)//8) + b[:(len(answers)%8)] third = c * (len(answers)//10) + c[:(len(answers)%10)] correct1 = [x-y for x,y in zip(first,answers)] correct2 = [x-y for x,..