Computer Science/자료구조24 [자료구조] ep3-1) 단일연결리스트(Single Linked List) ㅁ리스트 ADT: 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조응용 예: 스택, 큐, 집합 / 소규모 db(주소록 등) or 더 복잡한 데이터구조 재료 ※노드(node): 커다란 자료구조의 일부분 하나 하나를 의미e.g. 리스트의 노드, 트리의 노드 리스트는 배열과 쓰임새가 비슷해 보통 많이들 비교한다 ㅇ단일연결리스트: 노드 간의 링크가 하나 활용) 다항식을 표현하는 연결리스트한 개의 다항식(polynomial)을 한 개의 헤더 단일연결리스트로 표현하는 방식(연결리스트의 각 노드는 차수의 내림차순으로 유지하고, 계수가 0인 항의 노드는 유지하지 않음) 여기서 다항식의 덧셈을 구하는 프로그램을 만들자 (전체 코드)#include #include #pragma warning (.. 2024. 5. 3. [자료구조] ep2+) 하노이 탑 구현 하노이 탑이란? B 기둥을 이용해서 A 기둥에 놓인 크기가 다른 원판을 C 기둥으로 옮기는 문제이다. 이때 원판은 한 번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다.+ 이동횟수 공식은 (2^n - 1) 회이다 e.g. n = 1인 경우 1회의 이동, n = 2인 경우 3회의 이동, n = 3인 경우, 7회의 이동 문제)원반의 개수 N을 입력받아, 하노이 탑 문제의 수행과정을 출력하는 프로그램을 작성해라 의사코드)n: 이동해야 할 원반 수from: 출발 기둥aux: 보조 기둥to: 목표 기둥 모식도) //A에 1~N 쌓여있음 A B C 1 2 . . N //N-1개를 A에서 C를 거쳐 B로 이동 A B C N 1 .. 2024. 4. 7. [자료구조] ep2) 재귀(Recursion) ㅇ재귀(recursion): 종료조건을 만족하기 전까지 자기 자신을 계속해서 호출→ 종료조건을 잘 설정해야 한다진행 방향: 종료조건을 향하여 진행작동 원리: stack을 생각하자 (LIFO, 후입선출) 이 작동원리에 대한 마인드셋이 너무 너무 중요하다예를 들어 재귀함수는 3건의 요청이 들어온다 하면 한 함수가 3건의 요청을 처리하는 것이 아닌, 각각 3개의 함수가 1건의 요청을 처리하는 것이다 (재귀함수를 이해하기 위한 최고의 그림이자 예시이다, 세종대 컴공 교수님들 최고!) 참고 및 출처: 실전 C프로그래밍(나중채, 한동일 등), 데이터 구조 원리와 응용(국형준), C언어로 쉽게 풀어 쓴 자료구조(천인국) 2024. 4. 7. [자료구조] ep1+) 비트행렬로 배우는 시간복잡도의 중요성 그림과 같은 비트행렬 A가 있다고 하자, 1을 카운트하는 방법에는 다양한 방법들이 존재한다여기서 나는 2가지 방법을 얘기하려 한다 1. 가장 일반적인 방법으로 이중포문을 이용해 각 행마다 0이 나올 때까지 카운트를 하는 방법: O(n^2) 2. 제일 하단 좌측에서 시작해 우측 상단을 향해 지그재그 방식으로 올라오며 카운트를 하는 방법: O(n) 1번 방식은 시간복잡도가 O(n^2)이므로 n값이 커질수록 실행 시간은 제곱수로 증폭하게 된다반면에, 2번 방식은 시간복잡도가 O(n)이므로 n값이 커질 수록 실행 시간은 그저 선형적으로 증가하게 된다따라서 우리는 실행 시간의 측면에서 2번 방식이 압도적으로 더 좋은 것을 알 수가 있다그렇기에 우리는 상황에 맞는 자료구조와 알고리즘을 설계할 수 있는 능력을 길러야.. 2024. 4. 7. [자료구조] ep1) 자료구조 기본 지식들 ㅇ다차원 배열- 3차원 배열 - 4차원 배열 ㅇ빅오(Big O) 표기법: 연산의 횟수를 대략적(점근적)으로 표기"최악의 case 실행시간을 고려한다" [예시](1) 7n-2: O(n)(2) 3n^3 + 20n^2 + 5: O(n^3)(3) 3log(n) + log(log(n)): O(log(n))(4-1) n까지의 반복문: O(n)(4-2) n까지의 이중반복문: O(n^2)(4-3) n까지의 삼중반복문: O(n^3)(5) 조건문에서의 실행시간은 최악의 case로 합산한다+ O(log*n)은 중첩 log(n)을 의미 함수 증가율의 상한을 표시!※ 빅오메가, 빅세타 표기법과 공간복잡도는 생략 ㅇ의사코드 or 수도코드(pseudo-code): 컴퓨터가 아닌 인간에게 읽히기 위해 알고리즘을 간략하게 .. 2024. 4. 7. [자료구조] ep0) 자료구조란? 자료구조란 단어를 들었을 때 뭔가 막막하고 어려울 것 같은 느낌이 들지만 전혀 그렇지 않다 쫄 필요가 전혀 없다 자료구조에서 자료는 영어로 Data 이 Data는 개발에서 변수와 구조체를 뜻한다 우리가 변수를 선언할 때 앞에 자료형을 붙이지 않는가? e.g. int n 따라서 자료구조라는 학문은 변수와 구조체의 구조화를 연구하는 분야이다 한번 일상속에서의 자료구조를 찾아보자 ㅇ스택(stack): 그릇을 쌓아서 보관하는 것 ㅇ큐(queue): 마트 계산대의 줄 ㅇ리스트(list): 버킷 리스트 ㅇ딕셔너리(dictionary): 영어사전 ㅇ그래프(graph): 지도 ㅇ트리(tree): 컴퓨터의 디렉토리(폴더) 구조 그렇다면 왜 이 자료구조가 중요한 것인가? 물론 자료구조가 알고리즘의 선행되는 개념이기도 하고.. 2024. 1. 18. 이전 1 2 3 다음
