Update 240109
우선적으로 1회독 후 다회독할 예정
[알고리즘의 성능]
1.알고리즘
-정의 : 주어진 문제를 유한한 시간내에 해결하는 단계적 절차
-데이터 구조: 데이터를 조직하고 접근하는 체계적 방식
*좋은 알고리즘 기준
- 알고리즘과 데이터 구조 작업에 소요되는 실행시간
-기억장소 사용량
2.실행시간
-보통 알고리즘의 실행시간은 대체로 입력의 크기와 함께 성장한다.
-평균실행시간은 종종 결정하기 어렵다
-최악실행시간에 집중해야한다(가장 오래걸린 실행시간을 봐야지 개선이된다)
-실행시간을 구하려면 다양한 크기와 요소로 구성된 입력을 사용하여 실행해본다
-시스템 콜을 사용하여 실제 실행시간을 정확히 측정하고 결과를 도표로 작성하면서
실행시간 보는 방법이 있다.
※위와 같은 실험적 방법은 단점이 있다
-실험에 포함되지 않은 입력에 대한 실행시간을 제대로 반영하지 않을 수 있다.
-두 개의 알고리즘을 비교하기 위해서는, 반드시 동일한 하드웨어와 소프트웨어 환경이
사용되어야한다. (HW:프로세서, 클락비, 메모리,디스크 / SW: 운영체제, 프로그래밍언어, 컴파일러)
-알고리즘 자체를 완전한 프로그램으로 구현해야되는데 이것이 번거롭다
*실행시간 구하기 이론적 방법
-하드웨어나 소프트웨어와 무관하게 알고리즘의 속도를 평가할 수 있다.
-모든 입력 가능성을 고려하는 것이 중요(n이라는 가정이 붙는다)
-알고리즘을 구현한 프로그램 대신 의사코드로 표현된 알고리즘을 사용한다
3.의사코드
-알고리즘을 설명하기 위한 고급 언어
-컴퓨터가 아닌, 인간에게 읽히기 위해 작성됨
-자연어 문장보다 더 구조적이지만, 프로그래밍 언어 보다 덜 상세함
-알고리즘을 설명하는데 선호되는 표기법
4.임의 접근 기계 모델(RAM)
-하나의 중앙처리장치(CPU)
-메모리 각각의 셀은 임의의 수나 문자 데이터를 저장함
-메모리셀들은 순번으로 나열되며, 어떤 설에 대한 접근이라도 동일한 시간 단위가 소요됨
5.원시작업
-알고리즘에 의해 수행되는 기본적인 계산들
-의사코드로 표현가능
-임의접근기계 모델에서 수행시 상수시간이 소요된다고 가정
-ex: 산술식/논리식의 평가, 배열원소 접근, 메소드 호출
6.원시 작업 수 세기
-의사코드를 조사함으로써, 알고리즘에 의해 실행되는 원시작업의 최대 개수를 입력크기의 함수 형태로 결정할 수 있다.
-원시 작업 수 자체가 알고리즘 소요시간과 같다 .
7.Big-Oh표기법
-알고리즘 수행시간 표기방법 : f(n)= O(g(n))
-실행시간 함수에서 가장 높은 차수만을 건든다. f(n)=O(n^p)
*Big Omega, BIg Theta라는 알고리즘 수행시간 표기법이 또 있다.
[재귀]
1.재귀알고리즘 : 알고리즘 자신을 사용하여 정의된 알고리즘을 재귀적이라고 한다.
2.재귀의 요소
-재귀 케이스: 차후의 재귀호출은 작아진 부문제들을 대상으로 이루어진다.(알고리즘 자신을 호출하는 부분)
-베이스 케이스: 부문제들이 충분히 작아지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결한다.
(더이상 알고리즘 자신을 호출하지 않고 문제를 직접 처리하는 부분)
void sum(int n){
if(n==1) return 1; //베이스 케이스
else return n+sum(n-1);//재귀 케이스
}
3.기본 규칙
-베이스 케이스를 항상 가져야 하며, 이는 재귀없이 해결될 수 있어야한다.
-재귀 호출은 항상 베이스 케이스를 향하는 방향으로 진행되어야 한다.
-재귀는 꼭 필요한 경우에만 사용해라. 저장/복구 떄문에 성능이 저하된다.
4.연습 문제
백준 27433 팩토리얼 2
#include<stdio.h>
long long int sum(long long int n) {
if (n == 0) {
return 1;
}
else {
return n * sum(n - 1);
}
}
int main() {
long long int input = 0;
scanf("%lld", &input);
printf("%lld", sum(input));
return 0;
}
백준 10870 피보나치 수 5
#include<stdio.h>
int sum(int n) {
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
else {
return sum(n-1) + sum(n - 2);
}
}
int main() {
int input = 0;
scanf("%d", &input);
printf("%d", sum(input));
return 0;
}
백준 25501 재귀의 귀재
#define _CRT_NO_SECURE_WARNINGS
#include <stdio.h>
#include <string.h>
int tr;
int recursion(const char* s, int l, int r) {
tr++;
if (l >= r) return 1;//한자리 인 경우, 숫자 반전
else if (s[l] != s[r]) return 0;//앞뒤 자리가 다른 경우
else {
return recursion(s, l + 1, r - 1); //두자리 이상이고 비교하는 문자 2개가 같을 때
}
}
int isPalindrome(const char* s) {
return recursion(s, 0, strlen(s) - 1);
}
int main() {
int testNum = 0;
scanf("%d", &testNum);
char str[1001];
for (int i = 0; i < testNum;i++) {
tr = 0;
scanf("%s", &str);
int a = isPalindrome(str);
printf("%d %d\n", a, tr);
}
return 0;
}백준 2447 별 찍기-10
#include <stdio.h>
void star(int x, int y, int n)
{
if ((x / n) % 3 == 1 && (y / n) % 3 == 1)
{
printf(" ");
}
else
{ if (n / 3 == 0) // 종료조건
printf("*");
else
{
star(x, y, n / 3);
}
}
}
int main()
{
int n, i, j;
scanf("%d", &n);
i = 0;
while (i < n)
{
j = 0;
while (j < n)
{
star(i, j, n);
j++;
}
printf("\n");
i++;
}
}
백준 11729 하노이탑 이동 순서
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int hanoi(int num) {
if (num == 1) {
return 1;
}
else {
return 2 * hanoi(num - 1) + 1;
}
}
void hanoiMov(int num,int start, int end) {
int noNum = 0;
switch (start) {
case 1:
if (end == 2) {
noNum = 3;
}
else {
noNum = 2;
}
break;
case 2:
if (end == 1) {
noNum = 3;
}
else {
noNum = 1;
}
break;
case 3:
if (end == 1) {
noNum = 2;
}
else {
noNum = 1;
}
break;
}
if (num == 1) {
printf("%d %d\n",start,end);
}
else {
hanoiMov(num-1, start, noNum);//start에서 start와 end가 아닌 수로 가야함
printf("%d %d\n",start,end);
hanoiMov(num - 1, noNum, end);
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n",hanoi(n));
hanoiMov(n, 1, 3);
return 0;
}
하노이탑은 3개의 기둥이 있는 것이다. 이 3개의 기둥은 3가지로 구분할 수 있다. 처음 시작할 때 원판이 있는 기둥(start),
최종적으로 원판을 모두 규칙에 맞고 옮겨야하는 기둥(end) 그리고 이 2가지에 해당하지 않는 남은 기둥(noNum)
위 문제에서 구해야하는 것은 1)하노이탑의 최소 이동횟수, 2)하노이탑의 원판의 이동 경로 이다.
*하노이탑의 최소 이동횟수.
1개 이동횟수 = 1
2개 이동횟수 = 1개 noNum으로 이동횟수 + 2번 원판 이동횟수 1회 + 1개 noNum에서 end로 이동횟수
3개 이동횟수 = 2개 noNum으로 이동횟수 + 3번 원판 이동횟수 1회 + 2개 noNum에서 end로 이동횟수
4개 이동횟수 = 3개 noNum으로 이동횟수 + 4번 원판 이동횟수 1회 + 3개 noNum에서 end로 이동횟수
n개 이동횟수 = n-1개 noNum으로 이동횟수 + n번 원판 이동횟수 1회 + n-1개 noNum에서 end로 이동횟수
위 식으로 일반화를 할 수 있는데, 일종의 점화식이다.
(점화식은 더 작은 요소로 치환해서 진행된다는 점에서 재귀와 밀접하다고 본다. )
(재귀 문제를 풀기 위해서는 하노이 탑의 원판의 개수가 작을 때를 상정해서 생각해보면 도움이 된다. )
이동횟수에 어디로 가는지는 중요하지 않으므로
n개 이동횟수= 2* (n-1개의 이동횟수) +1 이라고 볼 수 있다.
*하노이탑의 이동 경로
n개의 이동경로
= n-1개를 start 기둥에서 noNum 기둥으로 옮기는 경로 + start기둥에서 end 기둥으로 n번 원판 옮기는 경로
+ n-1개를 noNum 기둥에서 end 기둥으로 옮기는 경로
위 2가지 식을 이용하면 된다 .
[리스트]
0.구조체 문법
리스트 구현시 참조
1.순차 자료구조
:배열
순차 자료구조는 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성
문제를 그대로 안고 있다.
2.연결자료구조
각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 구현방식
물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.(누수)
노드 단위로 메모리가 할당되며,
저장 위치의 순서와 상관없이 노드의 링크 필드에 다음 자료의 주소를 저장한다.
노드={data, link} . C언어로 구현시 구조체와 포인터 조합이다.
연결 구조는 포인터를 담을 저장 공간이 추가로 필요한 대신, 삽입이나 삭제 연산을 하고 난 다음에
논리적 순서와 물리적 순서를 맞추기 위해 추가로 작업하지 않아도 된다. 그만큼 오버헤드가 발생하지
않아 삽입이나 삭제 연산을 할 때 효율적이다.
1)단순 연결 리스트
-사용하는 함수: 노드추가/ 노드 삭제/ 노드 검색
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode{
element data;//int 형인 데이터
struct ListNode *link;//ListNode 구조체의 포인터
} ListNode;
void error(char *message){
fprintf(stderr,"%s\n",message);
exit(1);
}
ListNode* insert_first(ListNode *head,element value){ //첫 노드 추가
ListNode *p=(ListNode *)malloc(sizeof(ListNode));
p->data=value;
p->link=head;//기존에 헤드 역할을 하고 있는 노드의 주소
head=p;//이제는 head의 역할이 p로 바뀌므로 head주소는 p주소이다
return head;//헤드는 선두 노드
}
ListNode* insert(ListNode *head,ListNode* pre, element value){일반적인 노드 추가
ListNode *p=(ListNode *)malloc(sizeof(ListNode));
p->data=value;
p->link=pre->link;
pre->link=p;//pre는 연결할 주소를 받는다.
return head;
}
ListNode* delete_first(ListNode *head){//첫 노드 삭제
//head는 없어져서는 안되는 요소이므로 removed라는 노드에 넣어두었다가 두번째 노드로 변경한다.
ListNode *removed;
if(head==NULL) return NULL;
removed=head;
head=removed->link;
free(removed);
return head;
}
ListNode* delete(ListNode *head,ListNode *pre){ //노드 삭제
ListNode *removed;
removed=pre->link;
pre->link=removed->link;
free(removed);
return head;
}
void print_list(ListNode *head){//연결된 자료 출력
for (ListNode *p=head;p!=NULL;p=p->link){
printf("%d->",p->data);
}
printf("NULL\n");
}
int main() {
ListNode *head=NULL;
for(int i=0;i<5;i++){
head=insert_first(head,i);
print_list(head);
}
for(int i=0;i<5;i++){
head=delete_first(head);
print_list(head);
}
return 0;
}
//출처 : https://velog.io/@kysung95/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%A1%A0-C%EB%A1%9C-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%A5%BC-%EB%A7%8C%EB%93%A4%EC%96%B4%EB%B3%B4%EC%9E%90
2)원형 연결 리스트
-마지막 노드의 링크가 첫번째 노드를 가리킴
-하나의 노드에서 링크를 따라가면 모든 노드 방문 가능
-모든 노드의 링크가 NULL이 아니다.(head가 Null인경우 제외)
-단순 연결리스트에서 마지막 노드가 첫번째 노드를 가르키도록 하면 된다.
-이때 첫번째 노드는 header가 가르키는 노드를 말한다.
-head는 첫번째로 추가한 노드의 주소가 된다. 마지막 노드로 하면 불편하다.
-사용하는 함수 : 노드추가/ 노드 삭제/ 노드 검색
*앞부분에 노드 추가하는 함수
(1).추가한 노드의 link에 head 노드의 link의 값을 넣는다.
(2).head 노드의 link에 추가한 노드의 주소를 넣는다.
*뒷부분에 노드 추가하는 함수
(1).추가한 노드의 link값에 head의 link값을 넣는다.
(2).head의 link에 추가한 노드의 주소를 넣는다.
(3).head의 주소를 추가한 노드의 주소로 바꾼다.
위 사진의 순서대로 함수를 구성하면 된다.
노드 삭제의 경우, 단순 연결 노드에서 중간 노드를 지우는 것과 다름이 없다.
모든 노드가 앞뒤로 연결되어있는 노드가 있기 때문이다. 지울 노드의 주소만 알면된다.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode {
element data;//int 형인 데이터
struct ListNode* link;//ListNode 구조체의 포인터
} ListNode;
ListNode* insert_front(ListNode* head, element value) { //앞 노드 추가
ListNode* p = (ListNode*)malloc(sizeof(ListNode));
if (head == NULL) { //첫노드
head = p;
p->data = value;
p->link = NULL;
}
else{
p->data = value;
if (head->link == NULL) {//두번째 노드추가
p->link = head;
head->link = p;
}
else {// 그 이후 노드 추가
p->link = head->link;
head->link = p;
}
}
return head;
}
ListNode* insert_back(ListNode* head, element value) {//뒤 노드 추가
ListNode* p = (ListNode*)malloc(sizeof(ListNode));
p->data = value;
if (head ==NULL) {//첫번째 노드 추가
p->link = NULL;
head = p;
}
else {
if (head->link == NULL) {//두번째 노드 추가
head->link = p;
p->link = head;
head = p;
}
else{//그 다음 노드 추가
p->link = head->link;
head->link = p;
head = p;
}
}
return head;
}
void print_list(ListNode* head) {//연결된 자료 출력
if (head == NULL) {
printf("No Data Form\n");
}
else {
if (head->link == NULL) {//노드 1개인 경우
printf("head %d->\n", head->data);
}
else {//노드 2개 이상
ListNode* p = head;
printf("head ");
do {
printf("%d->", p->data);
p = p->link;
} while (p!=head);
printf("\n");
}
}
}
int main() {
ListNode* head = NULL;
for (int i = 0;i < 5;i++) {
head = insert_back(head, i);
print_list(head);
}
return 0;
}
3)이중 연결 리스트
-자신의 노드와 뒤 노드를 가리키는 양쪽 방향에 링크가 있다(링크가 두개)
-사용하는 함수 : 노드추가/노드삭제/노드검색
3.연습문제
백준 1158
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct Node* link;
}Node;
Node* addNodeFirst(int newData, Node* head) {//리스트 끝에 노드 추가
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newData;
newNode->link = NULL;
head = newNode;
return head;
}
Node* addNode(int newData,Node* head) {//리스트 끝에 노드 추가
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newData;
newNode->link = head;
head = newNode;
return head;
}
void insertNode(int newData, Node *frontNode) {//중간에 노드 추가
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = newData;
newNode->link = frontNode->link;
frontNode->link = newNode;
}
Node* deleteFirst(Node* head) {
if (head == NULL)return NULL;
Node* removed;
removed = head;
head = head->link;
free(removed);
return head;
}
Node* deleteNode(Node*prev) {// prev->link->data 를 지우는 역할 . prev가 가르키는 노드를 지운다.
//일회적으로 지움
Node* deleteToNode = prev->link;
if (prev != NULL) {
prev->link = deleteToNode->link;
return prev;
}
}
void printNode(Node*head) {
while (head != NULL) {
printf("%d->", head->data);
head = head->link;
}
printf("NULL \n");
}
int main()
{
Node* head = NULL;
int a, b = 0;
scanf("%d %d",&a,&b);
//1.노드 만들기
head=addNodeFirst(a,head);
for (int i = a-1; i > 0;i--) {
head=addNode(i, head);//노드 만들기
}
//printNode(head);
//2.노드 숫자 뺴기
Node * startNode = head; //체크하는 노드, head는 NULL과 상반되는 곳
int nodeIndex = 0;
int deleteVal = 0;
Node* prevNode = NULL;
printf("<");
while (head != NULL) {
deleteVal = 0;
nodeIndex++;
if (startNode == head) {//선두 노드일때
if (nodeIndex==b) {//노드 빼는 경우
deleteVal =startNode->data;
printf("%d", deleteVal);
head=deleteFirst(head);
startNode = head;
nodeIndex = 0;
if (head != NULL) {
printf(", ");
}
}
else {//노드 안빼는 경우
prevNode = startNode;
startNode = startNode->link;
}
}
else if(startNode!= NULL){//중간 노드
if (nodeIndex == b) {//노드 빼는 경우
deleteVal = startNode->data;
printf("%d", deleteVal);
prevNode= deleteNode(prevNode);
startNode = prevNode->link;
nodeIndex = 0;
if (head != NULL) {
printf(", ");
}
}
else {//노드 안뺴는 경우
prevNode = startNode;
startNode = startNode->link;
}
}
if (startNode == NULL)
{
if (head != NULL) {
startNode = head;
prevNode = head;
}
else {
//while 종료
printf(">");
}
}
}
return 0;
}
[집합]
[스택]
[큐]
[트리]