분류 전체보기
-
Stack - 배열,연결리스트,원형연결리스트자료구조와 알고리즘/자료구조 2023. 5. 4. 11:33
- 스택은 데이터를 한 쪽 끝에서만 넣거나 뺄 수 있는 자료구조이다. -장/단점 장점: 구현이 쉽다, 데이터 저장 및 읽기 속도가 빠르다. 단점: 저장 공간 낭비, 데이터의 최대 갯수를 미리 지정해야함 *이는 스택의 장점을 최대한 활용하기 위해 배열기반으로 스택이 구현 되므로 발생하는 단점이다. -활용 컴퓨터 프로그램에서 함수를 부를 때 스택을 사용한다 > 순차적으로 읽으며, 가장 먼저 호출됨 함수가 가장 먼저 실행 > 위와 같이 함수 정보를 저장하는 스택을 콜스택이라고 함 재귀함수 또한 가장 마지막에 호출된 함수를 가장 먼저 실행하므로 스택의 구조로 구현된다고 볼 수 있다. -구현 >배열 기반 스택 헤더 #ifndef _St_Array #define _St_Array #define MAX_DATA 10..
-
LinkedList(3) 원형연결리스트자료구조와 알고리즘/자료구조 2023. 5. 2. 14:49
원형 연결리스트란, 리스트의 끝과 처음이 연결되어 참조하는 형식의 연결리스트를 말한다. 위 그림과 같이 연결의 형태가 원을 이루는 것을 원형연결리스트라고 부른다. 기존 연결리스트에서 head대신 tail을 사용하고 tail->next가 첫번째 노드를 가리키게 하면 된다. -ADT ADT는 크게 달라진 것이 없다. void Linsert --> 새 노드를 뒤에 추가 void LFinsert --->새 노드 처음에 추가 void Linit int LFirst int Lnext Ldata LRemove int Lcount - C언어 구현 헤더 #ifndef Circular_LinkedList #define Circular_LinkedList #define false 0 #define true 1 typedef..
-
LinkedList(2) - ADT와 구현자료구조와 알고리즘/자료구조 2023. 5. 1. 21:35
1 . ADT - 단순하게 데이터가 한쪽 방향으로 저장되고, 시작과 끝이 분명한 LinkedList를 구현해 보도록 하자. - 더미노드 기반으로 head만 존재한다. - ADT는 배열기반 연결리스트와 크게 차이가 없다. (정렬 추가) void Listinit(List * plist) > 리스트 초기화 void LInsert(List* plist, Ldata data) >리스트에 데이터를 추가 int LFirst(List* plist, Ldata* data) > 리스트에 저장된 데이터 참조를 위함 int LNext(List* plist, Ldata* data) > 리스트 저장된 데이터 참조 Ldata Lremove(List* plist) >리스트에 저장된 데이터 삭제 int Lcount(List* plis..
-
LinkedList (1)자료구조와 알고리즘/자료구조 2023. 5. 1. 17:18
데이터를 동적으로 할당하는 linkedList에 대해서 알아보기 전에 간단하게 그 컨셉에 대해 구현해보았다. #include #include typedef struct _node{ int data; struct _node* next; }node; int main(){ node* head =NULL; node* tail =NULL; node* cur =NULL; node* newnode = NULL; int readData; //데이터 읽기 while(1){ printf("자연수를 입력 하시오 종료하려면 0 입력"); scanf("%d",&readData); if(readDatadata =readData; newnode->next = NULL; if(head==NULL){ head=newnode; } el..
-
백준 15990 - 1,2,3 더하기 5자료구조와 알고리즘/문제풀기 2023. 4. 14. 15:09
전에 풀었던 1,2,3 더하기 업그레이드 버전이다. 같은 수를 중복하지않은 1,2,3 더하기를 만들면된다. 여기서 중복, 감소, 증가라는 단어를 살펴보면 1,1,2,3,4,3,2,1 -> 수를 바로 옆과 비교해서 두개씩 끊어서 생각해보면 된다. 1,1중복 -> 1,2중복x 증가 -> 2,3증가 ->3,4증가->4,3감소 계속 양 옆을 비교하는 것이다. 이제 문제로 돌아가보자. 문제에서는 중복되는 경우의 수를 제거하고 1,2,3을 사용해서 숫자를 만드는 경우의 수를 찾고 싶다. 예시 처럼 4를 만들고자 한다면, 3+1, 1+3,1+2+1의 꼴로 만드는 것이다. 먼저 그냥 1,2,3 더하기 처럼 생각해보자 N이라는 숫자를 만드는 경우의 수는 다음과 같다. N = N-1 +1 N-2 +2 각각 마지막 수까지 ..
-
백준 11052 - 카드 구매하기자료구조와 알고리즘/문제풀기 2023. 4. 14. 11:53
구매하려는 카드 N이 주어졌을 때, 카드 N개를 갖기 위해 지불해야하는 금액의 최댓값을 구하는 문제이다. 먼저 문제를 분석해보자. 민규는 카드를 어떻게 구매할 수 있을까? 각 카드팩의 가격이 카드의 갯수와 함께 주어졌다. 카드 1개 p[1] = M원 카드 두개 p[2] = K원 .. 민규가 N개의 카드를 구매한다면, N-1개가 들어있는 카드팩을 구매하고 p[1]개를 구매해서 N개 N-2개가 들어있는 카드팩을 구매하고 p[2]개를 구매해서 N개 0개가 들어있는 카드팩을 구매하고 p[N]개를 구매해서 N개를 구매하는 경우의 수로 나누어 생각해 볼 수 있을 것이다. 우리는 이 중에서 가장 비싸게 카드를 구매하는 방법을 찾으면 된다. 따라서 점화식은 D[n] = MAX(p[i] + D[n-i])일 것이다. 구하..
-
백준 11727 - 2 X N 타일링 2자료구조와 알고리즘/문제풀기 2023. 4. 14. 10:58
2*n타일링 문제에서 채울 수 있는 타일 2*2가 추가 된 것이다. 이제 2*2 타일은 2*1과 1*2와 2*2타일로 채울 수 있다. 3가지 타일로 다른 2*n타일로 마찬가지로 n-1타일에 2*1타일 추가 n-2타일에 1*2위아래 추가 n-2타일에 2*2타일 추가의 경우의 수로 2*n타일을 채우는 경우의 수를 생각할 수 있으니 점화식은 D[n] = D[n-1]+D[n-2]+D[n-2]이다. 상태:N , 종료조건 : 0일때는 0 1일때 1개 2일때 3개 return import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static int[] d; public static void main(Stri..
-
백준 11726 - 2 X N 타일링자료구조와 알고리즘/문제풀기 2023. 4. 14. 10:51
2*N 사이즈의 사각형을 2*1 타일 혹은 1*2타일로 채우는 방법의 경우의 수를 찾는 문제이다. - 먼저 상태와 종료조건을 생각해보자. => 상태 N , 종료조건 : ? 변하지 않는 것: 각 2*N의 타일을 채우는 경우의 수 가령 2*2타일을 채운다면, 2*1 옆으로 두개 1*2위아래로 두개씩 채울 수 있는 경우의 수 2가지 등 2*N의 타일을 채우는 경우의 수를 찾는 과정에서 생기는 2*N-1 ....2*1을 채우는 경우의 수는 변하지 않을 것이다. 이제 큰 문제를 작은 문제로 쪼개서 생각해보자. 2*N타일을 채우는 과정에서 2*n-1 ..2*n-2.. 2*n-3의 타일들을 채우는 경우의 수가 변하지 않는다면, 이를 활용할 수 있을 것이다. 2*N-1타일에서 2*1타일 하나가 추가된 모양이 2*N타일..