본문 바로가기

Basic Computer Science18

5. 리스트 - 알고리즘 문제 11728번: 배열 합치기 (acmicpc.net) 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 알고리즘 문제 풀이 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 그림으로 정.. 2023. 7. 12.
4. 리스트 - 이중 연결 리스트 (Double Linked List) 1. Double Linked List 개념 Pointer가 앞뒤로 두 개가 들어가기 때문에 동일 데이터 양의 Single Linked List 보다 더 많은 용량이 필요하다. 데이터 추가 시 Tail Node로 접근해서 데이터 추가가 가능하다. 데이터 검색/삽입 시 인덱스가 Head보다 Tail에 가까우면 Tail로 타고 들어가서 검색/삽입이 가능하다. 따라서 Double Linked List는 더 많은 필요 용량에도 불구하고 성능 상 나름의 장점을 가지게 된다. (시간 복잡도로는 Single Linked List와 동일하게 O(n)이지만 연산 속도가 더 짧을 것으로 예상할 수 있다) 2. Double Linked List 구현 (JAVA) single Linked List와 마찬가지로 Node 기반으.. 2023. 7. 11.
3. 리스트 - 연결리스트(Linked List) 1. Linked List 개념 Node는 데이터 필드와 다음 Node를 가르키는 포인터 필드로 구성되어 있다. 가장 앞에 위치한 Node = Head 가장 뒤에 위치한 Node = Tail 이며 Tail은 가르킬 Node가 없으므로 Null을 가르킨다. 데이터 검색 시 인덱스 기반이 아니라 Node들의 Pointer를 통해 검색해 들어가야하므로, 검색의 시간 복잡도가 데이터의 개수와 같은 O(n)이다. 데이터 추가 시 Tail에 추가 Node를 넣어주므로 시간 복잡도가 역시 O(n)이다. 데이터 삽입 시 데이터를 배열 리스트처럼 뒤로 미뤄줄 필요는 없고, 포인터를 통해 연결해주면 된다. 다만, 데이터 삽입 될 곳을 찾아가는 과정 때문에 시간 복잡도가 역시 O(n)이다. 또한, Head에 앞쪽으로 데이터.. 2023. 7. 11.
2. 리스트 -배열(Array List) 1. ArrayList 구현 (JAVA) Java가 익숙치 않아서 조금 어려움이 있지만 주석을 달면서 개념을 이해해 가보자! package list; import java.util.Arrays; public class MyArrayList implements IList { private static final int DEFAULT_SIZE = 50; private int size; // 배열안에 들어가 있는 데이터 사이즈, 인덱스 역할 변수 private T[] elements; // 삽입할 데이터 변수 T[]은 임의의 데이터 유형을 받을 수 있도록함 public MyArrayList() { // 배열리스트 생성자 만들기 this.size = 0; this.elements = (T[]) new Objec.. 2023. 7. 10.
1. 자료구조 기초 0. 자료구조란 자료(데이터)를 어디에 어떻게 관리(검색, 순회(iterate), 저장, 삭제, 변경) 할지 자료를 담는 추상적인 틀 데이터의 형태와 쓰임에 가장 적합한 자료구조를 사용해야 컴퓨터의 자원을 효율적으로 사용 가능하다. 각 자료구조의 특징 / 장점 / 한계를 파악해야한다. * 알고리즘 : 어떤 문제를 풀기 위한 동작의 절차 Input 값을 통해 Output의 결과를 내는 것 1. 빅오 표기법 (자료구조, 알고리즘을 비교한다) 자료구조 또는 알고리즘이 문제를 해결하기 위한 가장 상한(최악)의 시간을 기준으로 한다. - 가장 큰 영향력이 있는 항만 표시 - 상수항은 무시 2. 시간 복잡도(데이터 처리에 소요되는 시간) O(1) : 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘.. 2023. 6. 29.
0. 자료 구조 시작 자료 구조 공부 이유 - Cybersecurity 석사 과정 시작 전 필수 학부 과목 공부 CS 학부과정을 전혀 듣지 않았었기 때문에 준비해야하는 것이 무엇인지 찾아보다가, 전공자들이 공통적으로 가장 필요하다고 이야기하는 자료구조 먼저 공부하기로 했다. 다행히 예전에 돈 벌때 끊어 둔 패스트 캠퍼스의 컴퓨터 공학 전공 필수 강의가 있어서 이걸로 해본다. - 개발자들 코딩 테스트 혹은 면접 시 자료구조, 알고리즘이 필수 그만큼 중요하다는 뜻? 개발할 건 아니지만 대충 왜 이렇게 코드가 구현 됐는지 이해할 때 필요할 것 같다. 프로그램 성능과 직결되는 것이 자료구조 / 학부생들 첫번째 탈주가 가장 많이 일어나는 과목 Java를 이용해서 실제 구현하는 실습까지 진행한다. 2023. 6. 29.

티스토리툴바