I about me

이진탐색 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이며, 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음. *** 정렬된 알고리즘 *** 3강. 탐색(Search) _ 이중 탐색(Bi.. : 네이버블로그 (naver.com) 3강. 탐색(Search) _ 이중 탐색(Binary search) ※ 주의 ※ 정렬된 알고리즘으로 이중 탐색을 진행한다. ex) 아래 리스트에서 14를 찾으시오. ... blog.naver.com

너비 우선 탐색(BFS) 시작 노드에서 출발해 시작 노드를 기주능로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 부모가 나가면 자식이 들어와 기능 특징 시간 복잡도(노드 수: V, 에지 수: E) 그래프 완전 탐색 - FIFO 탐색 - Queue 자료구조 이용 O(V + E) 1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 2. 큐에서 노드를 꺼낸 후 꺼내 노드의 인접 노드를 다시 큐에 삽입하기 3. 큐 자료구조에 값이 없을 때까지 반복하기 너비 우선 탐색(BFS) 구현 방법 다음과 같은 반복하면 'A-B-C-D-E-F-G-H-J' 가 된다. 1. (초기화) traversal ← 빈 리스트, q ← 빈 큐 2. 빈 트리가 아니면, root node를 q에 추가(enqueue) 3. q..

깊이 우선 탐색(DFS) 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하는 것 기능 특징 시간 복잡도(노드 수: V, 에지 수: E) 그래프 완전 탐색 - 재귀 함수로 구현 - 스택 자료 구조(FIFO) O(V + E) 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단결선 찾기, 사이클 찾기, 위상 정렬 - 노드 방문 여부를 체크할 배열이 필요!! - 인접 리스트 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 2. 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 3, 스택 자료구조에 값이 없을 때까지 반복하기

동적 계획법의 원리와 구현 방식 1. 큰 문제를 작은 문제로 나눌 수 있어야 한다. 2. 작은 문제들이 반복되어 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다. 3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며, 추후 재사용할 때는 이 DP 테이블을 이용한다. 4. 동적 계획법은 다운 방식과 바텀-업 방식으로 구현할 수 있다. 동적 계획법의 대표 문제 D[n] = D[n-1] + D[n-2] Tip! 1. 아 여기서 여기.. 여기서 여기 ( x ) 6번째를 찾을 거야! 1, 2, 3, 4, 5번째 숫자가 이렇게 있네? 이들의 관계가 어떻길래 저렇게 나온거지? → 그렇게 하고 일반화하기!! 2. 시간 복잡도 주의

[그리디 3단계] ① 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. ② 적절성 검사: 현재 선택한 해가 문제의 제약 조건에 벗어나지 않는지 검사한다. ③ 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다. 해결하지 못하면 ①로 돌아감.

[출처: 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 | 1주차 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현] 1. 문제를 본다. 2. 문제를 해석한다. (1) 최대, 최소 범위를 파악합니다. (2) 단순 구현이라면 구현하자. (3) 무식하게 풀 수 있다면 무식하게 풀자 (4) 아니라면 다른 알고리즘을 생각하자 (5) 제출하기 전, 반례를 항상 생각하자 3. 코드를 작성한다. https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net

[출처: 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 | 1주차 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현] 위와 같이 진행할 경우, N이 10만이라는 숫자가 주어질 때, 10만 * 10만 = 100억의 시간복잡도가 생긴다. 이것은 불가능할 확률이 높다는 뜻이니 다른 방법을 써야한다! 함께 누적합을 알아보자. 다음과 같이 1번 박스, 2번 박스, 3번 박스 이렇게 만들어 놓고, 원하는 값이 있을 때 만들어놓은 박스들을 이용해서 구하는 방법이다! 근데 또 1번 박스 따로, 2번 박스 따로, 이렇게 만드는 것은 쉽지 않다. 그러므로 이전에 만들어놓은 값에 그 해당 요소만 더해가는 방식으로 만들어준다. psum[1] psum[2] = psum[1] + a[2] psum[3] = psum[2] ..

파이썬의 스택(LIFO) 연산(리스트 이름이 s일 때) s.append(data): top 위치에 새로운 데이터를 삽입하는 연산 s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산 ex) 길이 우선 탐색(DFS), 백트래킹 파이썬의 큐(FIFO) 연산(리스트 이름이 s일 때) s.append(data): rear 위치에 새로운 데이터를 삽입하는 연산 s.popleft(): front 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 s[0]: front 위치에 현재 있는 데이터를 단순 확인하는 연산 ex) 너비 우선 탐색(BFS)

배열과 리스트는 정보를 담을 수 있는 기본적인 자료구조이다. 파이썬에서는 리스트가 배열의 특성도 함께 내포하고 있어 크게 구분하지는 않지만, 두 개의 특징과 동작원리를 아는 것은 매우 중요하다고 한다. 그럼 무엇이 비슷하고 무엇이 다른 건지 함께 살펴보도록 하자! 배열 리스트 정의 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 (값+포인터를 묶은 노드)를 포인터로 연결한 자료구조 장점 인덱스를 사용하여 값에 바로 접근 가능 크기를 변하시키기 쉬움 단점 한 번 선언하면 크기를 늘리거나 줄일 수 없음. 값에 접근하는 속도가 느림 그러나 파이썬에서는 리스트가 배열의 장점도 가져왔다는 것을 깨닫고, 앞으로 거의 모든 문제에서 리스트를 사용하면 된다는 것을 잊지 말자..!! https://www.acmi..

코드의 논리 오류를 어떻게 잡을까? ① 문법적인 오류는 "컴파일러"를 통해 충분히 잡아낼 수 있음. ② 논리적인 오류는 "디버깅"을 통해서 잡아내야함... 요 녀석이 골칫거리ㅋㅋ 디버깅이 왜 중요할까? 우리가 코테 문제를 풀다보면 index나 예외처리 등 실수를 많이 낸다...! 즉, 코드는 돌아가지만 요구한 조건에 맞지 않아 '틀렸습니다!' 하는 사태가 일어나는 것이다... 그렇기에 디버깅이 실수를 줄여줄 수 있다고 한다! 오류 ① 초기화가 안 되어 있음. 오류 ② 인덱스 범위 지정이 잘못되어있음. 오류 ③ 잘못된 변수 사용 오류 ④ 파이썬 자동 형 변환 요즘 프로그래머스를 풀 때 75.8%, 81.0% 정답률 이런 식으로 나올 때마다 매우 화가 난다...! 다른 거는 맞았다는데... 왜 너의 케이스만..