선형탐색

정의💡 한쪽 끝에서 시작하여 원하는 요소를 찾을 때까지 목록의 각 요소를 조사하는 알고리즘요소를 찾지 못하는 경우에는 데이터셋의 끝까지 간다.효용배열, 연결리스트의 정렬여부와 무관하게 원소를 탐색할 수 있음그러나 배열이 정렬되어 있고 원소가 배열 내에 존재하는 경우에 탐색 성능이 올라감절차1. 시작: 컬렉션의 첫번째 원소에서부터 시작2. 비교: 현재의 원소와 찾고자하는 원소와 비교3. 확인: 현재 원소가 찾고자하는 원소인 경우 true 또는 현재 원소의 인덱스를 반환4. 이동: 찾고자 하는 원소가 아닌 경우에는 컬렉션의 다음 원소로 이동5. 반복: 컬렉션의 끝에 도달할 때까지 2에서 4의 과정을 반복6. 찾지 못한 경우: 컬렉션의 끝에 도달해도 원소를 찾을 수 없는 경우에는 찾을 수 없음 반환구현Hor..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 7.

선택정렬(Selection Sort)

정렬이란?💡원소들의 크기에 따라 순서를 배치하는 것내림차순: 크기가 증가하는 순으로 원소들을 배치하는 것오름차순: 크기가 감소가는 순으로 원소들을 배치하는 것 선택정렬(Selection Sort)💡리스트를 반복적으로 순회하며 현재 위치에 맞는 값을 선택하여 제자리에 놓는 방식동작방식초기상태첫번째 반복두번째 반복반복종료구현#include using namespace std;int main(){ int arr[] = {8, 3, 2, 5, 1, 1, 2, 5, 8, 9}; int size = sizeof(arr) / sizeof(arr[0]); // 선택정렬 for (int i = 0; i arr[j]) { swap(a..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 2.

[백준 16165 (실버3)] 걸그룹 마스터 준석이(파이썬)

문제출처https://www.acmicpc.net/problem/16165문제분석① 걸그룹에 대한 정보를 입력 받은 후에 ② 퀴즈의 유형에 따라 출력하는 값의 형태가 결정되는 프로그램을 구현하는 문제였다. 예를 들어, '사나'와 1을 퀴즈로 입력 받으면 '사나가 속한 그룹의 이름'을 출력해야 하고 '레드벨벳'과 0을 퀴즈로 입력받으면 '레드벨벳'에 속한 멤버들의 이름을 알파벳 순으로 출력해야한다. 퀴즈의 유형은 1과 0으로 구분된다. 1이면 멤버의 이름으로 그룹명을 찾아야 하고 0이면 그룹명으로 멤버의 모든 이름을 찾아야 한다. 문제접근dict을 활용하기로 하였다. 이름을 조회해서 관련 된 이름을 검색하기에 dict이 좋기 때문이다.  dict은 키와 값으로 이뤄진다. hash table을 파이썬에 구현..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 5. 10.

다이나믹 프로그래밍

다이나믹 프로그래밍이 필요한 이유공간을 희생해서 시간을 벌자.현실의 문제들 중에 그대로 컴퓨터로 해결하기에는 어려운 것들이 많다. 해를 구하는데 시간이 오래 걸리거나 메모리 공간을 매우 많이 필요한 경우가 그러하다. 그래도 메모리공간을 담보로 연산속도를 향상 할 수 있는 방법들이 존재한다. 다이나믹 프로그래밍이 그 중에 하나다.적용조건1. 큰 문제를 작은 문제로 나눌 수 있다.2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.기본 아이디어Memoization, DP table피보나치 수열을 예를 들자. 피보나치 수열은 연속 된 두개의 항이 그 다음 항의 합인 수열이다.f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1피보나치 수열은 재귀함수로 구현할 수 있다..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 5.

자료구조와 알고리즘 공부 로드맵

https://roadmap.sh/datastructures-and-algorithms Data Structures and Algorithms Roadmap Learn about Data Structures and Algorithms using this roadmap. Community driven, articles, resources, guides, interview questions, quizzes for modern backend development. roadmap.sh 자료구조와 알고리즘 로드맵입니다.

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 3. 30.

큐(queue): 점심시간에 은행에서 업무를 보는 사람들

개론 큐란? 큐는 스택과 같이 데이터를 임시로 저장하는 자료구조 입니다. 스택은 가장 나중에 들어간 데이터가 먼저 나오는 후입선출(Last in First Out, LIFO) 구조라면 큐는 가장 먼저 들어간 데이터가 먼저 나오는 선입선출(First in First Out, FIFO) 구조 입니다. 은행창구에서 번호표대로 업무 보는 사람들, 놀이기구를 타기 위해 줄을 사는 사람들 모두 큐입니다. 큐의 작업와 구조 큐에 데이터를 넣는 행위를 인큐(enqueue)라고 합니다. 데이터를 제거하는 행위를 디큐(dequeue)라고 합니다. 큐에서 데이터 입구는 rear, 데이터 출구는 front 라고 합니다. 큐의 구현방법 큐는 배열로 구현하는 방법과 링 버퍼로 구현하는 방법 두가지가 있습니다. 큐는 데이터의 추가..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 3. 27.