CS+PS/Algorithm14 [알고리즘] 다이나믹 프로그래밍(DP) 중복되는 연산을 줄이자 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 잇는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. ➡️ 연산 속도가 메모리 공간을 최대한으로 활용할 수 있는 효율적 알고리즘 작성의 필요성 ⬆️ 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 이는 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치.. 2023. 11. 28. [알고리즘] 이진탐색 (범위가 큰 수라면.. 이진탐색이다!) 순차 탐색 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 순차 탐색은 이름처럼 순차로 데이터를 탐색한다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자령에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. #순차탐색 def sequential_search(n, target, array): #각 원소를 하나씩 확인하며 for i in range(n): if array[i] == target: return i+1 #현재 위치 반환(인덱스는 0부터 시작하므로 1 더하기) .. 2023. 11. 14. [파이썬]빠른 입출력 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 주로 사용한다. 그런데 이렇게 입력 데이터의 개수가 많은 문제에 input() 함수를 이용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. 이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다. import sys #하나의 문자열 데이터 입력 받기 input_data = sys.stdin.readline().rstrip() #입력받은 문자열 그대로 출력 print(input_data) sys 라이브러리를 사용할 때는 한줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다. 소스코드에 readline()으로 입력하면.. 2023. 11. 13. [알고리즘] 정렬 (선택, 삽입, 퀵정렬..) 정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.(ex. 오름차순, 내림차순) 정렬 알고리즘으로 데이터를 정렬하면 다음장에서 배울 이진탐색(binary search)가 가능해진다. 정렬 알고리즘은 이진탐색의 전처리 과정이라고도 볼 수 있다. 코딩테스트를 대비하기 위해선 크게 5가지 정렬 방법에 대해서 알고 있으면 좋다! 선택정렬 / 삽입정렬 / 퀵정렬 / 계수정렬 / 파이썬 기본 라이브러리 정렬 정렬 알고리즘은 알고리즘 전공 시간때 배운바 있는데, 그때는 c++ 위주로 알고리즘 의사코드를 통해 공부를 했었다.(중간고사 대비를 위해 pseudocode 전체를 외웠던 악몽이...) 그 기억을 떠올려보면서 python에서의 코드 구현에는 어떤 이점이 있는지 알아보고 싶은 .. 2023. 11. 13. [알고리즘] BFS/DFS (feat. stack, queue) 꼭 필요한 자료구조 기초 BFS/DFS를 들어가기에 앞서, 데이터를 표현하고 관리하기 위한 구조에 대해서 간단히 얘기해보고 넘어가자. Stack 박스 쌓기에 비유할 수 있다 선입후출, 후입선출 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하기 동작한다. Queue 대기줄에 비유할 수 있다. 선입선출 구조 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 큐와 같은 경우 push_bac.. 2023. 10. 11. [C++] 연결리스트 (feat.바킹독) 연결 리스트의 정의 연결 리스트란, 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 연결 리스트의 성질 k 번째 원소를 확인/변경하기 위해 O(k)가 필요 (배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문) 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) ⭐️ 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 단일 연결 리스트: 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트 이중 연결 리스트: 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘다 들고 있다. 단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데, 이중 연결 리스트에서는 .. 2023. 9. 19. 이전 1 2 3 다음
