📊 Algorithm/Algorithm 주제별 정리45 🧚♂️알고리즘🧚♂️ - 자료구조 - 투 포인터 / 슬라이딩 윈도우 투 포인터 - 2개의 포인터 / 시간 복잡도 최적화 1번 백준 2018번 실버 5 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net - 결과값에 1 미리 넣기 (자기자신의 수) - 시작 포인터 / 끝 포인터 ( 값이 목표보다 작거나 같으면 끝포인터++ / 값이 목표보다 크면 시작포인터++) from sys import stdin N = int(stdin.readline()) sum = 1 # 현재 합 count = 1 # 자기 자신이 포함된 결과값 startPoint = 1 endPoint.. 2022. 12. 25. 🧚♂️알고리즘🧚♂️ - 자료구조 - 스택.큐.덱 ⭐️ 스택 / 큐 / 덱⭐️ 자료구조의 일종 스택 - 후입선출(LIFO, Last-In-First-Out) 구조 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다 위치 top : 삽입(push)과 삭제(pop)가 일어나는 위치 연산 list.append(data) : top에 새로운 데이터를 삽입하는 연산이다. list.pop(): top 위치의 데이터 삭제/확인\ list[-1] : top 위치의 데이터를 확인 - 깊이 우선 탐색 알고리즘 - 백트래킹 분야 (역순출력 등) 큐 - 선입선출(FIFO, First in first out) 구조 가장 먼저 삽입된 자료가 가장 먼저 삭제된다 +(deque이용) 위치 rear : 가장 끝 데이터(마지막에 넣은 데이터) front : 가장 앞의 데이터 연산 list.. 2022. 11. 16. 🧚♂️알고리즘🧚♂️ - 그리디 - 그리디 ⭐️탐욕 알고리즘(Greedy Algorithm)⭐️ 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 여러 경우 중 하나를 선택해야 할 때마다 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달 (그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없음 -하지만 대체로 그리디 문제들은 최적이 됨) 그리디 알고리즘 수행 방법 1) 해 선택 (현재 상황에서의 최선해 선택) 2) 적절성 검사 ( 현재 선택된 해가 문제의 제약 조건에 맞는지 검사) 3) 해 검사 ( 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사/아니라면 1로) 1 - 백준 11047번 - 실버3 11047번: 동전 0 첫.. 2022. 11. 7. 🧚♂️알고리즘🧚♂️ - 자료구조 - 배열/리스트/구간합 doit 코딩테스트 알고리즘-파이썬 배열 리스트 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 노드(값+포인터)를 포인터로 연결한 자료구조 인덱스 사용/값에 바로 접근 값 접근 속도가 느리다 삽입,삭제가 어려움 삽입 삭제 쉬움 선언 후 크기 조정 불가 크기가 정해져 있지 않음 구조가 간단 비교적 구조 복잠 파이썬에서는 배열/리스트 구분이 없음(하나로 합쳐짐) 1번 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net - bool형 숫자 변환을 유용하게 사용해 보자 2번 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 .. 2022. 9. 27. 🧚♂️알고리즘 공부🧚♂️ 요즘 문제 풀이에 한계를 느껴서 시간복잡도/풀이 방법 등 알고리즘에 대해 공부해봐야겠다는 생각이 들었다. 그래서 doit 알고리즘 코딩테스트 책을 샀다 내 버려진 doit 안드로이드랑 doit 깃/깃허브와 달리 끝까지 가보겠다! 안드로이드는 언젠간 할 거다! 깃/깃허브는 안할것같다.. 반 정도 하다가 큰 이득이 없는 것 같아서 탈주 파이썬은 끝냈다~ 시간복잡도 시간복잡도 : 주어진 문제를 해결하기 위한 연산 횟수 유형 Big-O (O(n))- 최악의 경우 Big-세타(θ(n)) - 보통의 경우 Big-Omega(Ω(n)) - 최적의 경우 최악의 경우를 많이 다룸 복잡도 O(1) 2022. 9. 26. 이전 1 2 3 4 5 다음
