알고리즘 6일차

알고리즘 입력 처리 출력

 

자료구조란

어떻게 하면 저장 하려는 데이터를 적은 메모리를 사용해서 효율적으로 저장 할 수 있고 관리 할 수 있는지 결정 할 수 있는 지에 대해 결정 할 수 있는 거라고 할 수 있다.

 

어떠한 자료구조를 선택 하는 건 중요한 문제라고 할 수 있다. 

그러기 위해선  각 자료구조에 대해서 장점과 단점을 알고 있어야 한다. 

 

선형구조 (순차적인 순서를 가지는 것)

배열 (Array)

• 장점: 배열은 C#에서 System.Array 클래스로 구현되며, 배열의 각 요소는 인덱스로 접근이 가능하다. 이는 랜덤 액세스가 가능하다는 장점이 있다. 바로접근
• 단점: 배열의 크기가 고정되어 있어 크기를 변경할 수 없고, 요소를 삭제할 때 다른 요소들을 이동시켜야 한다.

 

연결 리스트 (Linked List)

단일 연결 리스트: C#에서는 LinkedList<T> 클래스로 구현할 수 있고, 배열처럼 연결이 되어 있지 않고 노드로 이루어져 있고 각각의 노드는 다음 노드를 가리키는 포인터 변수를 갖고 있다. 

• 장점: 중간 삽입 및 삭제가 빠르다.
• 단점: 각 노드가 다음 노드를 가리키는 포인터 변수를 갖고 있다. 그래서 메모리 오버헤드가 발생 할 수 있다. 또한, 인덱스로 접근하기가 어렵다. 데이터에 접근 하려면 1번부터 쭉 이동을 해서 접근을 한다.

이중 연결 리스트: LinkedList<T>는 양방향으로 연결된 리스트로, 뒤로 가는 것뿐만이 아니라 앞으로도 갈 수 있다. 

(0->1->2) 뒤로 가는 거 (3>2>1>0) 앞으로 가는 거

 

원형 연결 리스트: C#에서 기본적으로 제공하지는 않지만, LinkedList<T>를 이용해 구현할 수 있다. 마지막 노드가 첫 번째 노드를 가리키도록 하면 된다. null이 존재 하지 않는 형태이다. 다음 포인터가 계속 있으므로

 

스택 (Stack) 큐 (Queue)

한 쪽 방향으로 삽입과 삭제가 이루어지는 자료구조

 

덱 (Deque)

스텍과 큐가 합쳐진 것. 양 쪽 방향에서 삽입과 삭제가 이루어진다. 

 

 

비선형 구조(순서를 갖지 않는 자료구조)

트리 (Tree)

부모와 자식 관계로 이루어진 계층적 자료구조다. 이진 트리나 AVL 트리 등 여러 형태가 있으며, C#에서 트리를 직접 구현하거나 BinaryTree와 같은 클래스를 정의하여 사용할 수 있다.

최상위 노드 root

어떠한 노드에 접근 하고자 한다면 반드시 root부터 시작을 해야 한다.

방향으로 흐르는 방향그래프

 

그래프 (Graph)

정점(Vertex)과 간선(Edge)으로 이루어진 비선형 자료구조로, 방향성과 비방향성을 가질 수 있다. C#에서 그래프는 인접 리스트나 인접 행렬로 구현할 수 있다.

root가 없다.

시작점이 없어서 어디서 시작하든 상관이 없다. 서로서로 연결이 되어 있는 형태를 그래프라고 한다. 

다양한 방향이 존재 하는 게 그래프다.

 

 

4. 메모리 영역

스택 (Stack)

C#에서 지역 변수나 매개변수는 스택 메모리 영역에 저장된다. 메소드가 끝나면 스택에 할당된 메모리는 자동으로 해제된다. 블록이 끝나면이라고도 한다.

힙 (Heap)

동적 메모리 할당이 이루어지는 영역으로, C#에서는 new 키워드를 사용해 객체를 생성하면 힙에 메모리가 할당된다. 이 메모리는 Garbage Collector가 관리한다. 다른 언어는 직접 해제도 해줘야 한다.

데이터 (Data) 영역

전역 변수나 static 변수가 저장되는 메모리 영역, 프로그램이 실행될 때부터 종료될 때까지 이 메모리 영역에 존재한다.

 

 

리스트와 연결리스트의 차이점

둘 다 데이터를 순차적으로 저장 하지만, 구현 방식과 동작 방식에 큰 차이가 있다. 

 

리스트

• 구현방식 : 리스트는 기본적으로 배열 기반의 자료구조다. c#에서는 List<T> 클래스를 이요해서 리스트를 구현 할 수 있다. 이 클래스는 내부적으로 동적 배열을 사용해서 요소들을 저장 한다.
• 메모리 할당 : 배열 기반이므로 연속 된 메모리 공간에 데이터를 저장 한다. 처음엔 일정한 크기로 배열을 할당하고, 요소가 추가 될 때 배열의 크기가 부족하면 더 큰 배열을 할당 하고 기존 데이터를 복사 해서 옮기는 방식이다. 
• 접근 속도 : 인덱스를 사용 하여 O(1) 시간 복잡도로 특정 요소에 접근 할 수 있다. 랜덤엑세스, 몇 번째 인덱스에 즉시 접근 가능
• 삽입 / 삭제의 속도 : 리스트 중간에 요소를 삽입하거나 삭제 할 때는 해당 위치 이후의 모든 요소를 이동 시켜야 하기 때문에 O(n)의 시간복잡도가 걸릴 수 있다.  

 

연결리스트

• 구현방식 : 노드라는 개별 객체들이 서로 연결 된 형태의 자료구조다. C#에서는 LinkedList<T> 클래스를 사용해서 구현 할 수 있다. 각 노드는 다음 노드를 가리키는 포인터참조(변수)를 가지고 있다. 
• 메모리 할당 : 연속 된 메모리 공간을 사용하지 않으며, 각 노드는 동적으로 메모리가 할당 된다. 따라서 리스트에 요소를 추가 하거나 제거 할 때마다 배열처럼 데이터를 복사 할 필요가 없다. 포인터변수의 주소만 바꿔주면 된다.
• 접근속도: 특정 인덱스에 접근 하려면 첫 번째 노드부터 순차적으로 탐색 해야 하기 때문에 O(n)이 걸릴 수 있다. 
• 삽입/삭제 속도 : 연결 리스트의 큰 장점으로 중간에 삽입 하거나 삭제 할 때 요소를 이동 시킬 필요가 없다. 특정 노드의 참조를 변경하기만 하면 되므로 O(1)의 시간 복잡도로 처리 할 수 있다.

 

인덱스에 접근 하는 경우가 많은 경우에는 List, 인덱스에 접근 하는 경우는 적고 삽입과 삭제가 자주 일어나는 경우 연결 리스트를 사용 하는 것이 좋을 것 같다. 

 

 

자료구조알고리즘이란

자료구조와 알고리즘이 결합 되어 자료구조 알고리즘이라는 개념이 탄생 한 것이다. 

이는 데이터를 어떻게 구조화 하고, 구조화 된 데이터를 바탕으로 문제를 해결할 것인지에 대해 전략을 의미한다. 

 

데이터를 특정 자료구조에 저장 한 다음, 그 자료구조를 기반으로 문제를 해결 하는 알고리즘을 의미한다. 적절한 자료구조를 선택 하면 알고리즘의 성능을 크게 향상 시킬 수 있다. 

 

이진 탐색 트리, 우선 순위 큐 등과 같은 것을 자료구조 알고리즘이라고 할 수 있다. 

 

이진 탐색 트리 : 트리 자료구조를 사용 하여 데이터 탐색을 효율적으로 수행 하는 알고리즘이다. 반으로 나눠서 찾는 것이다. 이 트리를 사용 하면 평균적으로 O(log n) 시간 복잡도로 데이터를 삽입, 삭제, 탐색 할 수 있다. 

우선 순위 큐 : 힙 자료구조를 사용하여, 가장 높은 우선순위를 가진 요소를 빠르게 찾는 알고리즘이다. 이 구조를 통해 O(log n) 시간 복잡도로 요소를 삽입 하고 제거 할 수 있다. 

 

자료구조 알고리즘.

자료구조를 어떻게 더 효율적으로 관리 할 수 있을지에 대해 만든 것이 자료구조 알고리즘, 그래서 우선순위 큐 등이 있는 것 같다. 그래서 큐나 배열 등등 자료구조들을 한 번 구현 해보면 좋을 것 같다.

 

알고리즘, 자료구조들 만들어보고 코딩문제들 하기 

 

 

=====

유기농 배추

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

199961

81830

54376

38.573%

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

 

 

??