알고리즘 6

[컴퓨터과학개론] 알고리즘

알고리즘 개념 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것 입출력: 0개 이상의 외부 입력, 1개 이상의 출력 명확성: 각 명령은 모호하지 않고 단순 명확해야 함 유한성: 한정된 수의 단계를 거친 후에는 반드시 종료해야 함 유효성: 모든 명령은 컴퓨터에서 실행 가능해야 함 효율성 → 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것 알고리즘 생성 단계 설계 표현/기술 정확성 검증 효율성 분석 자료구조와 알고리즘의 관계 자료구조: 데이터 사이의 논리적 관계를 표현하고 조직화 하는 방법 효율적인 프로그램을 위해 자료구조와 알고리즘을 고려해야함 알고리즘 설계 문제와 그에 따른 조건 등이 매우 다양 → 일반적이고 범용..

CS 2023.11.30

[자료구조] 자료구조란 무엇인가

자료구조란 무엇인가 자료(data)와 정보(information) 자료를 입력해주고 이것을 처리해주면 우리가 원하는 정보를 얻을 수 있습니다(P(D) = I). 즉, 정보란 자료의 가공 결과입니다. 자료의 정의 현실 세계에서 관찰이나 측정을 통해서 수집된 값이나 사실 우리의 생활에서 실제로 만질 수 있거나 볼 수 있는 것 길이, 무게, 부피 등을 측정할 수 있는 대상에 대해서 물리적인 단위로 표현하여 얻어낼 수 있는 내용 정보의 정의 어떤 상황에 대해서 적절한 의사결정을 할 수 있게 하는 지식으로서 자료의 유효한 해설이나 자료 상호 간의 관계를 표현하는 내용 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 처리 과정을 거쳐서 정리되고 정돈된 자료의 2차 처리 결과물 ..

알고리즘 - 정렬

정렬 정렬은 요소들을 일정한 순서대로 열거하는 알고리즘입니다. 정렬 기준은 사용자가 정할 수 있으며, 크게 비교식과 분산식 정렬로 나눌 수 있습니다. 대부분의 언어가 빌트인으로 제공해주며, 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재합니다. 상황에 따라서 적합한 정렬 방식이 있기 때문에 절대적으로 빠르다라고 말할 수 있는 정렬 방식은 없습니다. 비교식 정렬 버블 정렬: 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘입니다. O(n^2)를 가집니다. 선택 정렬: 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘입니다. O(n^2)를 가집니다. 삽입 정렬: 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘입니다. O(n^2)를 가집니다. ..

알고리즘 - 이진탐색

이진 탐색 여러분이 보통 탐색에 많이 사용하시는 방법은 선형 탐색입니다. 즉, 순서대로 하나씩 찾는 탐색 알고리즘을 말합니다. O(n)의 시간복잡도가 걸립니다. 하지만 효율성을 높이기 위해서 우리는 정렬 되어있는 요소들을 반씩 제외하며 찾을 수 있습니다. 이것을 이진 탐색이라고 합니다. 이진 탐색은 **O(log n)**만큼의 시간복잡도가 걸립니다. 이진 탐색은 반드시 정렬이 되어 있어야 사용할 수 있으며, 만약 정렬이 되어있지않다면 선형탐색보다 더 많은 시간이 걸릴 수도 있습니다. 배열 혹은 이진 트리를 이용하여 구현할 수 있습니다. 배열 배열에서 요소를 찾으려면 시작 지점을 left, 끝 지점을 right라고 두며 mid = (left+right)/2 로 중간 지점을 표현합니다. 중간지점과 탐색할 요..

자료구조와 알고리즘을 공부해야 하는 이유? 자바스크립트 똑똑하게 쓰기!

💡 알고리즘을 공부하고 문제를 풀 때 마음가짐 1. 항상 여러가지 풀이 방법이 있을 수 있다. 2. 항상 예외가 있을 수 있다 3. 내가 이미 푼 답을 최적화하는 방법을 항상 고민해야 한다. 4. 풀지 못했던 코드 또한 남겨두는 것이 좋다. 5. 다른 사람의 코드를 많이 봐야, 나의 생각에서 벗어나 새로운 사고를 할 수 있다. 6. 문제를 쉽게 포기하지 말고, 도저히 모르겠다면 답을 보고 시간이 지난 후 다시 풀어보는 것이 좋다. 7. 알고리즘 마스터가 될 필요는 없지만, 익숙해져야 한다. - 회사는 업무를 수행 할 수 있는 기초 능력을 확인하고 싶은 것이기 때문에 문제 해결 능력을 기르는 것이 좋다. - 예외적으로 알고리즘이 중요한 회사(게임, 인공지능 등의 분야)인 경우에는 중요하기 때문에 알고리즘/..