자료구조와 알고리듬 With Java/[zerobase] Algorithm

Chapter 02. 선형 자료구조

계란💕 2022. 5. 30. 13:20

2.1 자료구조 소개

  Def) 자료 구조(Data Structure): 자료를 효율적으로 관리하기 위한 구조

    - 목적에 맞게 사용한 자료구조는 실행시간 단축이나 메모리 용량 절감 효과가 있다.

    - 선형 자료구조 / 비선형 자료구조

 

  Note) 자료구조의 구현

    - 추상 자료형(absract Data type, ADT)

      -> 자료 형태와 자료에 대한 연산을 정의한 것

      -> 구체적인 구현 방법은 명시하지 않는다. (추상 클래스, 인터페이스)

 

 

2.2 배열

  Note) 배열

    - 데이터가 메모리 상에 연속적으로 저장된다 .

    - 데이터와 인덱스가 1:1 대응으로 구성된다.

    - 단점

      -> 데이터 추가/ 삭제가 번거롭다.

      -> 미리 최대 길이를 정해서 생성한다.

      -> 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성한다.

      -> 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간을 유지한다.

  Ex) 

java
열기

  Note) 실행 결과

 

 

2.3 배열 practice

  Ex 1) 주어진 배열에 대해 홀수 데이터의 평균과 짝수 데이터의 평균을 구하라

java
열기

  Note) 실행 결과

 

  Ex 2) 주어진 배열에서 target에 해당하는 값의 인덱스를 출력하라

java
열기

  Note) 실행 결과: 6

 

 

  Ex 3) 주어진 배열에 대해 데이터 순서를 거꾸로 변경하여 출력하라

java
열기

  Note) 실행 결과

 

 

  Ex 4) 배열에서 peek값을 출력하라

    - peek값이란? 좌우보다 큰 값을 말한다. 

java
닫기
<hide/>// Practice4
// 배열 arr 에서 peek 값 모두 출력
// 입출력 예시)
// arr: 3, 1, 2, 6, 2, 2, 5, 1, 9, 10, 1, 11
// 결과: 3, 6, 5, 10, 11

import java.util.Arrays;
public class Practice4 {
    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 6, 2, 2, 5, 1, 9, 10, 1, 11};
        for(int i = 0; i < arr.length; ++i){
            if(i == 0 && arr[i] > arr[i + 1]){
                System.out.print(arr[i]+ " ") ;
            }else if(i == arr.length - 1 && arr[i] > arr[i -1]){
                System.out.print(arr[i]+ " ") ;
            }else if(arr[i - 1] < arr[i] && arr[i] > arr[i + 1]){
                System.out.print(arr[i]+ " ") ;
            }
        }
       System.out.println();
    }
}

  Note) 실행 결과

 

 

  Ex 5) 배열의 데이터를 오름차순으로 출력한다.

java
열기

  Note) 실행 결과

 

 

  Ex 6) 배열에서 중복된 데이터를 없애고 새 배열을 만들어라

java
열기

  Note) 실행 결과

 

 

  Ex 7) 2차원 배열을 시계방향으로 90도 회전시킨 결과를 출력하라

 Sol) 

java
열기

 MySol)

java
열기

  Note) 실행 결과

 

 

2.4 연결리스트(LinkedList)

  Def) 연결 리스트:  데이터를 링크로 연결해서 관리하는 자료구조

    - 자료의 순서는 정해져있지만 메모리상 연속성이 보장되지는 않는다.

  

  Note) 장단점

  - 장점: 데이터 공간을 미리 할당할 필요가 없다. (리스트 길이가 가변적 - 데이터 추가, 삭제 용이)

 

  - 단점: 연결 구조를 위한 별도 데이터 공간 필요

    -> 연결 정보를 찾는 시간이 필요 (상대적으로 속도가 느리다.)

    ->  데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 필요하다. (head/ 중간/ tail)

  Note) Java에서는 Garbage Collection이 해당 메모리를 더이상 참조하지 않으면 자동으로 delete_Node를 지워준다.

 

  Note) 연결 리스트의 기본 구조

    Def) 노드(Node): 데이터 저장 단위로 값과 포인터로 구성된다.

    - 포인터(pointer): 다음 노드나 이전 노드의 연결 정보

    - 가장 앞에 있는 노드를 head, 가장 뒤에 있는 노드를 tail이라고 한다.

 

  Ex) 

java
열기

  Note) 실행 결과

 

 

  Ex) 단방향 연결 리스트

java
열기

  Note) 실행 결과

 

 

  Ex) 양방향 연결 리스트

java
열기

  Note) 실행 결과

 

 

  Ex) practice3  원형 연결 리스트

java
열기

  Note) 실행 결과

 

 

2.5 단방향 연결 리스트 practice

  Ex) practice1. 단방향 연결 리스트에서 중복 데이터를 찾아 삭제하라.

    - findData메서드의 반환형을  boolean으로 바꿔서 false인 경우에만 addData를 한다.

java
열기

  Note) 실행 결과

 

 

  Ex) practice2. 팰린드롬 연결 리스트: pallindrome 문자열이 맞는지 아닌지 확인하라

    - 단방향 연결 리스트로 팰린드롬 문자열 확인하기

java
열기

  Note) 실행 결과

 

 

  Ex) practice3  연결리스트 부분 뒤집기 - 주어진 연결 리스트에서 시작 위치부터 끝 위치 사이의 노드들을 뒤집으ㄹ시오

java
열기

  Note) 실행 결과

 

 

  Ex) practic4 주어진 문자열 배열을 연결 리스트 배열로 관리하는 코드를 작성한다.

    - 각각의 리스트에는 접근이 불가능하므로 해당 위치에 하나씩 객체를 만들어줘야한다.

java
열기

  Note) 실행 결과

 

 

2.6 스택(Stack)

  - 후입 선출구조(LIFO, last in first out / FILO, first in last out)

  ex) 함수 콜 스택, 수식 계산, 인터럽트(갑자기 발생한 일)처리

 

 

2.7 스택(Stack) 문제 풀이

  Ex 1)  ArrayList를 이용한 Stack 구현하기

java
열기

  Note) 실행 결과

 

 

  Ex 2) 배열을 이용한 Stack 구현하기

java
열기

  Note) 실행 결과

 

 

2.7 Stack 문제 풀이

  Ex 1) 문자열 뒤집기

 

  MySol)

    - for문(char c :  .. ) 대신에 for(String s : str.split("")) 을 쓸 수도 있다.

java
열기

  Note) 실행 결과

 

 

  Ex 2) 괄호 짝 검사

java
열기

  Note) 실행 결과

 

 

  Ex 3) 후위 표기법 연산

java
열기

  Note) 실행 결과

 

 

  Ex 4) 두 문자열 비교, '#'은 backspace로 바로 이전의 문자를 삭제하는 기능이라고 가정한다.

java
열기

  Note) 실행 결과

 

 

2.8 Queue

  - 선입선출(FIFO, first in first out) 

    ex) 프린터 출력 대기열, BFS

  - 데이터 추가(Enqueue), 꺼내기(Dequeue), 큐 공간 확인 동작으로 이뤄진다.

  - Queue는 Stack과 다르게 인터페이스로 구현되어 있기 때문에 객체를 만들 수 없다.

    -> <다형성>

    -> Queue queuue = new LinkedList();를 이용한다.

 

  Ex 1) ArrayList를 이용해서 Queue 구현하기

    - list.remove(0); 지우려는 데이터의 index를 매개변수로 넣는다.

java
열기

  Note) 실행 결과

 

 

  Ex 2) 배열을 이용해서 Circle Queue 구현하기 - 원형 큐

    - 인덱스 0에는 값을 비워둔다.

    - 원형 큐 관리를 위해 배열의 사이즈는  매개변수로 들어온 값에 1을 더한 값으로 정한다.(5 + 1)

   - enqueue를 할 때는 rear값만 변하고 front값은 변하지 않는다. 

java
열기

  Note) 실행 결과

 

 

2.9 Queue 문제 풀이

  Ex 1) 카드 섞기  - 1 ~ N 까지 번호로 구성된 N개의 카드가 있다. (1번: 위, N번: 가장 아래)

    (1) 가장 위의 카드는 버린다.  

    (2) 그 다음 위의 카드는 가장아래에 다시 넣는다. 카드가 한 장 남을 때까지 반복했을 때, 마지막 카드 구하기

    - intstream을 이용해서 하나씩 큐에 넣을 수 있다. 

    - 반환할 때, poll()이 아닌 remove()를 쓸 수도 있따.

IntStream.range(1, N + 1).forEach(x -> queue.add(x));
java
열기

  Note) 실행 결과

 

 

  Ex 2) 요세푸스 순열 - Josephus Permutation

  MySol)

java
열기

  Note) 실행 결과

 

 

 

 

2.10 Deque(Doubly ended Queue, 데크, 디큐)

  Def)  Deque: 양쪽에서 삽입과 삭제가 모두 가능한 자료 구조 (Stack + Queue)

    - 일부 기능을 제한하여 용도에 맞게 변형 가능

    - add / remove -> 공간이 부족하거나 제거할 데이터가 없을 때, 예외를 발생시킨다.

    - offer / poll -> 공간이 부족하거나 제거할 데이터가 없을 때, null이나  false를 반환시킨다.

 

    1) Scroll(입력 제한 데트): 한 쪽(rear 또는 front)의 입력을 제한한 데크

    2) Shelf(출력 제한 데크): 한 쪽의 출력을 제한한 데크

 

 

 

 

  Ex) Java Deque

java
열기

  Note) 실행 결과

 

 

  Ex 1) ArrayList를 이용한 Deque

java
열기

  Note) 실행 결과

 

 

  Ex 2)  배열을 이용한 Deque

java
열기

 

  Note) 실행 결과

 

 

2.11 Deque 문제 풀이

  Ex 1)  데이터 재정렬

java
열기

  Note) 실행 결과

 

  Ex 2) 팰린드롬

    - deque를 이용한 팰린드롬

    - remove가 아닌 pollFirst()와 pollLast()를 이용해야 데이터가 비어 있을 때, null을 반환한다.

java
열기

  Note) 실행 결과

 

 

  Ex 3)  중간에 데이터 추가하기

java
열기

 

  Note) 실행 결과

 

 

  Ex 4)  데크 리사이즈

java
열기

 

  Note) 실행 결과

 

 

2.12 해시 테이블(Hash Table)

  Def) Hash Table(해시 맵, 해시 표): 키와 값을 대응시켜 저장하는 데이터 구조, 키를 통해 데이터에 빠르게 접근 가능하다

    - 해싱: 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

    - 키(key): 해시 테이블 접근을 위한 입력 값

    - 해시 함수:  키를 해시 값으로 매핑하는 연산

    - 해시 값: 해시 테이블의 인덱스

    - 해시 테이블: 키와 값을 연관시켜 저장하는 데이터 구조

 

    Note) 해시 충돌: 해시테이블의 같으 ㄴ공간에 서로 다른 값을 저자하려는 경우

    - 서로 다은 키의 해시 함수를 통해 해시 값이 동일한 경우

    -  해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다.

 

    1) 개방 주소법(Open Address): 충돌 시 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장한다.

      -> hash와 value가 1:1 관계를 유지한다.

      -> 비어 있는 공간 탐색 방법에 따른 분류(선형 탐사법, 제곱 탐사법, 이중 해싱)

 

      (1) 선형 탐사법(Linear Probing): 빈 공간을 순차적으로 탐사하는 방법

        - 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사

        - 일차 군집화 문제 발생 (반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생한다.)

  

      (2) 제곱 탐사법(Quarratic Probing): 빈 공간을 n제곱만큼의 간견을 두고 탐사하는 방법

        - 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사한다.

        - 일차 군집화 문제 일부 보완

        - 이차 군집화 문제 발생 가능성

 

      (3) 이중 해싱(Double Hashing): 해시 함수를 이중으로 사용

        - 해시 함수1(최초 해시를 구할 때, 사용) / 해시함수2(충돌 발생 시, 탐사 이동 간격을 구할 때 사용한다.) 

        - 선형탐사, 제곱탐사에 비해 데이터가 골고루 분포된다. 

 

    2) 분리 연결법(Seperate Chaining): 해시 테이블을 연결 리스트로 구성한다.

        - 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용해서 해당 테이블에 데이터를 연결한다.

 

 

  Ex)  hash table

java
열기

  Note) 실행 결과

 

 

  Ex 1) 해시테이블을 배열로 구현하기

java
열기

  Note) 실행 결과

    - 8을 7로   나눈 나머지는  1이기 때문에

    - setvalue(8, 6)은 hash 1에 6을 넣는 것과 같은 충돌이 일어난다. 데이터가 바뀐다.

 

 

  Ex 2) 선형 탐사법

java
열기

  Note) 실행 결과

 

 

  Ex 3) 해시 충돌 해결 - 개방 주소법(제곱 탐사법)

java
열기

  Note) 실행 결과

 

 

  Ex 4) 해시 충돌 해결 - 개방 주소법 (이중 해싱)

java
열기

  Note) 실행 결과

 

 

  Ex 5) 해시 충돌 해결 - 분리 연결법

java
열기

  Note) 실행 결과

 

 

2.13 hash table 문제 풀이

 

  Ex 1) Hash Table

java
열기

  Note) 실행 결과

 

 

  Ex 2) Hash Table 

    - 정수형 배열 numbers가 주어졌을 때, target을 구할 수 있는지 확인하는 프로그램 작성하라

    - target에서 뺀 값을 key로 넣는다. (나중에 if문에서 containsKey로 비교하기 위해)

java
열기

  Note) 실행 결과

 

 

  Ex 3) HashTable과 HashMap 비교하기

    - 공통점: 둘 다 map인터페이스를 구현한 것이다.

    - 차이점: key에 null 사용 여부(hashmap: 가능, hashtable: 불가능)

      -> Thread safe(스레드 세이프): hashtable(o) - 멀티 스레드 환경에서 우수하다, hashmap(x) - 싱글스레드 환경에서 우수하다 .

      Def) Thread safe(스레드 세이프): 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수 혹은 객체가 여러 스레드로부터 동시에 접근이 이뤄져도 프로그램의 실행에 문제가 없다.

      ex) SyncronizedMap, ConcurrentHashMap -> 스레드 세이프한 HashMap으로 두 가지의 장점을 모두 가진다.

java
열기

  Note) 실행 결과

 

 

2.14 선형 자료구조 연습문제 풀이

 

  Ex 1) modification함수를 이용해서 배열 내 데이터 순서를 변경한다. modification 함수를 되돌리는 코드를 작성하라.

java
열기

  Note) 실행 결과

 

 

  Ex 2) 정수로 주어진 M * N 행렬에 대해 행렬의 원소 중에서 0이 있을 경우, 해당 원소가 위치하는 행과 열 전체 데이터를 0으로 작성하라.

 

  Sol)

    - 행렬 값이 0인 데이터에 대해 각 열과 행에 대해 boolean 값(fczero, frzero)를 true로 저장한다.

    - 1행 ~ 마지막 행 , 1열~ 마지막 열을 먼저 for문으로 0으로 바꾸는 작업을 한다.

    - 그 다음 0행, 0열은 firstRowZero/ firstColumnZero 를 이용해서 작업하면 된다. 

java
열기

 

  MySol) 만약 0이 같은 행에 두 개 있거나 같은 열에 두 개 넘게 있는 경우에는 오류가 생길지도 모르겠다.. 확인할 부분

java
열기

 

  Note) 실행 결과

 

 

  Ex 3) 1~N번 까지 N개의 풍선이 원형으로 놓여 있고 i번 풍선의 오른쪽에는 i + 1번 풍선이 있고 왼쪽에는i -1번 풍선이 있다. 

    - 처음에는 1번 풍선을 터뜨리고 풍선안에 있는 종이를 꺼내서 그 종이에 적힌 값만큼 이동하여 다음 풍선을 터뜨린다. 

    - 이미 터뜨린 풍선은 제외하고 이동한다.

    - 풍선이 터지는 순서대로 인덱스 출력

java
열기

  Note) 실행 결과

 

 

  Ex 4) 괄호 짝 검사, 세 종류의 괄호가 있다.

    - 여는 괄호의 순서에 맞춰 닫는 괄호의 순서도 맞아야한다.

    - 스택 하나만 가지고 풀 수 있다.

    - stack과 map의 성질을 함께 이동한다.

java
열기

  Note) 실행 결과

 

 

  Ex 5) Dummy - 도스게임

java
열기

  Note) 실행 결과

 

 

  Ex 6) 프린터 중요도 인쇄

java
열기

  Note) 실행 결과

 

 

  Ex 7) 스택 수열 만들기

    - 1~n까지의 숫자를 (오름차순으로) 스택에 넣었다가 뽑아 늘어놓음으로써 하나의 수열을 만든다. 

    - 임의의 수열이 주어졌을 때, 스택을 이용해 그 수열을 만들 수 있는지 없는지

    - 원하는 수가 나왔을 때, push를 한 다음에 뺀다.

java
열기

  Note) 실행 결과

 

 

  Ex 8) 베스트 앨범 출시

java
열기

  Note) 실행 결과: 4 1 3 0

 

 

  Ex 9) 완주하지 못한 선수

    - 동명이인 있는 경우가 있다.

java
열기

  Note) 실행 결과

 

 

  Ex 10) 어피치 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

java
열기

  Note) 실행 결과

 

저작자표시

'자료구조와 알고리듬 With Java > [zerobase] Algorithm' 카테고리의 다른 글

Chapter 03. 비선형 자료구조  (0) 2022.06.08
Chapter 01. 기초 수학 [zerobase]  (0) 2022.05.22
[Java 핵심 복습]  (0) 2022.05.13
Part 01. 연습문제 풀이 3 [zerobase]  (0) 2022.05.12
Part 01. 연습문제 풀이 2 [zerobase]  (0) 2022.05.11

'자료구조와 알고리듬 With Java/[zerobase] Algorithm'의 다른글

  • 현재글Chapter 02. 선형 자료구조

관련글

댓글

티스토리툴바