Day 16 복습

swap(스왑) 이란?

두 변수의 값을 서로 바꾸는 것
예: a = 3, b = 7 → swap 후: a = 7, b = 3

스왑하는 방법

a = 3, b = 7
int temp = 3;
a = b; //a = 7
b= a //b = 3

자료구조의 4가지 기본 방법

• 읽기 : 자료 구조 내 특정 위치를 찾아보는 것
• 검색 : 자료 구조 내에서 특정 값을 찾는 것
• 삽입 : 자료 구조에 새로운 값을 추가하는 것
• 삭제 : 자료 구조에서 값을 제거하는 것

배열이란?

컴퓨터 과학에서 기초적인 자료구조 중 하나
배열을 선언하면 컴퓨터는 프로그램이 쓸 수 있는 연속된 빈 셀들의 집합을 할당함
각 셀에는 특정 주소가 있음 (셀로 구성된 거대한 컬렉션이 메모리)

읽기

배열에서의 읽기는 한 번의 단계로 바로 갈 수 있음
각배열에 저장된 내용은 메모리의 시작 주소임 컴퓨터는 메모리 주소에 한번에 갈 수 있음
Ex)
배열의 인덱스는 0부터 시작함 -> 인덱스 0의 메모리 주소는 1010임 -> 인덱스3은 0부터 3슬롯 뒤임 -> 인덱스 3을 찾을려면 1010+3 =1013 주소로 감

검색

배열에서 검색은 인덱스 0부터 시작해서 찾고 있는 값이 발견될때까지 계속됨
먼저 0을 확인 -> 아니면 1 -> 찾을때가지 반복
컴퓨터가 이와같이 한번에 한 셀씩 확인하는 방법을 선형 검색이라고 부름
셀의 갯수가 N개일때 선형검색에 최대 N개의 단계가 필요함

삽입

배열에서 삽입은 어디에 데이터를 삽입하는가에 따라 효율성이 다름
끝에 삽입시 딱 한단계만 필요함 컴퓨터는 배열이 시작되는 주소를 알고 얼마나 많은 원소를 가지고 있는지 알기 때문에
하지만 처음이나 중간에 삽입할 경우 문제 발생
Ex)
5개의 셀에서 3번 위치에 삽입 시 5번을 6번위치 -> 4번을 5번 위치 -> 3번을 4번 위치후 3번위치에 삽입 총 4단계 필요
N개의 원소를 포함하는 배열에서 삽입시 최악의 경우 N+1개의 단계가 걸림

삭제

배열에서 삭제는 특정 인덱스를 제거하는 과정임
Ex)
5개의 원소를 가지고 있는 상황에서 인덱스 2번을 삭제하면 2번 삭제 -> 3번을 2번 위치에 -> 4번을 3번 위치에 옮겨야함
총 3단계가 필요함
N개를 포함하는 배열에서 삭제에 필요한 최대 단계 수는 N개임

집합이란?

중복 값을 허용하지 않는 자료 구조 중복값의 삽입을 절대 허용하지 않음

읽기

배열과 동일함

검색

배열과 동일함

삽입

집합에서의 삽입은 먼저 이 값이 집합에 들어가있는지 확인해야함 - 검색이 우선
Ex)
5개의 인덱스를 가진 집합에서 새로운 인덱스를 삽입할려면 1~5까지의 인덱스를 전부 확인 후 없으면 삽입
N개를 포함하는 집합의 경우 최악의 경우 (맨앞에 삽입 시 다 확인후 다시 다 옮기고 삽입) 2N+1 단계가 필요함

학습목표

1.백준 3문제

• 10811 바구니 뒤집기
• 1546 평균
• 27866 문자와 문자열

2.cs공부

• 누구나 자료구조와 알고리즘 2강
• 연결리스트
• TCP/UDP 기초

3.java

• AutoSaveTest 생성
• Stream체이싱 리펙토링

1.백준 3문제

1.10811 바구니 뒤집기

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 
도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.
바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.
둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)
도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

출력

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

예제 입력 1

5 4
1 2
3 4
1 4
2 2

예제 출력 1

3 4 1 2 5

풀이

package array;
import java.util.Scanner;

public class BOJ_10811_BasketReverse {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int t = 0; t < n; t++) {
            arr[t] = t+1;
        }
        for (int t =0; t < m; t++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            int start = i - 1;
            int end = j - 1;
            while (start < end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                start++;
                end --;
            }
        }
            for(int val :arr){
                System.out.print(val + " ");
            }
        }
    }

배열에서 부분 구간의 원소를 뒤집는 구현력 연습하는 문제/ 인덱스 조작, 구간 swap, 반복문 활용

2.1546 평균

문제

세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M100으로 고쳤다.
예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70100이 되어 71.43점이 된다.
세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다.

출력

첫째 줄에 새로운 평균을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-2 이하이면 정답이다.

예제 입력 1

3
40 80 60

예제 출력 1

75.0

예제 입력 2

3
10 20 30

예제 출력 2

66.666667

예제 입력 3

4
1 100 100 100

예제 출력 3

75.25

예제 입력 4

5
1 2 4 8 16

예제 출력 4

38.75

예제 입력 5

2
3 10

예제 출력 5

65.0

예제 입력 6

4
10 20 0 100

예제 출력 6

32.5

예제 입력 7

1
50

예제 출력 7

100.0

예제 입력 8

9
10 20 30 40 50 60 70 80 90

예제 출력 8

55.55555555555556

풀이

package array;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class BOJ_1546_AverageAdjust {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        double [] score = new double[n];
        double max = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            score[i] = Double.parseDouble(st.nextToken());
            if(max<score[i]){
                max = score[i];
            }
        }
        double sum = 0;
        for(int i=0;i<n;i++){
            sum+=(score[i]/max)*100.0;
        }
        System.out.println(sum/n);
    }
}

수치 데이터를 정규화한 후 평균을 계산 최대값 찾기 → 새로운 점수 계산 → 평균 구하기

3.문자와 문자열

문제

단어 S와 정수 i가 주어졌을 때, S의 i번째 글자를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 
S가 주어진다. 단어의 길이는 최대 1000이다.
둘째 줄에 정수 i주어진다. (1≤i≤S)

출력 

S의 i번째 글자를 출력한다.

예제 입력 1

Sprout
3

예제 출력 1

r

예제 입력 2

shiftpsh
6

예제 출력 2

p

예제 입력 3

Baekjoon
4

예제 출력 3

k

풀이

package string;
import java.util.Scanner;

public class BOJ_27866_StringChar {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = sc.nextInt();
        System.out.println(s.charAt(n-1));
    }
}

charAt()이란?

Java에서 문자열에서 특정 위치의 문자 하나를 꺼내올 때 사용하는 메서드

String s = "hello";
char c = s.charAt(1); // 'e

문자열에서 원하는 위치의 문자 접근 인덱스 기반 접근 (charAt),문자열 입력 처리

2.Cs공부

1.누구나 자료구조와 알고리즘 2강 알고리즘이 중요한 까닭

자료구조를 결정했더라도 코드의 효율성에 영향을 미칠 수 있는 중요한 요인이 있음
즉 사용할 알고리즘을 적절하게 선택해야함

알고리즘이란?

단순히 문제를 해결하는 절차일 뿐이다
컴퓨팅 관점에서는 특정 연산을 풀어나가는 절차를 뜻함

정렬된 배열이란?

값이 항상 순서대로 있어야 함
값을 추가 할때만다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지함
정렬된 배열에 삽입을 때는 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 위치를 정해야함
삽입에 있어 정렬된 배열이 배열보다 덜 효율적임 그러나 정렬된 배열은 검색 연산에 있어 강함

정렬된 배열의 검색

[17,3,75,202,80]이라는 배열이 있다는 가정에 일반 배열에서는 22를 찾기 위해서는 끝까지 다 검색해야함
그러나 정렬된 배열에서는 [3,17,75,80,202] 75에 도달하면 22가 없다는 걸 알기 때문에 검색을 종료함
하지만 이는 선형 검색 알고리즘일 경우의 차이이고 이진검색이라는 알고리즘을 사용시는 훨씬 빠르다

이진검색이란?

1~100사이의 숫자 맞추기를 한다고 가정했을때 가운데 값을 골라 높은지 낮은지 확인후 절반을 제거함
그걸 반복해서 원하는 숫자를 찾는 알고리즘

이진검색vs선형 검색

작은크기의 정렬된 배열의 경우 이진알고리즘이 선형보다 크게 나은점은 없으나 배열이 커질경우는 큰 차이가 생김
선형 검색은 원소의 수만큼 단계가 필요하나 이진검색은 배열의 원소수가 2배가 될때마다 1단계만이 늘어난다

위와 같이 사용자가 선택하는 알고리즘이 코드의 속도에 크게 영향을 줄 수 있다

2.LinkedList

연결된 리스트란?

각 요소가 데이터 + 다음 노드의 주소를 가지고 있는 구조
메모리가 비연속적이고 , 크기가 유동적임
삽입과 삭제가 빠르나 인덱스 접근이 느리고 구현이 복잡함

구조예시

[10 | 주소] → [20 | 주소] → [30 | null]

Java예시

LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");

3. 네트워크 TCP/UDP

TCP란?

Transmission Control Protocol
연결을지향하고 신뢰성을 보장한다 순서대로 도착함
데이터 유실없으나재전송해야하는속도느림
웹(HTTP),이메일(SMTP),파일정송(FTP)등에서 사용

3-Way Handshake란?

TCP통신을 시작할때 신뢰성있는 연결을 만들기위해
클라이언트와 서버가 3번의 메세지를 주고받는 과정
클라이언트 -> 서버 SYN(연결요청)
서버-> 클라이언트 SYN+ACK (연결 요청 +수신확인)
클라이언트 -> 서버 ACK (수신확인)
연결 완료

4-Way Handshake란?

TCP연결을 종료할때 클라이언트와 서버가 4번 메세지를 주고받는 과정
클라이언트 -> 서버 FIN (나가는 신호)
서버 ->클라이언트 ACK (수신확인)
서버 -> 클라이언트 FIN (나가는 신호)
클라이언트 -> 서버 ACK(수신확인)
연결 종료

UDP란?

User Datagram Protocol
비연결을지향하고 신뢰성이 없음 순서가 섞일 수 있음
데이터 유실이 일어날 수 있으나 속도가 빠름
스트리밍, 게임, 실시간 채팅, DNS 등에서 사용

3.java

1.AutoSave Test 생성

Add,remove,markdone시 자동 저장 되는지 확인

test시 실제 기능과 충돌하지 않도록 TodoService 파일명 분리 추가

TestAutosave 코드

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.time.LocalDate;
import java.util.ArrayList;
import java.util.List;
import java.io.File;

import static org.junit.jupiter.api.Assertions.*;
public class AutoSaveTest {
    private static final String FILENAME = "todosTest.json";
    private TodoService service;
    private List<Todo> todos;

    @BeforeEach
    void setup() {
        todos = new ArrayList<>();
        service = new TodoService(todos,FILENAME);
        new File(FILENAME).delete();
    }
    @Test
    void testAddTodoAutoSave(){
        service.add("Test","테스트", LocalDate.now().toString());
        List<Todo> loaded = TodoManager.loadTodosFromFile(FILENAME);
        assertEquals(1,loaded.size());
    }

    @Test
    void testRemoveTodoAutoSave(){
        service.add("Test","테스트", LocalDate.now().toString());
        service.remove(1);
        assertEquals(0,TodoManager.loadTodosFromFile(FILENAME).size());
    }
    @Test
    void testMarkDoneTodoAutoSave(){
        service.add("Test","테스트", LocalDate.now().toString());
        service.markDone(1);
        List<Todo> loaded = TodoManager.loadTodosFromFile(FILENAME);
        assertEquals(1,loaded.size());
        assertTrue(loaded.get(0).isDone());
    }
}

TodoService 코드 추가 및 수정

public class TodoService {
    private List<Todo> todos;
    private final String filename;
    private Stack<Todo> deleteTodos = new Stack<>();
    private void autoSave(){
        TodoManager.saveTodosToFile(todos, filename);
    }
    public TodoService(List<Todo> todos,String filename) {
        this.todos = todos;
        this.filename = filename;
    }

Main 코드 수정

TodoService service = new TodoService(todos,"todos.json");

2.TodoService Stream체이싱 사용 리펙토링

Print all 리팩토링

For 문을 intStream을 사용해서 스트림 체이싱으로 리펙토링함

메서드	설명
IntStream.range(a, b)	a부터 b-1까지
IntStream.rangeClosed(a, b)	a부터 b까지 포함
Stream.of(...)	값들을 스트림으로
Arrays.stream(arr)	배열 → 스트림

예시코드

for (int i = 0; i < todos.size(); i++) {
    System.out.println((i + 1) + ". " + todos.get(i));
}
——————————————————————————————
IntStream.range(0, todos.size())
    .forEach(i -> System.out.println((i + 1) + ". " + todos.get(i)));

리펙토링전

public void printAll() {
    if (todos.isEmpty()) {
        System.out.println("오늘 할 일이 없습니다.");
    } else {
    for (int i = 0; i < todos.size(); i++) {
    System.out.println((i + 1) + ". " + todos.get(i));
}

후

public void printAll() {
    if (todos.isEmpty()) {
        System.out.println("오늘 할 일이 없습니다.");
    } else {
        IntStream.range(0, todos.size())
                .forEach(i -> System.out.println((i+1)+"."+todos.get(i)));
    }
}

public void printIncomplete() {
    boolean hasIncomplete = false;
    for (int i = 0; i < todos.size(); i++) {
        if (!todos.get(i).isDone()) {
            System.out.println((i + 1) + ". " + todos.get(i));
            hasIncomplete = true;
        }
    }
    if (!hasIncomplete) {
        System.out.println("✅ 완료할 일이 없습니다.");
    }
}

printIncomplete() 리팩토링

.boxed()

IntStream을 일반 Stream로 변환
이유: 리스트로 collect하려면 Integer 객체형이 필요하기 때문
.collect(Collectors.toList()) 남은 인덱스를 리스트로 수집

항목	기본형 (primitive)	객체형 (wrapper/object)
예시	int, double, char	Integer, Double, Character
저장 방식	값 자체 저장	참조(reference) 저장
null 가능 여부	❌ 불가능	✅ 가능
메모리 위치	스택(stack)	힙(heap)
Stream 사용	❌ 직접 못 씀 (IntStream 따로 사용)	✅ Stream<T>에서 바로 사용 가능
컬렉션 저장	❌ 불가 (List<int> 불가)	✅ 가능 (List<Integer> 가능)

변경전

public void printIncomplete() {
    boolean hasIncomplete = false;
    for (int i = 0; i < todos.size(); i++) {
        if (!todos.get(i).isDone()) {
            System.out.println((i + 1) + ". " + todos.get(i));
            hasIncomplete = true;
        }
    }
    if (!hasIncomplete) {
        System.out.println("✅ 완료할 일이 없습니다.");
    }
}

변경 후

public void printIncomplete() {
    boolean hasIncomplete = false;
    List<Integer> incompleteTodos = IntStream.range(0, todos.size())
            .filter(i -> !todos.get(i).isDone())
            .boxed()
            .collect(Collectors.toList());
    if (incompleteTodos.isEmpty()) {
        System.out.println("✅ 완료할 일이 없습니다.");
    }else {
        incompleteTodos.forEach(i -> System.out.println((i + 1) + "." + todos.get(i)));
    }
}

Remove 메소드 출력 for문 리팩토링

public void remove(int displayIndex) {
    int realIndex = displayIndex - 1;
    if (isValidIndex(realIndex)) {
        IntStream.range(0, todos.size())
                .forEach(i -> System.out.println((i+1)+"."+todos.get(i)));
        deleteTodos.push(todos.get(realIndex));
        todos.remove(realIndex);
        autoSave();
        System.out.println("✅ 삭제되었습니다.");
    } else {
        System.out.println("❌ 잘못된 번호입니다.");
    }
}

리뷰

오늘은 백준 문제도 풀고 cs공부도 하고 java공부도 한 정말 멋진 하루였습니다
문제를 풀면서 알고리즘을 공부하고있는데 알고리즘을 공부하고 문제를 풀어야하는건지
닭이 먼전지 달걀이 먼저인지 헷갈리기 시작했지만 일단 해보겠습니다
배열과 문자열 그리고 swap에 대해서 알게 되었고
cs공부를 하면서 정렬된 배열 선형검색과 이진검색의 차이점
LinkedList TCP와 UDP에 대해 알게되었습니다
뭔가 드디어 갈피가 잡히는 느낌…! 이게 퍼즐 맞추는 느낌일까요
java보니까 거의 9일만에 했더라고요…
전에 autoSave 메소드를 만들어서 그걸 테스트하는 클래스를 만들었고
최근에 공부한 Stream체이싱을 이용해서 TodoService리팩토링도 했습니다
음 저 자신이 아주 멋있네요 내일도 힘내야겠습니다!