본문 바로가기

분류 전체보기216

연결 리스트 연결 리스트(linked representation): 동적으로 크기가 변할 수 있고 삭제나 삽입 시 데이터 이동할 필요 x- 포인터를 사용하여 데이터들을 연결 - 다른 자료구조(트리, 그래프, 스택, 큐 등)를 구현할 때도 많이 사용- 물리적으로 흩어져 있는 자료들을 포인터로 서로 연결하여 하나로 묶음- 중간에 삭제하거나 삽입할 때 앞뒤에 있는 데이터들을 이동할 필요 없이 포인터만 수정 - 하나의 프로그램 내에 동시에 여러 개의 연결 리스트 존재 가능- 이 경우 첫 번째 데이터로 연결 리스트들을 구별(첫 번째 데이터를 확보하고 포인터로 따라가면 나머지 데이터들을 얻을 수 있음) - 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어 추가 가능- 배열로 구현하는 것보다 구현이 어려움- 데이터와 .. 2024. 7. 17.
배열로 구현된 리스트 리스트의 순차적 표현(sequential representation): 배열로 리스트를 구현하면 순차적인 메모리 공간이 할당 리스트의 정의#define MAX_LIST_SIZE 100typedef int element;typedef struct { element array[MAX_LIST_SIZE]; int size;} ArrayListType;- 배열과 항목 개수를 구조체로 묶어 ArrayListType라는 새로운 타입 정의 기초 연산- 리스트 연산들을 함수로 구현- 모든 연산은 구조체 포인터를 전달받음(함수 안에서 구조체를 변경해야 하며, 포인터를 사용하지 않으면 구조체의 복사본이 전달되어 원본 구조체를 변경할 수 없기 때문)//오류 처리 함수void error(char* message) { fpri.. 2024. 7. 17.
리스트 리스트- 순서 또는 위치를 가진 항목들이 차례대로 저장되어 있는 자료구조 - 삽입 연산, 삭제 연산, 탐색 연산 등 기본적 연산 가능- 집합은 항목 간에 순서의 개념이 없으므로 집합과는 다름 리스트 ADT리스트의 구현- 배열 또는 연결 리스트를 이용하여 리스트 구현 가능 1. 배열을 이용한 구현- 구현이 간단하고 속도가 빠름- 리스트의 크기가 고정되므로 동적으로 크기를 조절하는 것이 어려움- 더 큰 배열을 만들어 기존 배열의 데이터를 복사하는 식으로 해결 가능하지만 CPU 시간이 낭비됨- 리스트 중간에 새로운 데이터를 삽입하거나 삭제하기 위해 기존 데이터들을 이동해야 함 2. 연결 리스트를 이용한 구현- 크기 제한이 없음- 리스트 중간에서 쉽게 삽입하거나 삭제할 수 있음- 구현이 복잡- 임의의 i번째 항.. 2024. 7. 17.
백준 2346: 풍선 터뜨리기(java) 문제풀이 큐의 양 끝에서 삽입과 삭제가 일어나므로 덱을 사용한다.덱 객체 생성하는 부분에서 LinkedList를 업캐스팅하면 메모리가 초과되므로 ArrayDeque를 사용해야 한다.class Balloon{ int index; int value; public Balloon(int index, int value) { this.index=index; this.value=value; }}풍선의 번호와 풍선의 내용물 2개의 변수가 함께 변화해야 하므로, 풍선의 번호와 내용물 정보를 저장하는 Balloon 클래스를 작성했다.int[] balloonValue=new int[N]; for(int i=0; i읽어들인 풍선 내용물 숫자를 저장하는 balloonValue 배열을 생성하고, 덱에 Balloon 객체를 삽.. 2024. 7. 16.
백준 28279: 덱 2(java) 문제풀이 늘 하던 것과 동일한 유형이다자세한 설명은 생략하겠다.BufferedReader로 입력받아 StringTokenizer로 분리하고 cmd에 따라 switch문으로 분리해 준 다음 별도의 덱 구현 없이 JDK 제공 라이브러리 덱을 이용해 풀이하였다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Deque;import java.util.LinkedList;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ B.. 2024. 7. 16.
백준 11866: 요세푸스 문제 0(java) 문제풀이 큐의 전단과 후단에서 삽입과 삭제가 모두 일어나므로, 마찬가지로 덱을 사용해 풀이했다. for(int i=0; i우선 1부터 N까지의 값을 덱에 삽입하여 덱을 완성한다. 이제 K번째 요소를 덱에서 제거해야 하지만, 스택이나 큐와 마찬가지로 덱에서도 인덱스를 사용하여 덱의 중간에 삽입하거나 삭제할 수 없다. 따라서 K번째 값을 제거할 수 있도록 해당 요소를 덱의 전단이나 후단으로 이동시키는 연산이 필요하다.for(int i=0; iK번째 요소를 전단으로 가져오려면 K 앞에 있는 K-1개의 요소들을 제거한 뒤 후단에 삽입해야 하므로 위와 같이 작성할 수 있다. 도식적으로 표현하면 아래와 같다.사람들이 모두 제거될 때까지 위 과정을 반복해주면 된다.import java.io.BufferedReader.. 2024. 7. 16.

티스토리툴바