본문 바로가기

inflearn/Do it! 알고리즘 코딩테스트 with C++6

섹션2. 정렬(Sorting). 버블정렬(Bubble Sort) º 다른 정렬 알고리즘에 비해 정렬 시간은 오래 걸리지만 로직이 단순하다 º 버블정렬이란? -> 데이터의 인접요소끼리 비교하고, swap연산을 수행하며 정렬하는 방식 º 핵심 이론 -> 두 인접한 데이터의 크기를 비교해 정렬하는 방식입니다. 시간 복잡도는 o(n^2) º 수행방식 -> 인접한 두개의 값을 비교하고 큰 값을 오른쪽, 작은 값을 왼쪽으로 바꿔줌 -> 두번째 루프에선 정렬된 영역을 제외한 나머지 영역을 정렬해준다 º 시간복잡도(O(n^2) -> 루프 한번을 도는데 모든 데이터를 거쳐서 접근해서 끝까지 가야함. 또한 루프를 도는 횟수만큼 정렬이 됨. -> 루프 한번을 도는데 n의 시간복잡도를 가짐 º 즉, n개의 데이터를 정렬시키려면 n번의 루프가 필요함 -> O(n^2) º 만.. 2023. 10. 1.
섹션1. 자료구조(Data Structure). 스택과 큐 º 삽입과 삭제연산이 후입선출(나중에 들어온 데이터가 먼저 나가는 구조)로 이뤄지는 자료 구조 º top위치에서만 데이터 삽입, 삭제가 가능하다 º 위치 용어 -> top : 삽입과 삭제가 일어나는 위치 º 연산 용어 -> push : top위치에 새로운 데이터를 삽입하는 연산 -> pop : top위치에현재 있는 데이터를 삭제하고 확인하는 연산 -> top : top 위치에 현재 있는 데이터를 단순 확인하는 연산 º 스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩테스트에 효과적, 후입선출은 재귀 함수 알고리즘 원리와 일맥상통 Q1. Stack과 재귀함수가 왜 LastInFirstOut로 같을까? -> Stack은 데이터 삽입과 삭제가 top에서만 일어남 Q2. 재귀함수는 왜 LIFO.. 2023. 10. 1.
섹션1. 자료구조(Data Structure). [투 포인터 실전 문제] 좋은 수 구하기(백준 1253) 1. 예제 출력에서 나온 8이 어떻게 나온건지 분석해보기 -> 1,2 는 표현이 안됨. -> 3은 1과 2의 합 -> 4는 1과 3의 합 -> 5,6,7,8,9,10 모두 다른 두 수의 합으로 표현이 가능함. -> 그러므로 총 8개.(3,4,5,6,7,8,9,10) --> 하지만 예제입력은 정렬되어있고 양의 정수이지만, 입력할때는 정렬되지 않을 수도 있고, 음의 정수가 나올 수 있음. 2. 문제 분석하기 그럼 질문! -> 이 문제를 보고, 어떻게 '투 포인터 정렬'이란걸 알지? A. 사실 여러가지 종류의 문제를 풀어봐야 한다. 하지만 공부를 계속 하다보면 코딩테스트에 나오는 타입은 대개 정해져있다. 이런 문제는 이런 알고리즘은 쓰는구나 라고 정해지는 순간이 오게 된다. 예제 입력을 봤을 때, 일렬로 데이.. 2023. 9. 30.
섹션1. 자료구조(Data Structure). 구간 합 º 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 예시1) 배열 인덱스 4부터 10까지의 합 (S[4] = A[0]~A[4] ) º S[i] = S[i-1] + A[i] ( S[i-1] = S[0] + S[1]+ ... + S[i-1] ) 예시) º S[j] - s[i-1] 예시) Q.왜 S[j] - S[i-1] 공식을 사용하는걸까? A. 1. A배열의 인덱스 2부터 5까지의 합을 구하려고 한다. 공식대로 하면 S[5] - S[1]을 해준다. 왜? 2. S[5]는 A[0]부터 A[5]까지의 합이 담겨있다. 3. S[1]은 A[0[부터 A[1]까지의 합이 담겨있다. 4. S[5]에서 S[1]을 뺴주게 되면 보라색으로 동그라미 .. 2023. 9. 30.
섹션1. 자료구조(Data Structure). 배열과 리스트 그리고 *벡터 º 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 º 인덱스를 통해 참조하며, 선언한 자료형의 값만 저장 º 새로운 값을 추가하거나 특정 인덱스 값을 삭제하려면 해당 인덱스 주변에 있는 값을 이동시켜야 하기에 어려움이 있다. º 배열의 크기는 한번 선언하면 크기를 늘리거나 줄일 수 없다 º 구조가 간단해 코딩테스트에 많이 사용된다. º 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 (노드는 값과 포인트를 갖는 기초 단위) º 인덱스가 없어 값에 접근하려면 head 포인트부터 순서대로 접근해야한다 (접근 속도가 느리다) º 포인터로 연결되어 있어 데이터 삽입, 삭제가 빠르다 º 선언할때 크기를 별도로 지정하지 않아도 된다. º 즉, 리스트의 크기가 정해져 있지 않아 크기.. 2023. 9. 28.
섹션0. 코딩테스트 준비하기 안녕하세요 슐리반입니다. 강의 들은 내용 정리하겠습니다. 1. 시간복잡도 핵심 1) 시간복잡도 시간복잡도 : 연산 함수 (1억번 연산이 1초) -> c++이 제일 빠르다 º 빅 오메가 : best case º 빅세타 : 평균 º 빅오 : worst case 코딩테스트에서는 빅오를 기준으로 수행시간을 계산하는게 좋다. 1. 알고리즘 선택 기준으로 사용하기 º 버블정렬 시간복잡도 : n^2 º 병합정렬 시간복잡도 : nlogn 예시) 코딩테스트 문제 -> 시간 제한 : 2초 º 여기서 도출할 수 있는 점! º c++의 경우 1초에 1억번 연산을 함, 2초가 제한이라면 2억번 이하의 연산을 수행하는 알고리즘을 짜야함. 따라서, 문제에서 주어진 시간제한과 데이터.. 2023. 9. 28.

티스토리툴바