반응형 알고리즘19 [알고리즘] 투 포인터 투 포인터 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 특정한 합을 가지는 부분 연속 수열 찾기 시작점(start)와 끝점(end)이 첫 번째 원소의 인덱스(0)를 가르키도록 한다. 현재 부분합이 M과 같다면 카운트한다. 현재 부분합이 M보다 작으면 end를 1 증가시킨다 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문에 투포인터 알고리즘으로 해결 할 수 있다. 만약 리스트 내 원소에 음수데이터가 포함되어있는 경우에는 위 알고리즘으로 해결 할 수 없다. # 특정 합계 값이 5라고 가정 .. 2021. 3. 14. [자료구조] 스택, 큐 (파이썬) 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조 스택 후입 선출 구조 (LIFO) 재귀 함수의 수행 또한 스택 자료구조를 사용한다. 기본 자료 구조 사용 stack [5,3,2,1] stack.appned(3) stack.pop() print(stack) print(stack[::-1]) # 최하단 원소부터 출력 큐 선입 선출 구조 (FIFO) Collections 에서 제공하는 deque 라이브러리 사용 from collections import deque queue = deque() queue.append(5) queue.popleft() queue.reserve() # 순서를 역순으로 바꾸기 (정렬을 의미하지는 않음) x = list(.. 2021. 3. 10. [백준] 암호 만들기 1759 (파이썬) import itertools import sys l, c = map(int,sys.stdin.readline().rstrip().split()) secret = sorted(list(sys.stdin.readline().rstrip().split())) data = ('a', 'e', 'i', 'o', 'u') for x in list(itertools.combinations(secret, l)): count = 0 for i in data: if i in x: count += 1 if count >= 1 and l - count >= 2: # 자음이 2개 이상이란 것을 고려하지 않았었다. print(''.join(x)) # 출력 초과 왜 그러지? 조합 값이 l이 아닌 4를 넣었다. itertools라.. 2021. 3. 8. [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조( or 재귀함수)를 이용한다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 더이상 2번의 과정을 수행할수 없을 때까지 반복합니다. BFS (너비 우선 탐색) 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조를 이용한다. 탐색 시작노드를 큐에 삽입하고 방문처리를 합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다. 더 이상 2번의 과정을 수행할 수 .. 2021. 3. 7. 이전 1 2 다음 반응형
