전체 글53 알고리즘 - 버블 정렬(Bubble Sort) / 버블 정렬 구현 정렬이란?정렬은 객체들이 나열된 순서를 어떤 논리적인 순서에 맞도록 바꾸는 작업이다. 예를 들면 숫자들의 순서를 오름차순으로 변경하거나 내림차순으로 바꾸는 등의 일을 할 수 있다. 📌 정렬 알고리즘을 배워야 하는 이유.서로 다른 알고리즘 간의 비교하는 방법을 배울 수 있다.정렬 알고리즘에 적용한 기술들을 다른 문제에도 유사하게 활용할 수 있다.정렬을 먼저 수행하면 효율적으로 문제를 해결할 수 있거나 해결 불가능한 문제도 가능하게 해준다. 버블 정렬?각 패스마다 정렬되지 않은 값 중 가장 큰 값을 의미하는 버블이 올바른 위치로 이동하게 되면서 정렬이 수행되는 알고리즘이다. 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이라고 생각하면 쉽다. 📌 버블 정렬의 동작 순서.배열 내에서 연속된 두 항목.. 2024. 8. 2. 자료구조 - 백(Bag), 스택(Stack), 큐(Queue) 백(Bag)'우리는 항상 가방에서 물건을 꺼낼 때 중간에 있는 물건을 잡기 마련이다. 그리고 그 중간의 물건을 꺼내게 된다.'는 발상에 근거하여 Bag 자료구조가 나타나게 되었다. 백은 항목을 삭제할 수 없는 컬렉션으로 항목을 수집하고 수집된 항목들을 순회할 수 있는 도구를 제공한다. 항목들은 서로 어떤 순서로 순회하는지 전혀 상관하지 않는다. 그래서 항목의 순서에 특별히 의미가 없다면 백을 이용한다. 📌 백을 사용하는 이유백을 사용하는 이유는 단순히 데이터를 추가하고자 할 때 사용한다. 예를 들어, 중간에 조작을 하면 안 되는 로그 데이터 등의 경우에 백을 사용할 수 있다. 배열을 사용할 수도 있지만, 추상 데이터 타입은 필요한 연산만 제공하여 중간의 값을 읽거나 삭제할 수 없도록 강제하여 데이터의 .. 2024. 7. 26. 추상 데이터 타입(Abstract Data Type, ADT) 추상 데이터 타입(Abstract Data Type, ADT)?추상 데이터 타입은 데이터 타입을 정의하는 것이다. 이때, 데이터 타입을 정의하는 것을 데이터 추상화 혹은 추상 데이터 타입이라고 한다. 사용자는 원하는 대로 데이터 타입을 만들어 낼 수 있다. 이를 통해 사용자는 데이터를 더욱 구체적으로 표현하고 쉽게 사용할 수 있게된다. 추상 데이터 타입은 데이터가 구체적으로 어떻게 표현되어 있는지를 사용자가 알 수 없도록 숨기기 때문에 사용자는 데이터의 구체적인 표현 방식을 몰라도 된다. 이는 데이터를 더욱 안전하게 보호할 수 있게 해준다. Ex.)Conuter()카운터를 생성합니다.increment():void카운터의 값을 증가시킵니다.reset():void카운터의 값을 0으로 초기화 합니다.curr.. 2024. 7. 25. 알고리즘 - 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍?다이나믹 프로그래밍이란 큰 문제를 작은 문제로 나누어 해결하고 작은 문제의 결과를 재사용하면서 중복 계산을 피하며 작업을 줄여 효율적으로 문제를 해결하는 방법이다. 이때, 작은 문제를 하위 문제라고 한다. 하위 문제는 동일한 문제를 작게 만들어 해결함으로써 어떤 문제를 풀 때 더 작은 문제이다. 재귀 호출은 프로그램을 단순하게 만들 수 있지만, 불필요한 재귀 호출이 일어나면 재귀 코드의 속도를 느리게 만들 수 있다. 그래서 불필요한 재귀 호출이 일어나지 않도록 해야 한다. 하위 문제가 중첩되는 이유는 같은 함수를 여러 번 중복해서 호출하기 때문이다. 이러한 불필요한 호출을 줄이기 위해서 필요한 함수 호출을 한 번만 하고 그 결과를 변수에 저장한다. 피보나치 수열다이나믹 프로그래밍으로 .. 2024. 7. 15. 알고리즘 - 재귀(Recursive), 꼬리 재귀(Tail recursive) 재귀란?재귀는 자기 자신을 호출하는 함수이다. 알고리즘이 임의의 단계만큼 깊이 들어가야 한다면 재귀가 좋은 방법일 수 있다. 재귀 함수 분석 방법1. *베이스 케이스를 찾는다2. 베이스 케이스에서 함수가 어떻게 동작하는지 살핀다.3. 베이스 케이스 바로 이전의 조건을 찾는다.4. 베이스 케이스 바로 이전의 조건에서 함수가 어떻게 동작하는지 확인한다.5. 이전의 조건으로 거슬러 올라가면서 코드가 어떻게 동작하는지 확인한다.이렇게 재귀 함수는 베이스 케이스부터 거꾸로 올라가면서 추론하는 방법이 유용하다. *BaseCase베이스 케이스는 함수가 반복되지 않는 경우이다. 즉, 함수가 더 이상 자기 자신을 호출하지 않아서 종료되는 조건이다. 모든 재귀 함수는 무한으로 호출하지 않도록 베이스 케이스가 반드시 하나 .. 2024. 7. 15. BigO 표기법으로 최적화하기 BigO 표기법?- 시간 복잡도를 쉽게 소통하기 위해서 자료구조와 알고리즘의 효율성을 일관되게 설명하는 수학적 개념을 형식화한 표현- 일관되게 어떤 알고리즘이든 분석할 수 있다.- 알고리즘의 성능이나 복잡성을 분석할 때 사용된다.- 시간 복잡도 혹은 공간 복잡도를 나타낼 때 사용된다.- 데이터가 늘어날 때 알고리즘의 성능이 어떻게 변화하는지 추세를 나타낸다.- 대문자 O에 괄호 안에는 수식을 넣어 표기한다. Ex.) O(N), O(1), O(logN) BigO를 사용하는 이유빅오 표기법은 알고리즘의 효율성을 평가하는 데 중요한 도구이다. 빅오 표기법을 사용하여 알고리즘의 수행 시간을 예측하고 비교할 수 있다. 빅오 표기법을 이용하여 실행 시간이 더 적은 알고리즘을 선택하여 처리 시간을 단축할 수 있다. .. 2024. 7. 12. 이전 1 2 3 4 5 ··· 9 다음
