Java Persistence API의 약자. 자바에서 객체(클래스)와 DB 테이블을 연결해주는 표준 인터페이스(스펙). 즉, SQL을 직접 안 쓰고도, 자바 객체로 DB 작업을 할 수 있게 해줘. JPA 자체는 “규격”일 뿐이고, 실제 동작은 구현체가 처리.

Hibernate란?

JPA 구현체 중 하나 (가장 많이 씀). JPA가 “이렇게 만들어라”라고 규칙만 정해주면, Hibernate가 실제 SQL을 만들어서 DB랑 통신함. 스프링부트에서 spring-boot-starter-data-jpa 쓰면 기본 구현체가 바로 Hibernate.

JPQL 이란?

Java Persistence Query Language JPA에서 쓰는 “객체지향 쿼리 언어” SQL처럼 생겼지만 테이블/컬럼이 아니라 엔티티/필드 기준으로 작성 👉 즉,

SQL: SELECT * FROM board WHERE user_id = 'hong';
JPQL: SELECT b FROM Board b WHERE b.userId = 'hong'

JPQL vs SQL 차이

구분 SQL JPQL user_id b.userId (엔티티 필드) 반환 ResultSet (Row) 엔티티 객체 (Board) 실행 DB 직접 실행 Hibernate가 SQL로 변환해서 실행 jpa 환경을 위한 라이브러리

pom.xml에 추가

 <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-jpa</artifactId>
  </dependency>

JPA 기본

• application.properties에 저장

  spring.jpa.open-in-view=false
  spring.jpa.show-sql=true
  spring.jpa.properties.hibernate.format_sql=true

스키마 자동 생성 전략

spring.jpa.hibernate.ddl-auto=validate

(교육용으로는 update가 편함; 운영은 none 권장)

none: 아무 것도 안 함 (운영 기본)

validate: 엔티티와 DB 스키마 일치 여부만 검사, 불일치면 에러

update: 가능한 범위에서 스키마 갱신

create: 매 기동마다 드랍 후 생성

create-drop: 기동 시 생성, 종료 시 드랍(테스트용)
​
JpaRepository<Entity, id> 기본제공 메소드


findAll() → 전체 목록

findById() → 단건 조회

save() → insert/update 겸용

deleteById() → 삭제

count() → 전체 행 수

findAll(Pageable) → 페이징 조회

실제 테이블과 연결되는 Entity 구현

package com.study.project.jpa;

import java.sql.Date;

import jakarta.persistence.Column;
import jakarta.persistence.Entity;
import jakarta.persistence.GeneratedValue;
import jakarta.persistence.GenerationType;
import jakarta.persistence.Id;
import jakarta.persistence.Table;

@Entity
@Table(name="board")
public class JpaBoardEntity {


    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    @Column(name = "board_num")
    private Integer boardNum;

    @Column(name = "user_id", nullable = false)
    private String userId;

    @Column(name = "user_name")
    private String userName;

    @Column(name = "board_subject")
    private String boardSubject;

    @Column(name = "board_content")
    private String boardContent;

    @Column(name = "reg_date")
    private Date regDate;

    @Column(name = "upt_date")
    private Date uptDate;

    @Column(name = "view_cnt")
    private Integer viewCnt;

    // === getter / setter ===
    public Integer getBoardNum() { return boardNum; }
    public void setBoardNum(Integer boardNum) { this.boardNum = boardNum; }

    public String getUserId() { return userId; }
    public void setUserId(String userId) { this.userId = userId; }

    public String getUserName() { return userName; }
    public void setUserName(String userName) { this.userName = userName; }

    public String getBoardSubject() { return boardSubject; }
    public void setBoardSubject(String boardSubject) { this.boardSubject = boardSubject; }

    public String getBoardContent() { return boardContent; }
    public void setBoardContent(String boardContent) { this.boardContent = boardContent; }

    public Date getRegDate() { return regDate; }
    public void setRegDate(Date regDate) { this.regDate = regDate; }

    public Date getUptDate() { return uptDate; }
    public void setUptDate(Date uptDate) { this.uptDate = uptDate; }

    public Integer getViewCnt() { return viewCnt; }
    public void setViewCnt(Integer viewCnt) { this.viewCnt = viewCnt; }
}

1. SRP 단일 책임 원칙

• 한 클래스는 하나의 책임만 가져야 한다.
• 구현 객체를 생성하고 연결하는 책임은 AppConfig가 담당, 클라이언트 객체는 실행하는 책임만 담당

2. DIP 의존 관계 역전 원칙

• 추상화에 의존해야하지 구체화에 의존하면 안된다.
• 의존성 주입은 이 원칙을 따르는 방법 중 하나
• 클라이언트 코드는 인터페이스만으로는 아무것도 실행할 수 없다. AppConfig가 객체 인스턴스를 클라이언트 코드 대신 생성해서 클라이언트 코드에 의존관계를 주입했다.

3. OCP

• 소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어야 한다.
• AppConfig가 클라이언트 코드에 주입하므로 클라이언트 코드는 변경하지 않아도 됨

📍 IoC, DI, 그리고 컨테이너

제어의 역전 Ioc(Inversion of Control)

• AppConfig 등장 후 구현 객체는 자신의 로직을 실행하는 역할만 담당한다. 프로그램에 대한 제어 흐름에 대한 권한은 모두 AppConfig가 가지고 있다. 이렇듯 프로그램의 제어 흐름을 직접 제어하는 것이 아니라 외부에서 관리하는 것을 제어의 역전이라고 한다.

프레임워크 vs 라이브러리

• 프레임워크가 내가 작성한 코드 제어하고, 대신 실행하면 프레임워크(JUnit)
• 내가 작성한 코드가 직접 제어의 흐름을 담당하면 라이브러리

의존 관계 주입 DI(Dependency Injection)

• 인터페이스에만 의존하여 실제 어떤 구현 객체가 사용될지 모른다.
• 의존관계는 정적인 클래스 의존 관계와, 실행 시점에 결정되는 동적인 객체(인스턴스) 의존관계 둘을 분리해서 생각해야한다.
• 정적인 클래스 의존관계를 변경하지 않고, 동적인 객체 인스턴스 의존관계를 쉽게 변경할 수 있다.

정적인 클래스 의존관계 : import 코드만 보고도 쉽게 알 수 있다. 실행하지 않아도 분석할 수 있다. 그러나 이 의존관계로만으로 실제 어떤 객체가 주입될지 알 수 없다.

동적인 객체 인스턴스 의존관계 : 애플리케이션 실행 시점에 실제 생성된 객체 인스턴스의 참조가 연결된 의존 관계다.

Ioc 컨테이너, DI 컨테이너

• AppConfig 처럼 객체를 생성하고 관리하면서 의존관계를 연결해 주는 것을 IoC 컨테이너 혹은 DI 컨테이너라고 한다.
• 의존관계 주입에 초점을 맞추어 최근에는 주로 DI 컨테이너라 한다.

• 스프링데이터 : crud 편하게 해주는 거
• 스프링 세션 : 세션 기능 편리하게 해주는 거
• 스프링 시큐리티 : 보안
• 스프링 Rest Docs : api 편하게 해주는 거
• 스프링 배치 : 배치처리에 특화된 기술
• 스프링 클라우드 : 클라우드 특화

스프링은 좋은 객체 지향 애플리케이션을 개발할 수 있게 도와주는 프레임워크

📍 좋은 객체 지향 프로그래밍이란?

객체 지향 특징

• 추상화
• 캡슐화
• 상속
• 다형성

객체 지향 프로그래밍이란?

객체들의 모임, 각각의 객체는 메세지를 주고 받고 데이터를 처리할 수 있다.

다형성 Polymorphism

• 자동차가 바뀌어도 운전자에 영향을 안 준다.
• 자동차의 인터페이스에 따라 다 구현했기 때문에, 운전자는 자동차 인터페이스에 대해서만 의존하면 된다.
• 클라이언트에 영향을 주지 않고 새로운 기능을 제공할 수 있다.
• 새로운 자동차가 나오도 클라이언트는 바꿀 필요가 없다.

클라이언트를 변경하지 않고 서버의 구현 기능을 유연하게 변경할 수 있는 게 다형성의 본질

정리

• 인터페이스를 안정적으로, 가장 변화가 없게 설계하는 게 가장 중요함.
• 스프링은 다형성을 극대화해서 이용할 수 있게 도와줌.
• 제어의 역전(IoC), 의존관계 주입(DI)도 다형성을 활용할 것.

📍 좋은 객체 지향 설계의 5가지 원칙(SOLID)

1. SRP : 단일 책임 원칙 (single responsibility principle) 범위를 적절하게 적용하는 게 객체 지향 개발의 묘미

2. OCP 개방-폐쇄 원칙 (Open/closed principle) 소프트웨어 요소는 확장에는 열려있으나 변경에는 닫혀있다. 인터페이스를 구현한 새로운 클래스를 하나 만들어서 새로운 기능을 구현 문제점 : 구현 객체를 변경하려면 클라이언트 변경해야한다. 분명 다형성을 사용했지만 OCP 원칙을 지킬 수 없다. => 이걸 지키기 위해 DI 컨테이너 이런 게 필요하다.

3. LSP 리스코프 치환 원칙 (Liskov substitution principle) 자동차 인터페이스가 있으면 악셀을 구현해야 한다. 악셀을 밟아도 뒤로 가는 차도 만들 수 있다. 컴파일이 되더라도 액셀이 앞으로 간다는 규약을 안지키면 안되다. 규약을 지키자!

4. ISP 인터페이스 분리 원칙 (Interface segregation principle) 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다 정비 인터페이스 자체가 변해도 운전자 클라이언트에 영향을 주지 않음

5. DIP 의존관계 역전 원칙 (Dependency inversion principle) 역할에 의존해야지, 구현에 의존하면 안된다. 대본에 의존해야지, 담당 배우에 의존하면 안된다. 자동차 기능에 의존해야지, k3를 많이 아는 건 중요하지 않다. 문제점 : 인터페이스, 구현 클래스 둘다 의존하게 된다.

정리

• 다형성만으로 OCP, DIP를 지킬 수 없다. (스프링 프레임워크로 해결..)
• 인터페이스를 무분별하게 남발하면 추상화라는 비용이 발생한다.
• 기능을 확장할 가능성이 없으면 구현 클래스로 쓰고, 향후에 리팩터링해서 인터페이스랑 구현해도 된다. 근데 미래에 확장 가능성이 있으면 처음부터 도입하는 게 중요하다.

🔎 알고리즘 개요

에라토스테네스의 체는 다음과 같은 단계로 작동합니다:

초기화:

2부터 원하는 숫자 범위의 최대값까지 모든 숫자를 나열합니다. 소수 판별을 위한 배열을 준비하고, 2부터 시작해 해당 배열에 모든 숫자를 "소수"로 가정하여 표시합니다.

소수 판별:

가장 작은 소수인 2부터 시작합니다. 2의 배수는 모두 소수가 아니므로 제외합니다. (2는 소수이므로 남겨둡니다.) 다음으로, 남아 있는 가장 작은 숫자를 찾고 그 숫자의 배수들을 모두 제거합니다. 이 과정을 나열된 숫자 중 남은 가장 작은 수에 대해 반복합니다. 해당 숫자가 이미 제거되었다면, 그 다음 숫자로 넘어갑니다. 최대값의 제곱근까지 이 과정을 반복합니다.

결과:

남아 있는 숫자는 모두 소수입니다.

예제

예를 들어, 1부터 30까지의 숫자에서 소수를 찾는 과정은 다음과 같습니다:

2부터 시작하여 2의 배수(4, 6, 8, 10, ..., 30)를 모두 지웁니다. 남은 숫자 중 3은 소수이므로, 3의 배수(9, 12, 15, ..., 30)를 모두 지웁니다. 4는 이미 지워졌으므로, 5를 확인합니다. 5는 소수이므로, 5의 배수(10, 15, 20, ..., 30)를 모두 지웁니다. 이 과정을 반복하여 남아 있는 숫자들(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)이 소수가 됩니다.

장점

효율적: 에라토스테네스의 체는 단순하지만 매우 효율적입니다. 주어진 범위 내의 모든 소수를 찾는 데 걸리는 시간 복잡도는 nlogn입니다. 직관적: 알고리즘의 작동 방식이 직관적이고 이해하기 쉽습니다.

단점

메모리 사용: 숫자 범위가 커질수록 메모리 사용량도 증가합니다. 매우 큰 숫자 범위에서는 메모리 최적화가 필요할 수 있습니다. 에라토스테네스의 체는 소수를 빠르고 효율적으로 찾는 방법으로, 특히 컴퓨터 과학과 수학에서 널리 사용됩니다.

💻 에라토스테네스의 체 Java 구현

import java.util.Arrays;

public class SieveOfEratosthenes {
    public static void main(String[] args) {
        int n = 30;  // 1부터 30까지의 소수를 찾기
        boolean[] isPrime = new boolean[n + 1];

        // 모든 숫자를 소수로 가정하고 true로 초기화
        Arrays.fill(isPrime, true);

        // 0과 1은 소수가 아니므로 false로 설정
        isPrime[0] = false;
        isPrime[1] = false;

        // 2부터 시작하여 제곱근 이하까지 반복
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // i의 배수들을 모두 소수가 아니라고 표시
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 소수 출력
        System.out.println("소수 목록:");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

💡 설명

초기화:

boolean[] isPrime = new boolean[n + 1];는 숫자 0부터 n까지의 소수 여부를 저장하는 배열입니다. 인덱스가 숫자에 해당하고, 값이 true면 그 숫자가 소수라고 가정합니다. Arrays.fill(isPrime, true);를 사용하여 모든 숫자를 처음에는 소수로 간주합니다. isPrime[0]과 isPrime[1]은 소수가 아니므로 false로 설정합니다.

소수 판별:

for (int i = 2; i * i <= n; i++)에서, 2부터 시작하여 n의 제곱근까지 반복합니다. if (isPrime[i])를 통해 현재 숫자가 소수인지 확인하고, 소수라면 그 숫자의 배수들을 모두 false로 설정합니다.

결과 출력:

마지막으로, 소수로 남은 숫자들을 출력합니다. 실행 결과 위 코드가 실행되면, 1부터 30까지의 소수가 출력됩니다:

소수 목록: 2 3 5 7 11 13 17 19 23 29

이 코드는 원하는 범위 내에서 소수를 빠르고 효율적으로 찾을 수 있는 방법을 보여줍니다. n 값을 변경하여 다른 범위의 소수를 찾을 수도 있습니다.

자료 구조에서는 데이터를 어떻게 구축할지 고민하고, 알고리즘에서는 자료구조에서 어떤 순서와 방식으로 탐색할지 고민해야 한다.

그래프 구현 방식

• 인접 행렬 adjacency matrix : 노드에 비해 간선수가 적은 희소 그래프에 쓰임. 시간 복잡도가 O(1)로 좋지만 노드가 모두 연결된 경우 NXN 크기의 인접행렬 필요
• 인접 리스트 adjacency list : 정점에 연결된 간선의 정보를 빠르게 알 수 있음. 시간 복잡도 O(N), 공간 복잡도는 O(E+V)로 인접행렬보다 이득. 다만 연결된 간선을 전부 확인해야해서 느림 -> 그래도 더 많이 씀.

그래프에서 경로를 찾는 두 가지 방법

• 깊이 우선 탐색 : 깊게 탐색 후 되돌아오는 특성이 있음. ex) 모든 가능한 해를 찾는 백트래킹 알고리즘, 그래프의 사이클

• 최단 경로 아니면 깊이 우선 탐색 고려하기!

• 너비 우선 탐색 : 가중치가 없는 그래프에서 최단 경로를 보장. ex) 미로찾기에서 최단경로 찾기, 네트워크 분석

📌 깊이 우선 탐색

방식1

1. 스택이 비었는지 확인. 스택이 비었다는 건 모드 노드를 방문했다는 듯으로 탐색 종료
2. 스택에서 노드를 pop합니다.
3. pop한 노드의 방문 여부 확인. 방문하지 않았다면 방문 처리
4. 방문한 노드와 인전한 모든 노드 확인. 이중 방문하지 않은 노드를 스택에 push. 이때 오름차순을 고려한다면 역순으로 push해야함

   고려사항

5. 가장 깊은 노드까지 방문한 후
6. 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음
7. 해당 노드에서 방문할 노드가 있는지 확인한다.

   방식2 : 재귀함수 - 시스템 스택에 함수 쌓기

📌 너비 우선 탐색

방식

1. 큐가 비었는지 확인. 큐가 비었다면 모든 노드를 확인했다는 의미로 탐색을 종료
2. 큐에서 노드를 poll 한다
3. poll한 노드와 인접한 모든 노드를 확인하고 그중 아직 방문하지 않은 노드를 큐에 add하며 방문처리

   고려사항

4. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 한다
5. 이미 방문한 노드인지 확인할 수 있어야 한다

방문처리시점 차이

• 깊이 우선 탐색 : stack은 다음에 방문할 인접한 노드를 push. pop하며 방문처리
• 너비 우선 탐색 : 큐에 add하며 방문 처리

📍 이진 탐색의 개념

이진 탐색은 정렬된 배열에서 원하는 값을 찾기 위해 배열의 중간 요소와 비교하면서 탐색 범위를 좁혀나가는 방법입니다. 탐색할 값이 중간 요소보다 작으면 왼쪽 반을, 크면 오른쪽 반을 탐색합니다. 이 과정을 반복하면 결국 원하는 값을 찾거나 배열에 값이 없음을 확인할 수 있습니다.

📍 이진 탐색의 동작 과정

초기화:

1. 배열의 시작 인덱스를 left에, 끝 인덱스를 right에 저장합니다.

반복:

1. left가 right보다 작거나 같은 동안 반복합니다.
2. 중간 인덱스 mid를 계산합니다: mid = (left + right) / 2
3. 배열의 중간 요소와 탐색할 값을 비교합니다.
4. 중간 요소가 탐색할 값보다 크면 right를 mid - 1로 설정합니다.
5. 중간 요소가 탐색할 값보다 작으면 left를 mid + 1로 설정합니다.
6. 중간 요소가 탐색할 값과 같으면 값을 찾았으므로 해당 인덱스를 반환합니다.

결과:

1. 반복이 종료될 때까지 값을 찾지 못하면 값이 배열에 없는 것이므로 실패를 반환합니다.

📍 이진 탐색의 구현 예제

다음은 자바를 이용한 이진 탐색의 구현 예제입니다:

public class BinarySearch {
    public int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;  // 값을 찾은 경우
            } else if (arr[mid] < target) {
                left = mid + 1;  // 오른쪽 절반 탐색
            } else {
                right = mid - 1;  // 왼쪽 절반 탐색
            }
        }
        return -1;  // 값을 찾지 못한 경우
    }

    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = bs.binarySearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array");
        }
    }
}

시간 복잡도

• 이진 탐색의 시간 복잡도는 O(log n)입니다. 이는 탐색 범위를 절반으로 줄이기 때문에 발생하는 특성입니다. 예를 들어, 1000개의 요소가 있는 배열에서 이진 탐색을 사용할 경우, 최대 10번의 비교로 원하는 값을 찾을 수 있습니다. 이는 선형 탐색의 O(n) 시간 복잡도와 비교했을 때 매우 효율적입니다.

활용 사례

• 데이터베이스 검색: 대량의 데이터가 정렬된 상태로 저장되어 있을 때, 이진 탐색을 통해 빠르게 데이터를 검색할 수 있습니다.
• 프로그래밍 문제 해결: 코딩 테스트나 알고리즘 문제에서 효율적인 탐색 방법이 필요할 때 자주 사용됩니다.
• 표준 라이브러리 활용: 많은 프로그래밍 언어의 표준 라이브러리에서 이진 탐색을 지원하는 메서드를 제공합니다. 예를 들어, 자바의 Arrays.binarySearch() 메서드를 활용할 수 있습니다.

이러한 이진탐색을 활용하여 프로그래머스의 예제에 접근해보았습니다. 간단한 문제는 기본적인 이진탐색 코드를 구현하면 되지만, 난이도가 올라갈수록 어떤 것을 이진탐색의 대상으로 볼지 판단하는 게 문제의 key라고 생각했습니다. 프로그래머스의 '순위 검색', '입국심사', '징검다리' 문제를 보며 이진탐색이 필요한 부분을 찾아보겠습니다. (문제 원문은 생략하고 링크로 대체하겠습니다)

<순위 검색>

이 문제는 개발팀에서 궁금해하는 문의조건에 해당하는 후보자가 몇명인지를 알아내야 합니다. 이 문제 풀이는 2가지 갈래로 생각해볼 수 있습니다.

1. 이진탐색이 필요하지 않은 경우 : 점수를 제외한 항목 2. 이진탐색이 필요한 경우 : 점수 (ex. 100점 이상을 찾아내야함)

1번의 경우 지원자들의 정보에 "-" 라는 경우의 수를 만들어 저장하고, 이를 비교할 것입니다. 2번의 경우 1번 조건을 만족하는 정보중에서 점수를 기준으로 이진탐색합니다. 이를 통해 후보자 수를 알아냅니다.

여러 가지 조건이 비교할 때 조건 자체에 어떤 차이가 있는지 파악하고, 조건에 맞는 탐색이 중요한 문제였습니다.

• 제출 코드

  import java.util.*;
  

class Solution { public HashMap<String, List> map;

public int[] solution(String[] info, String[] query) {
    int[] answer = new int[query.length];
    map = new HashMap<>();

    // 지원자 정보 - 경우의 수 저장
    for(int i=0; i<info.length; i++) {
        String[] parts = info[i].split(" ");
        String[] conditions = {parts[0], parts[1], parts[2], parts[3]};
        int score = Integer.parseInt(parts[4]);
        makeInfo(conditions, score, 0, "");
    }

    // 모든 리스트 정렬 (한 번만 수행)
    for (String key : map.keySet()) {
        Collections.sort(map.get(key));
    }

    // 요구사항과 일치하는 지원자 정보 저장
    for(int i=0; i<query.length; i++) {
        String[] parts = query[i].replaceAll(" and ", "").split(" ");
        String request = parts[0];                // 요구사항
        int score = Integer.parseInt(parts[1]);   // 요구점수
        int cnt = 0;    // 후보자수

        // 지원자 맵에 요청사항과 일치하는 key가 있는 경우
        if(map.containsKey(request)) {
            cnt = countInfo(request, score);    // 후보자 수를 리턴
        }
        answer[i] = cnt;
    }

    return answer;
}

// 지원자 정보를 경우의 수대로 저장
public void makeInfo(String[] conditions, int score, int depth, String str) {
    if(depth == 4) {
        if(!map.containsKey(str)) {
            map.put(str, new ArrayList<>());    // map에 key 등록
        }
        map.get(str).add(score);                // list에 점수 추가
        return;
    }
    makeInfo(conditions, score, depth+1, str+conditions[depth]);
    makeInfo(conditions, score, depth+1, str+"-");
}

public int countInfo(String request, int score) {

    List<Integer> list = map.get(request);
    // Collections.sort(list);

    int left = 0;
    int right = list.size();

    while(left<right) {
        int mid = (left + right) / 2;
        int midScore = list.get(mid);
        if(score <= midScore) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return list.size() - left;
}

}

<br/>
<br/>

## [<입국심사>](https://school.programmers.co.kr/learn/courses/30/lessons/43238)

이 문제는 입국심사를 마칠 수 있는 가장 최소한의 시간을 찾는 것이었습니다.
이런 경우 시간초를 움직여가면서 몇명이 입국심사를 완료했는지 확인하는 게 핵심이었습니다.
이는 이진탐색으로 접근이 가능합니다.

* 제출 코드
```java
import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;

        Arrays.sort(times);

        long left = 0;
        long right = n * times[times.length - 1]; // 가장 최대치

        // left < right 조건
        while(left <= right) {
            long mid = (left + right) / 2;  // 중간 초
            long count = 0;                 // 심사 가능한 사람 수

            // 반복문으로 심사 가능한 사람 수 계산
            for(int i=0; i<times.length; i++) {
                count += mid / times[i];
            }

            // 필요 인원 초과시
            if(count >= n) {
                answer = mid;
                right = mid - 1;

            // 필요인원 이하인 경우
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
}

<징검다리>

이 문제는 개인적으로 참 어려웠는데요. 돌을 랜덤으로 부술 수 있는데 어떻게 중간 지점을 잡아 이진탐색을 할지가 고민이었습니다.

문제에서 요구하는 바는 돌을 랜덤으로 부수면서 각 지점 사이의 최솟값 중 최댓값을 찾는 것이었습니다. 즉, 최솟값의 범위를 이진탐색으로 움직여 가면서 최솟값 중의 최댓값을 알아내는 문제였습니다.

최솟값을 움직여서 어떻게 답을 알 수 있느냐? 최솟값 보다 작은 거리를 가지는 돌들을 부수면 됩니다. -> 그 어떤 돌도 최솟값보다 작은 거리는 가지지 않을 것입니다. 그리고 이 부순 갯수를 세서 인자로 들어온 n과 비교해가며 이분탐색으로 최솟값 중 최댓값에 도달하면 됩니다.

• 제출 코드

  import java.util.*;
  

class Solution { public int solution(int distance, int[] rocks, int n) { int answer = 0;

    Arrays.sort(rocks);

    int left = 0;
    int right = distance;

    while(left <= right) {
        int mid = (left + right)  / 2;
        int bronkenRocks = getBrokenRocks(distance, rocks, mid);

        if(bronkenRocks <= n) {
            left = mid + 1;
            answer = mid;
        } else {
            right = mid - 1;
        }
    }

    return answer;
}

public int getBrokenRocks(int distance, int[] rocks, int mid) {
    int cnt = 0;
    int prev = 0;

    for(int i=0; i<rocks.length; i++) {
        if(rocks[i] - prev < mid) {
            cnt++;
        } else {
            prev = rocks[i];
        }
    }
    if(distance - prev < mid) cnt++;

    return cnt;
}

}

```

이진탐색은 시간복잡도가 낮은 매우 효율적인 알고리즘으로, 무엇을 이진탐색으로 기준으로 삼을 것인가에 따라 활용도가 좋을 것 같습니다. 저는 위의 예제들을 풀면서 이진탐색의 기준을 유연하게 사고해야겠다는 생각이 들었습니다.

피드백은 언제든 환영입니다. 감사합니다 :)

모음 사전

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

입출력 예 word result "AAAAE" 6 "AAAE" 10 "I" 1563 "EIO" 1189

입출력 예 설명 입출력 예 #1 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2 "AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3 "I"는 1563번째 단어입니다.

입출력 예 #4 "EIO"는 1189번째 단어입니다.

class Solution {
    public int solution(String word) {
        int answer = 0;
        return answer;
    }
}

모음 5개로 이뤄진 사전에서 원하는 문자열이 몇번째에 위치하는지 알아내는 문제입니다.

답을 알아내기 위해서는 사전이 규칙에 의거하여 구성되어야 한다는 사실을 먼저 파악할 수 있습니다. 이를 바탕으로 어떻게 알고리즘적으로 접근할 수 있을까요?

🔎 접근 방식

1. 사전 구성 => 완전 탐색하여 사전을 구성하겠습니다. 찾고자 하는 단어 앞으로 한 단어라도 빠져있다면 원하는 답을 찾을 수 없을 것입니다.

2. 규칙에 의거한 구성 => 문제는 모음의 순서를 기반으로 최대 5개를 구성을 쌓고, 사전에 등록해야합니다. 단어의 구성이 DFS에 가까운 형태이기 때문에 DFS를 사용하여 문제를 해결하겠습니다.

💡그림으로 이해하기

그림과 이해하면 아래와 같습니다.

1. 5개의 모음을 dfs 호출합니다. depth는 모두 0으로 시작합니다.
2. dfs를 호출할 때마다 list 에 add 하여 사전을 채웁니다. dfs가 재귀호출 될 때마다 depth는 1씩 깊어집니다.
3. depth가 5가 되면 return 하고, 이전 재귀로 돌아가 나머지 dfs를 수행합니다.

list가 쌓이면 위와 같이 A, AA, AAA, AAAA, AAAAA, AAAAE ... 이 될 것입니다. 코드는 아래와 같습니다

💻 Java Code

import java.util.*;

class Solution {
    List<String> list;
    public int solution(String word) {
        String[] arr = {"A", "E", "I", "O", "U"};
        list = new ArrayList<>();

        // 완전탐색 하여 사전 구성
        for(int i=0; i<arr.length; i++) {
            dfs(arr, arr[i], 0);    // 단어의 구성이 dfs에 가까운 형태이므로 dfs로 해결
        }

        // 주어진 word 순서를 리턴하는 함수 indexOf 사용
        return list.indexOf(word) + 1;
    }

    public void dfs(String[] arr, String str, int depth) {

        // 5글자를 넘어가면 return
        if(depth == 5) return;
        list.add(str);  // 사전 추가

        // 깊이우선탐색하여 글자를 쌓아간다
        for(int i=0; i<arr.length; i++) {
            dfs(arr, str + arr[i], depth+1);
        }
    }
}

모음사전을 일전에 풀고 다시 풀어보는데 풀이과정이 쉽게 떠오르지 않아 dfs를 내것으로 만드는 과정이 필요하겠다 싶어 정리하게 되었습니다. 풀이과정 자체는 짧지만, 풀이과정을 기억하고 있으면 dfs의 기본이 될 것 같습니다. 더 좋은 의견은 언제든 환영입니다. 감사합니다 :)

해당 문제는 "쿼드 트리 알고리즘" 을 이해하고, 이를 코드로 구현해보는 문제입니다.

✏️ 쿼드 트리 알고리즘

📍 정의

쿼드 트리 압축은 이미지를 4개의 영역으로 나누어 각 영역이 동일한 값으로 이루어져 있는지 확인합니다. 만약 그렇다면 해당 영역을 한 개의 값으로 압축하여 저장하고, 그렇지 않다면 영역을 재귀적으로 나누어 압축을 시도합니다. 이러한 방식을 통해 이미지의 일부 또는 전체를 효율적으로 압축할 수 있습니다.

따라서 쿼드트리 알고리즘은 재귀를 통해 분할 정복 방법론을 구현한 것으로 이해할 수 있습니다.

📍 기본 아이디어

1. 이미지를 작은 사각형 영역으로 분할합니다.
2. 각 영역이 특정 조건을 만족하는지 확인합니다. 예를 들어, 모든 픽셀의 색상이 동일한 경우 등의 조건을 확인할 수 있습니다. 2-1 만약 조건을 만족하지 않는다면 영역을 더 작은 영역으로 분할하고 재귀적으로 위의 과정을 반복합니다. 2-2 만약 조건을 만족한다면 해당 영역을 하나의 단일 노드로 표현합니다.

📍 사용

이는 이미지나 비트맵 데이터와 같은 2차원 배열을 효율적으로 압축하기 위해 사용되는 기술입니다. 주로 이미지 처리나 컴퓨터 그래픽스 분야에서 사용됩니다.

💡 재귀 문제를 해결하는 핵심 포인트

1. Base Case 정의 : 재귀 함수에서는 반드시 종료 조건을 명확하게 정의해야 합니다. 이를 Base Case라고 합니다. Base Case를 정의하지 않으면 무한히 재귀 호출이 일어나 스택 오버플로우가 발생할 수 있습니다.

2. 작은 문제로 분할 : 재귀 함수는 큰 문제를 작은 문제들로 분할하여 해결합니다. 각 재귀 호출에서는 문제의 크기가 작아지도록 만들어야 합니다.

3. 재귀 호출 : 작은 문제들을 해결하기 위해 자기 자신을 호출합니다. 이때 입력값이나 상태가 변경되어야 하며, 이를 통해 Base Case에 도달하도록 합니다.

4. 결과 합치기 : 작은 문제들을 해결한 결과를 합쳐서 큰 문제의 해답을 얻습니다. 종종 이러한 결과들을 재귀 호출의 결과로 반환하거나 전역 변수를 통해 누적합니다.

5. 재귀 호출의 깊이 제한 : 재귀 호출의 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있으므로, 문제 특성에 맞게 적절한 재귀 호출의 깊이를 설정해야 합니다.

깨알코너, "작은 문제"를 다루는 재귀와 동적 프로그래밍 헷갈리지 말자! (더보기)

🤷‍♀️ 재귀와 동적프로그래밍

재귀

재귀는 주로 "분할 정복" 방식을 사용합니다. 큰 문제를 작은 문제로 나누고 이를 해결하는 과정에서 계속해서 재귀적으로 자신을 호출합니다. 이러한 과정에서 기본적으로 "큰 것에서 작은 것"으로 해결 방식을 취합니다.

동적프로그래밍

동적 프로그래밍은 문제를 해결하기 위해 "작은 아이디어"에서 시작합니다. 주어진 문제를 작은 부분 문제로 나누고, 각각의 부분 문제를 해결하면서 이전에 계산된 결과를 저장하고 재활용하여 중복 계산을 피합니다. 이는 보통 반복문을 사용하여 구현되며, 작은 부분 문제들을 해결하고 그 결과를 테이블에 저장하는 방식입니다. 이러한 과정에서 "작은 것에서 큰 것"으로 해결 방식을 취합니다.
물론 이 두 가지 접근 방식은 문제의 특성과 성격에 따라 적합한 방법이 다를 수 있습니다. 때로는 동적 프로그래밍으로 풀 수 있는 문제가 재귀로 풀기도 하고, 그 반대의 경우도 있습니다. 하지만 일반적으로는 위에서 설명한 대로 재귀와 동적 프로그래밍은 각각 다른 문제 해결 방법을 제공합니다.

🔎 프로그래머스 :: 쿼드압축 후 개수 세기

문제 설명 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다. arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항 arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다. arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다. arr의 각 행에 있는 모든 값은 0 또는 1 입니다.
입출력 예 arr result {{1,1,0,0},{1,0,0,0},{1,0,0,1},{1,1,1,1}} {4,9} {{1,1,1,1,1,1,1,1},{0,1,1,1,1,1,1,1},{0,0,0,0,1,1,1,1},{0,1,0,0,1,1,1,1},{0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,1},{0,0,0,0,1,0,0,1},{0,0,0,0,1,1,1,1}} {10,15}

입출력 예 설명 입출력 예 #1 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다. 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다. 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

재귀의 핵심 포인트를 바탕으로 수도 코드를 작성해보겠습니다.

💡 sudo code

함수 쿼드트리:
    만약 영역 전체가 같은 숫자라면: (재귀 호출 여부 판단)
        만약 그 숫자가 0이면:
            0의 개수를 증가시킴
        그렇지 않으면:
            1의 개수를 증가시킴
    그렇지 않으면:
        배열을 네 개로 나눠 쿼드트리 호출 (재귀호출)

코드로 이해하면 아래와 같습니다.

💻 Java Code

class Solution {
    int[] answer = new int[2];

    public int[] solution(int[][] arr) {
        quard(arr, 0, 0, arr.length); // 쿼드 트리 알고리즘을 호출하여 압축 수행
        return answer; // 결과 반환
    }

    // 주어진 영역이 압축 가능한지 여부를 판단하는 함수
    public boolean zip(int[][] arr, int x, int y, int len) {
        int pointer = arr[x][y];

        // 영역 내의 모든 값이 같은지 확인하여 압축 가능 여부 판단
        for(int i=x; i<x+len; i++) {
            for(int j=y; j<y+len; j++) {
                if(pointer != arr[i][j]) return false; // 값이 다르면 압축 불가능
            }
        }
        return true; // 모든 값이 같으면 압축 가능
    }

    // 이미지를 재귀적으로 분할하여 쿼드 트리 압축을 수행하는 함수
    public void quard(int[][] arr, int x, int y, int len) {

        // 압축할 수 있다면
        if(zip(arr, x, y, len)) {
            if(arr[x][y] == 0) answer[0]++;     // 압축 가능하고 0인 경우 0의 개수 증가
            else answer[1]++;                   // 압축 가능하고 1인 경우 1의 개수 증가
            return;                             // 현재 영역은 더 이상 분할할 필요 없음

        // 압축할 수 없다면 잘라서 다시 압축 시도
        } else {
            quard(arr, x, y, len/2);            // 왼쪽 위 사분면
            quard(arr, x, y+len/2, len/2);      // 오른쪽 위 사분면
            quard(arr, x+len/2, y, len/2);      // 왼쪽 아래 사분면
            quard(arr, x+len/2, y+len/2, len/2);// 오른쪽 아래 사분면
        }
    }
}

쿼드트리 알고리즘이라고 하여 어렵게 생각할 게 아니라,

재귀에 대한 이해를 바탕으로 1) 재귀 호출 여부 판단(end point)과 2) 재귀 호출을 하는 것이 포인트인 문제였던 것 같습니다.

더 좋은 방법이 있다면 피드백 환영합니다. 감사합니다 :)

오늘 풀어볼 문제는 프로그래머스의 '거리두기 확인하기'로, 2021 카카오 채용연계형 인턴십에 나왔던 문제입니다.

위드코로나로 전환되며 이제는 거리두기가 벌써 먼 과거가 되었지만 문제를 풀어보며 실생활적인 발상, 궁금증을 알고리즘으로 풀어보도록 하겠습니다.

🪑 거리두기 확인하기

2021 카카오 채용연계형 인턴십

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어, 위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다.

위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다.

위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다. (두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. )

응시자가 앉아있는 자리(P)를 의미합니다.

빈 테이블(O)을 의미합니다.

파티션(X)을 의미합니다.

❓ question

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

❗ 제한사항

• places의 행 길이(대기실 개수) = 5
• places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
• places 원소의 길이(대기실 가로 길이) = 5
• P는 응시자가 앉아있는 자���를 의미합니다.
• O는 빈 테이블을 의미합니다.
• X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.

❕ return 값 형식

1차원 정수 배열에 5개의 원소를 담아서 return 합니다. places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다. 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

places result [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] {{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}}

입출력 예 #1

첫 번째 대기실

No. 0 1 2 3 4 0 P O O O P 1 O X X O X 2 O P X P X 3 O O X O X 4 P O X X P 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No. 0 1 2 3 4 0 P O O P X 1 O X P X P 2 P X X X O 3 O X X X O 4 O O O P P (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다. (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다. (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No. 0 1 2 3 4 0 P X O P X 1 O X O X P 2 O X P O X 3 O X X O P 4 P X P O X 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No. 0 1 2 3 4 0 O O O X X 1 X O O O X 2 O O O X X 3 O X O O X 4 O O O O O 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No. 0 1 2 3 4 0 P X P X P 1 X P X P X 2 P X P X P 3 X P X P X 4 P X P X P 모든 응시자가 거리두기를 지키고 있습니다.

▶ 두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = {};
        return answer;
    }
}

이 문제는 5x5 크기의 대기실에서 응시자들이 거리두기를 잘 지키고 있는지 확인하는 문제입니다. 거리두기를 위한 조건은 맨해튼 거리가 2 이하로 앉지 말아야 하며, 파티션으로 막혀 있는 경우에는 허용됩니다.

이러한 문제를 해결하는 데에는 탐색 알고리즘을 이용할 수 있을 거 같습니다.

너비 우선 탐색(BFS) or 깊이 우선 탐색(DFS) 알고리즘 둘 중 어떤 것이 더 적합한지 판단하기 위해서는 문제의 특성을 4가지 각도로 고려해보겠습니다.

접근하기

최단 거리 탐색:

이 문제에서는 응시자들 사이의 거리를 계산하여 거리두기를 지켰는지 확인해야 합니다. BFS는 너비 우선 탐색이므로 시작점으로부터 레벨별로 탐색을 진행합니다. 이는 최단 거리를 먼저 찾아내는 특성을 가지고 있습니다. 따라서 BFS를 사용하면 최단 거리를 더 효율적으로 찾을 수 있습니다.

=> bfs는 이동할 때 최단거리로 이동

탐색 범위 제한:

거리두기를 확인할 때, 맨해튼 거리가 2 이하인 응시자만을 고려해야 합니다. BFS는 시작점에서부터 주어진 조건에 맞는 노드만을 탐색하므로, 맨해튼 거리가 2 이하인 응시자들만을 고려할 수 있습니다. 반면에 DFS는 깊이 우선 탐색이기 때문에 시작점에서부터 모든 경로를 탐색하게 됩니다.

=> 조건에 맞는 노드들만을 탐색

공간 효율성:

대기실의 크기가 고정되어 있고, 응시자들 사이의 맨해튼 거리가 2 이하인 경우만을 고려해야 합니다. BFS는 너비 우선 탐색이므로 한 번에 한 레벨씩 탐색하면서 공간을 효율적으로 사용할 수 있습니다. 반면에 DFS는 깊이 우선 탐색이므로 재귀 호출을 사용하면서 스택에 깊게 들어가는 경우가 발생할 수 있습니다.

=> 쓸데 없이 깊게 들어갈 필요 없다

종료 조건:

BFS는 종료 조건이 명확하게 설정되어 있습니다. 시작점에서부터 BFS를 수행하다가 최단 거리를 찾았을 때 탐색을 종료하면 됩니다. 하지만 DFS는 모든 경로를 탐색해야 하므로 종료 조건을 설정하기가 어려울 수 있습니다.

=> 종료조건 설정에 유리하다

따라서 이 문제에서는 거리두기를 확인하기 위해 BFS가 더 적합합니다. sudo 코드를 작성하면 다음과 같습니다.

문제 풀이

💡 sudo code

1. 대기실 생성 char[][] place 배열에 담아줍니다.
2. 대기실 생성시 방문여부 배열을 초기화합니다.
3. 대기실을 순회하며 사람(P)인 경우 bfs 함수를 호출하여 근방을 탐색합니다. 3-0. 시작점을 큐에 넣고, 해당 시작점을 방문처리해준다. ★ 큐가 비어있지 않는 동안 3-1부터 3-4까지 반복한다 3-1. 요소 추출 및 종료조건 확인 : 큐에서 요소를 꺼내고, 해당 요소가 맨해튼거리(depth) 2를 초과하였는지, 사람(P)인지 확인한다. 해당하는 경우 맨해튼거리 초과는 무시, 사람은 false를 리턴한다. 3-2. 조건에 맞는 노드 탐색 : 위의 조건에 해당하지 않는 경우 상하좌우 탐색을 한다. 3-2. 레벨별 탐색 : 배열접근 범위에 들어가고, 파티션(X)이 아니라서 접근할 수 있고, 아직 방문할 수 있는 요소를 큐에 추가한다. 3-3. 해당 요소를 방문처리한다.
4. 3번에서 호출한 bfs에서 한 번이라도 false가 나면 결과값을 false로 update하고, 현재 대기실 탐색을 빠져나온다.
5. 최종적으로 현재 대기실에 대한 결과값을 바탕으로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

💻 code

import java.util.*;

class Solution {

    public Queue<int[]> queue;
    public boolean[][] visited;
    public int[] dx = {-1, 1, 0, 0};
    public int[] dy = {0, 0, -1, 1};

    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        for(int k=0; k<places.length; k++) {
            // 대기실 선언
            char[][] place = new char[5][5];

            // 1. 대기실 생성 char[][] place 배열에 담아줍니다.
            for(int j=0; j<5; j++) {
                place[j] = places[k][j].toCharArray();
            }

            // 2. 대기실 생성시 방문여부 배열을 초기화합니다.
            visited = new boolean[5][5];

            boolean result = true;

            // 3. 대기실을 순회하며 사람(P)인 경우 bfs 함수를 호출하여 근방을 탐색합니다.
            for(int i=0; i<place.length; i++) {
                for(int j=0; j<place[i].length; j++) {
                    if(place[i][j] == 'P') {
                        // 거리두기 결과값을 넣어준다
                        if((!bfs(place, i, j, 0))) {
                            result = false;
                            break;
                        }

                    }
                }
            }

            answer[k] = !result ? 0 : 1;
        }  

        return answer;
    }

    public boolean bfs(char[][] place, int x, int y, int dep) {

        queue = new LinkedList<>();

        // 3-0. 시작점을 큐에 넣고, 해당 시작점을 방문처리해준다.
        queue.offer(new int[] {x, y, dep});
        visited[x][y] = true;

        // 큐가 비어있지 않는 동안 3-1부터 3-4까지 반복한다
        while(!queue.isEmpty()) {
            int[] arr = queue.poll();
            int row = arr[0];
            int col = arr[1];
            int depth = arr[2];

            // 3-1. 요소 추출 및 종료조건 확인 : 큐에서 요소를 꺼내고, 해당 요소가 맨해튼거리(depth) 2를 초과하였는지, 사람(P)인지 확인한다. 해당하는 경우 맨해튼거리 초과는 무시, 사람은 false를 리턴한다.
            if(depth > 2) continue;

            if(depth != 0 && place[row][col] == 'P') {
                return false;
            }

            // 3-2.    조건에 맞는 노드 탐색 : 위의 조건에 해당하지 않는 경우 상하좌우 탐색을 한다.
            for(int i=0; i<4; i++) {
                int newRow = row + dx[i];
                int newCol = col + dy[i];

                // 3-2. 레벨별 탐색 : 배열접근 범위에 들어가고, 파티션(X)이 아니라서 접근할 수 있고, 아직 방문할 수 있는 요소를 큐에 추가한다.
                if(newRow >= 0 && newRow < 5 && newCol >= 0  && newCol < 5 &&
                    place[newRow][newCol] != 'X' &&
                    !visited[newRow][newCol]) {
                        queue.offer(new int[] {newRow, newCol, depth+1});
                        visited[newRow][newCol] = true;    // 3-3. 해당  요소를 방문처리한다.
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        // String[][] places = {{"OOPOO", "OPOOO", "OOOOO", "OOOOO", "OOOOO"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
        String[][] places = {{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
        int[] result = sol.solution(places);
        for(int i:result) {
            System.out.print(i + " ");
        }
    }
}

개인적으로 해당 문제에서 깨달음을 얻음 부분은 두 가지입니다.

1) 단일한 시작점이 주어졌던 bfs 문제에서 벗어나, bfs를 여러 번 호출할 수 있었다는 점 2) 상하좌우를 접근할 때 배열을 이용하면 편하다는 점

알고리즘을 공부하다보면 항상 틀을 깨고, 다시 넓혀가는 기분이 듭니다. 다음 풀이로 다시 돌아오겠습니다. 더 좋은 풀이가 있다면 언제든 피드백 부탁드립니다. 감사합니다 :)

오늘 풀어볼 문제는 프로그래머스의 순위로,

플로이드-와샬 알고리즘(Floyd-Warshall algorithm)을 변형하여 접근하는 풀이입니다. 하여 먼저 플로이드-와샬 알고리즘에 대해 접근해보도록 하겠습니다.

🔎 플로이드-와샬 알고리즘(Floyd-Warshall algorithm)이란?

플로이드-와샬 알고리즘(Floyd-Warshall algorithm)은 그래프 이론에서 모든 정점 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치를 가지는 그래프에서도 사용할 수 있습니다. 특히, 음의 사이클이 없는 그래프에서 모든 정점 사이의 최단 경로를 찾는 데 사용됩니다.

이 알고리즘의 주요 아이디어는** "거쳐가는 정점"을 고려하여 더 나은 경로가 있는지**를 검사하는 것입니다. 모든 정점 쌍에 대한 최단 경로를 찾기 위해 3중 중첩된 반복문을 사용합니다.

알고리즘의 동작은 다음과 같습니다:

📍 동작원리

1. 초기 그래프의 인접 행렬을 구성합니다. 여기서 각 (i, j) 쌍에 대한 값은 정점 i에서 정점 j까지의 직접 가중치입니다. 이때, 인접하지 않는 정점 쌍의 경우 무한대로 설정합니다.

int[][] graph = {
    {0, 5, INF, 10},
    {INF, 0, 3, INF},
    {INF, INF, 0, 1},
    {INF, INF, INF, 0}
};

2. 모든 정점 쌍 (i, j)에 대해 다음 작업을 수행합니다.

3. 각 정점 k를 거쳐가는 경로를 고려하여, 정점 i에서 정점 j로 가는 최단 경로를 업데이트합니다. 즉, 현재까지 알려진 i에서 j로의 최단 경로와 i에서 k를 거쳐 j로 가는 경로를 비교하여 최단 경로를 갱신합니다. 위의 과정을 반복하여 모든 정점 쌍에 대한 최단 경로를 찾습니다.

if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
}

예제 코드로 보면 아래와 같습니다.

import java.util.Arrays;

public class FloydWarshall {
    static final int INF = 99999;

    public static void main(String[] args) {
    // 1. 초기 그래프의 인접 행렬을 구성합니다.
        int[][] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };

        int[][] shortestPaths = floydWarshall(graph);

        System.out.println("모든 정점 쌍 간의 최단 경로:");
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if (shortestPaths[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(shortestPaths[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    // 2. 모든 정점 쌍 (i, j)에 대해 다음 작업을 수행합니다.
    public static int[][] floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // 그래프의 값을 가지고 초기화
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 플로이드-와샬 알고리즘 적용
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
            // 3. 각 정점 k를 거쳐가는 경로를 고려하여, 정점 i에서 정점 j로 가는 최단 경로를 업데이트합니다.
                    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        return dist;
    }
}

이 알고리즘의 시간 복잡도는 O(V^3)이며, 여기서 V는 그래프의 정점 수입니다. 따라서 이 알고리즘은 작은 규모의 그래프부터 중간 규모의 그래프까지 효율적으로 작동합니다. 그러나 매우 큰 그래프에 대해서는 성능이 떨어질 수 있습니다.

📍 동적 프로그래밍적인 측면

참고로, 플로이드-와샬 알고리즘은 동적 프로그래밍적인 측면으로도 볼 수 있니다. 그 이유는 정점 쌍 간의 최단 경로는 작은 부분 문제들의 최단 경로를 결합하여 얻을 수 있기 때문입니다.

📍 다익스트라 알고리즘과의 차이점

다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다면, 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구합니다. 다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택했다면, 플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 수행합니다.

프로그래머스의 순위 문제는 승리 및 패배한 결과를 바탕으로 선수들 간의 순위를 결정해야 하는 문제입니다. 이 문제는 위에서 설명한 플로이드-와샬 알고리즘의 변형으로, 차이점은 다음과 같습니다.

🔎 변형 요소

1) 그래프 구성

일반적인 플로이드-와샬 알고리즘에서는 그래프의 가중치가 각 간선의 길이입니다. 하지만 이 문제에서는 각 경기 결과에 따라 선수들 간의 관계를 표현하는 방식으로 그래프를 구성했습니다. 예를 들어, A 선수가 B 선수를 이겼다면 (A, B) 간선의 가중치는 1로, 반대로 B 선수가 A 선수를 이겼다면 -1로 설정됩니다.

2) 경로 탐색

플로이드-와샬 알고리즘에서는 모든 정점 쌍 간의 최단 경로를 찾는 것이 목표입니다. 하지만 이 문제에서는 주어진 경기 결과를 바탕으로 선수들 간의 관계를 업데이트하여 최종적으로 각 선수의 순위를 결정합니다. 따라서 경로 탐색과 동적 프로그래밍의 측면에서 일부 변형이 있습니다.

3) 경로 업데이트

플로이드-와샬 알고리즘에서는 거쳐가는 정점을 고려하여 최단 경로를 업데이트합니다 이 문제에서는 선수들 간의 경기 결과를 통해 선수들 간의 관계를 업데이트합니다.

위와 같은 변형은 주어진 문제의 특성에 따라 필요한 변형이며, 일반적인 플로이드-와샬 알고리즘과 유사한 접근 방식을 가지고 있습니다.

코드로 이해하면 아래와 같습니다.

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] match = new int[n][n];

        // 1) 그래프 구성
        for(int[] result : results){
            int winner = result[0] - 1;
            int loser = result[1] - 1;
            match[winner][loser] = 1;     // win
            match[loser][winner] = -1;    // lose
        }

    // 2) 경로 탐색
        // a->b 이고 b->c이면 a->c 인 경우
        for(int b=0; b<n; b++) {
            for(int a=0; a<n; a++) {
                // 진 경우는 제외
                if(match[a][b] <= 0) {
                    continue;
                }

                // 이긴 경우 (a->b)
                for(int c=0; c<n; c++) {
            // 3) 경로 업데이트
                    // b->c인 경우, 그리고 a와 c의 관계를 알 수 없는 경우
                    if(match[b][c] > 0 && match[a][c] == 0) {
                        match[a][c] = 1;
                        match[c][a] = -1;
                    }
                }
            }
        }

        for(int i=0; i<match.length; i++) {
            int cnt = 0;
            for(int j=0; j<match[i].length; j++) {
                if(match[i][j] != 0) cnt++;
            }
            // n에서 자기 자신을 제외하고 (-1) 값이 있는 경우 순위를 알 수 있음.
            if(cnt == n - 1) answer++;
        }   

        return answer;
    }
}

1) 선수들의 이기고 지는 경우를 그래프화 하고, 2)3) 플로이드-와샬 알고리즘을 변형하여 이기고 지는 경우를 추가적으로 알 수 있는 경우를 그래프에 업데이트 했습니다.

플로이드-와샬 알고리즘이 모든 정점 쌍 간의 최단 경로를 구하는 것이 목표라면, 주어진 문제는 업데이트된 그래프를 바탕으로 경로를 가지는 경우를 구하는 것이 목적인 문제였습니다.

이상 플로이드-와샬 알고리즘을 통해 접근하는 순위 풀이 였습니다. 더 좋은 방법이 있다면 언제든 피드백 환영합니다 :)

출처) 프로그래머스 - 순위

오늘 풀어볼 문제는 프로그래머스의 월간 코드 챌린지 시즌1 문제인 "삼각 달팽이" 입니다.

🐌 삼각 달팽이

문제 설명 정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항 n은 1 이상 1,000 이하입니다.

입출력 예 n result 4 [1,2,9,3,10,8,4,5,6,7] 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

🗝️ key point

1) 등차수열의 합

해당 문제는 삼각형을 다루는 문제로 n의 값에 따라 1개씩 늘어가며 층이 쌓이는 정삼각형 구조입니다.

즉, 어떤 높이의 삼각형이든 삼각형을 쌓는데 필요한 블록의 갯수는 등차가 1인 등차수열의 합이라고 볼 수 있습니다.

하여 answer 배열의 크기는 n의 등차수열 합이 됩니다.

int[] answer = new int[n*(n+1)/2];    // 등차수열의 합

2) 삼각형의 외각 패턴

삼각형의 외각 패턴은 각 행마다 숫자가 하나씩 증가하면서 차례로 채워지는 형태의 삼각형을 의미합니다. 이 패턴은 주로 프로그래밍에서 배열 또는 출력 패턴을 생성하는 데 사용됩니다.

아래와 같은 반복문이 바로 삼각형의 외각 패턴을 코드로 간단하게 구현한 것입니다.

public class Main {
    public static void main(String[] args) {
        int n = 4; // 삼각형의 높이 (행의 개수)

        int count = 1; // 출력할 숫자를 나타내는 변수

        // 이중 반복문을 이용하여 삼각형의 외각패턴을 생성
        for (int i = 0; i < n; i++) { // 행을 나타내는 반복문
            for (int j = i; j < n; j++) { // 열을 나타내는 반복문
                // 삼각형의 외각패턴에 따라 숫자를 출력
                System.out.print(count + " ");
                count++; // 다음 숫자로 이동
            }
            System.out.println(); // 행이 바뀌면 줄바꿈
        }
    }
}

출력 값은 다음과 같습니다.

1 2 3 4 
5 6 7 
8 9 
10 

위와 같은 반복문을 사용하면 삼각형의 외각패턴을 구현해낼 수 있습니다. 이를 바탕으로 삼각형의 모양을 배열에 담아보겠습니다.

3) 인덱스 활용

문제에서 요구하는 것은 삼각형을 좌측 대각선으로 내려가고, 아래를 죽 채우고, 우측 대각선으로 올라오는 형태로 값이 담기길 요구하고 있습니다. 그렇기 때문에 삼각형의 외각패턴을 활용하여 이동수를 제한하되 실제 배열에는 값을 넣기 위한 인덱스가 따로 필요합니다. 삼각을 그리기 위해 3가지 패턴으로 나누어 인덱스를 변경해보겠습니다.

위의 3가지 키포인트를 살려서 구현된 코드는 아래와 같습니다.

💻 문제풀이

public int[] solution(int n) {
        int[] answer = new int[n*(n+1)/2];      // 1) 등차수열의 합
        int[][] arr = new int[n][n];            // 그래프

        // 값을 넣고 싶은 인덱스
        int x = -1;
        int y = 0;
        int num = 1;

        // 2) 삼각형의 외각 패턴 (이중 반복문)
        // 6 -> 5 -> 4 -> 3 -> 2 -> 1 번 수행하기 위함
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {

                // 3) 인덱스 활용
                // 왼쪽 -> 바닥 -> 오른쪽 -> .. 반복됨
                // i=0 -> i=1 -> i=2 -> .. 반복되어 아래와 같이 조건문으로 접근 가능

                // 대각선 왼쪽
                if(i % 3 == 0) {
                    x++;

                // 바닥
                } else if(i % 3 == 1) {
                    y++;

                // 대각선 오른쪽
                } else {
                    x--;
                    y--;
                }
                arr[x][y] = num++;
            }
        }

        // 정답 배열에 접근할 인덱스
        int idx = 0;

        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                if(arr[i][j] == 0) break;   // 0인 경우 반복문 빠져나감
                answer[idx++] = arr[i][j];
            }
        }

        return answer;
    }

해당 문제는 이중반복문에서 j=i 값이 들어갈 때 어떤 패턴이 나오는지 파악할 수 있는 좋은 문제였습니다. 또한 i와 j를 이용하여 배열에 접근하는 익숙한 형태를 떠나 반복문으로 접근횟수를 만들어내고, 또 다른 인덱스로 배열을 컨트롤할 수 있다는 점이 새삼 신선하게 다가왔네요.

더 좋은 접근법이 있다면 언제든 댓글 부탁드립니다 :)

출처 ) 프로그래머스 - 삼각 달팽이

큐(Queue)는 컴퓨터 과학에서 사용되는 데이터 구조 중 하나입니다. 큐는 데이터를 저장하는 추상 자료 구조로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In-First-Out) 방식으로 동작합니다.

드라이브 스루와 같이 먼저 들어온 차가 먼저 나가는 것을 떠올리면 쉽게 이해할 수 있습니다.

기본 동작:

Enqueue(인큐): 데이터를 큐의 뒤쪽에 추가하는 작업을 의미합니다. Dequeue(디큐): 큐의 앞쪽에서 데이터를 제거하고 반환하는 작업을 의미합니다.

용도:

프로세스 관리: 작업 대기열을 관리하거나, 시스템 리소스에 대한 접근을 제어할 때 사용됩니다. 네트워크 통신: 데이터 전송이나 메시지 큐에 사용되어 패킷이나 메시지가 도착한 순서대로 처리됩니다. 알고리즘: 너비 우선 탐색(BFS) 등 다양한 알고리즘에서 활용됩니다.

구현:

큐는 배열(Array)이나 연결 리스트(Linked List)로 구현될 수 있습니다. 배열을 사용하면 큐의 크기가 고정되지만, 연결 리스트를 사용하면 크기에 제한이 없습니다.

이러한 큐를 활용한 너비 우선 탐색(BFS)에 대해 알아보겠습니다.

너비 우선 탐색(BFS)란?

너비 우선 탐색(BFS, Breadth-First Search)은 그래프를 탐색하는 알고리즘 중 하나로, 루트 노드로부터 시작하여 인접한 노드를 먼저 모두 탐색한 후, 그 다음 레벨의 노드를 탐색하는 방식입니다. 이는 그래프를 수평적으로 탐색하는 것으로 생각할 수 있습니다.

알고리즘 동작:

1. 시작 노드를 큐에 넣습니다.
2. 큐가 비어 있지 않은 동안 다음을 반복합니다:

• 큐에서 노드를 하나 꺼냅니다.
• 해당 노드의 이웃한 모든 미방문 노드를 큐에 추가합니다.
• 방문한 노드를 기록합니다.

용도:

최단 경로 탐색: 두 노드 간의 최단 경로를 찾을 때 사용됩니다. 그래프의 연결 여부 확인: 그래프가 연결되어 있는지 확인할 때 유용합니다. 네트워크 트래픽 분석: 네트워크의 특정 지점에 도달하기 위한 경로를 찾을 때 사용됩니다.

구현:

BFS는 주로 큐를 사용하여 구현됩니다. 시작 노드를 큐에 넣고, 큐가 빌 때까지 다음 노드를 꺼내고 그 노드의 이웃을 탐색합니다.

이러한 너비우선탐색을 이용하여 프로그래머스 '가장 먼 노드'라는 문제를 풀어보겠습니다.

가장 먼 노드

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예 n vertex return 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

입출력 예 설명 예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

해당 문제는 1번 노드에서 이어진 노드들의 최단거리를 찾아가면서 가장 먼 거리를 가지는 노드들을 찾으면 되겠습니다.

그림으로 이해하면 다음과 같습니다.

1. 양방향 그래프이므로 양쪽 모두 기록해준다

2. 출발 노드 + depth(는 0) 을 큐에 넣는다

3. 큐에서 노드를 꺼내고 연결된 노드들을 DEPTH와 함께 큐에 넣는다

4. 현재 노드를 방문 처리한다.

5. 큐가 빌 때까지 3,4 과정을 반복한다

큐와 너비우선탐색을 활용한 코드는 다음과 같습니다.

import java.util.*;

class Solution {

    /*
     * 각 노드에 연결된 다른 노드들을 리스트로 관리한다. 이것은 양방향 그래프에서 각 노드의 이웃을 저장하는 방법이다.
     * 각 엣지에 대해 두 개의 노드 간의 연결을 양쪽으로 기록한다.
     * 방문한 노드를 추적하여, 너비 우선 탐색을 수행한다.
     */


    // 양방향 그래프를 담을 리스트
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public int solution(int n, int[][] edge) {

        // 리스트 내 리스트 초기화
        for(int i=0; i<=n; i++) graph.add(new ArrayList<>());

        // 양방향 그래프이므로 양쪽 모두 기록해준다
        for(int[] i: edge) {
            int v = i[0];
            int w = i[1];
            graph.get(v).add(w);
            graph.get(w).add(v);
        }

        // 방문배열 선언 및 초기화
        boolean[] visit = new boolean[n+1];

        // 그래프, 시작점, 방문배열을 인자로 bfs(너비우선탐색) 진행
        return bfs(graph, n, visit);
    }

    public static int bfs(ArrayList<ArrayList<Integer>> graph, int n, boolean[] visit) {
        // 노드 + depth를 함께 들고 다니기 위해 int[]의 Queue 선언
        Queue<int[]> queue = new LinkedList<>();
        int answer = 0;
        int maxDepth = 0;

        // 현재 노드(1) + 현재 depth(0)을 큐에 넣는다
        queue.offer(new int[] {1, 0});

        // 노드 1를 방문 처리한다.
        visit[1] = true;

        // 큐에 값이 있는 동안 탐색을 계속한다
        while(!queue.isEmpty()) {
            int[] arr = queue.poll();
            int v = arr[0];
            int depth = arr[1];

            if(maxDepth == depth) answer++; // 최대 길이 노드라면 answer++;
            else if(maxDepth < depth) {     // 더 긴 거리에 노드가 있다면 answer = 1, maxDepth 갱신
                maxDepth = depth;
                answer = 1;
            }

            // v에 대한 ArrayList 순회
            for(int i=0; i<graph.get(v).size(); i++) {
                int w = graph.get(v).get(i);

                // 방문하지 않은 경우 스택에 쌓음 + 방문처리
                if(!visit[w]) {
                    queue.offer(new int[] {w, depth+1});
                    visit[w] = true;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 6;
        int[][] edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
        int result = sol.solution(n, edge);
        System.out.println(result);
    }
}

풀이 방식은 조금씩 다를 수 있겠습니다. 더 효율적인 코드로 작성 가능하다면 언제든 좋은 피드백 부탁드립니다 :) 이상 큐와 너비우선탐색을 활용한 프로그래머스 - 가장 먼 노드 풀이였습니다.

일하다 보면 필수는 아니지만, 이 정도로 유용한 것이 또 있을까요? 그것이 바로 정규 표현식입니다. 아마 보통 처음 접하게 되는 것은 회원가입 페이지를 만들 때가 아닐까요? 저도 취준 시절에 회원가입 페이지를 만들며 정규 표현식의 편리함을 몸소 느꼈습니다. 하지만 막상 일을 시작하니 자주 사용되는 것이 아니라서 공부해야지~ 하면서도 우선순위에서 미루고 있었습니다.

그러던 어느 날, 상사분을 통해 한 번 제대로 알아두면 평생 활용할 수 있다는 말에 정규 표현식 책을 꺼내 들었습니다.

실습은 반드시❗

정규 표현식이라는 약속과 같습니다. 우리가 이 기호들을 이렇게 해석할 것이다, 라는 게 정규 표현식입니다. 그래서 각 챕터 별로 정규 표현식을 실습하는 것이 약속을 손에 익히는데 큰 도움이 됩니다.

저는 개인적으로 Regex101 사이트를 추천합니다. 이 사이트를 통해 정규 표현식을 실습하고 테스트할 수 있었습니다.

그래서 무슨 책을 추천하는데?

오늘 제가 소개드릴 책은 '손에 잡히는 정규 표현식'입니다. 이 책은 단 한 권으로도 정규 표현식의 개념을 이해하고, 그 활용법을 쉽게 익힐 수 있도록 구성되어 있습니다. 특히 초보자분들이나, 중간중간 참고하고 싶은 분들께 추천드립니다.

제가 아래에 내용의 핵심적인 내용과 공부한 것들을 함께 정리해두겠지만, 더 깊은 이해를 위해서는 직접 책을 읽으며 실습하는 것이 좋습니다.

꼭 읽었으면 하는 챕터

• 1장부터 10장까지

읽지 않아도 되는 챕터

• 부록 A부터 C

여기까지만 알아도 도움되는 정규 표현식

정규표현식으로 색상 번호 일치여부 찾기

body {
color : "#335533"
, background-color : "#ffffff"
}

#[A-Za-z0-9][A-Za-z0-9][A-Za-z0-9][A-Za-z0-9][A-Za-z0-9][A-Za-z0-9]

이 코드는 스타일 시트에서 색상 번호를 찾는 정규표현식을 살펴봅니다. 색상 번호는 "#"으로 시작하고 6자리의 16진수로 표현됩니다.

제외하고 찾기

sam.xls
na1.xls
sa1.xls
na2.xls
cal1.xls
usa3.xls

[ns]a[^0-9]\.xls

=> sam.xls만 나옴 위 예제에서는 sa 뒤에 숫자가 오는 .xls 확장자를 제외한 것을 찾는 정규표현식을 보여줍니다.

메타문자 사용하기

myArray[1]
myArray[2]
myArray[3]
myArray[4]

myArray\[[0-9]\]

메타 문자를 이스케이프하여 사용하는 예제입니다. 대괄호 안의 숫자에 일치하는 패턴을 찾습니다.

줄바꿈 문자

\r : 캐리지 리턴
\n : 엔터
\t : 탭

이 예제에서는 다양한 줄바꿈 문자에 대해 설명하고 있습니다. 윈도우와 유닉스/리눅스 시스템에서의 줄바꿈 문자의 차이도 언급되어 있습니다.

문자 클래스

myArray[1]
myArray[2]
myArray[3]
myArray[4]

myArray\[\d\]

\d, \w, \s 등의 문자 클래스에 대해 설명하는 예제입니다. 각 클래스가 어떤 문자를 일치시키는지를 보여줍니다.

포직스 문자 클래스

[:alnum:]        모든 영숫자([a-zA-Z0-9]와 같다)
[:alpha:]        모든 영문자([a-zA-Z]와 같다)
[:blank:]        빈칸(space)이나 탭 문자([\t]와 같다)
[:cntrl:]        아스키 제어문자(아스키 0번부터 31, 127번)
[:digit:]        모든 한 자리 숫자([0-9])와 같다
[:print:]        출력 가능한 모든 문자
[:graph:]        [:print:]와 동일하나 빈칸(space)는 제외
[:lower:]        모든 소문자([a-z]와 같다)
[:upper:]        모든 대문자([A-Z]와 같다)
[:punct:]        [:alnum:]이나 [:cntrl:]가 포함되지 않은 모든 문자
[:space:]        빈칸을 포함한 모든 공백 문자([\f\n\r\t\v]와 같다)
[:xdigit:]       모든 16진수 숫자([a-fA-F0-9]와 같다)

포직스 문자 클래스의 예제입니다. 각 클래스가 어떤 문자를 일치시키는지에 대한 설명이 포함되어 있습니다.

문자 하나 이상 찾기

이메일 주소를 찾는 정규표현식 예제입니다. [\w.]+는 이메일 주소의 사용자 이름에 해당하는 부분을 나타내며, @ 다음에는 도메인 이름이 옵니다. 도메인 이름은 [\w.]+.\w+와 같이 표현됩니다.

[\w.]+@[\w.]+\.\w+

이 정규표현식은 다음과 같은 이메일 주소를 찾을 수 있습니다:

ben@forta.com
test.support@forta.com
span@forta.urgent.com

집합 안에서는 마침표를 이스케이프 하지 않아도 되지만, 이스케이프 해도 문제가 발생하지 않습니다.

문자가 없는 경우나 하나 이상 연속하는 문자 찾기 문자가 없거나 하나 이상 연속하는 문자를 찾는 예제입니다. \w+[\w.]*@[\w.]+.\w+는 이메일 주소를 찾는 정규표현식으로, 이메일 사용자 이름과 도메인 이름 사이에 문자가 없거나 하나 이상의 문자가 연속될 수 있습니다.

\w+[\w.]*@[\w.]+\.\w+

이 정규표현식은 다음과 같은 이메일 주소를 찾을 수 있습니다

ben@forta.com
test.support@forta.com
.span@forta.urgent.com

문자가 없거나 하나만 있는 문자 찾기

URL을 찾는 정규표현식 예제입니다. https?://[\w./]+는 http:// 또는 https://로 시작하는 URL을 찾습니다. URL에는 사용자 이름, 도메인 이름, 경로가 포함될 수 있습니다.

https?:\/\/[\w.\/]+

이 정규표현식은 다음과 같은 URL을 찾을 수 있습니다:

http://www.forta.com/
https://www.forta.com/

구간 지정하기: 정확한 구간 찾기

#[[:xdigit:]]{6}

이 정규표현식은 6자리의 16진수 숫자를 찾습니다. 주로 색상 코드와 같은 것을 찾을 때 사용됩니다.

구간 지정하기: 범위 구간 찾기

\d{1,2}[\/-]\d{1,2}[\/-]\d{2,4}

이 정규표현식은 날짜를 찾는 데 사용됩니다. 날짜 형식은 숫자로 된 월/일/년 또는 월-일-년입니다.

예:

4/8/03 10-6-2004 2/2/2 01-01-01

구간 지정하기: 최소 구간 찾기

\d+\: \$[\d]{3,}\.\d{2}

이 정규표현식은 특정 패턴을 가진 텍스트를 찾습니다. 숫자로 시작하고, 콜론(:)이 나오고, 공백, 달러 기호($), 그리고 최소 세 자리의 숫자, 소숫점(.), 그리고 두 자리의 숫자로 된 패턴입니다.

예:

1001: $496.00 1002: $1290.69 1003: $26.43 1004: $613.42 1005: $7.61 1006: $414.90 1007: $25.00

과하게 일치하는 상황 방지하기: 탐욕적 수량자 vs 게으른 수량자

정규표현식에서 과하게 일치하는 상황을 방지하는 방법에는 탐욕적 수량자와 게으른 수량자가 있습니다.

• 탐욕적 수량자: , +, {n,} 등을 사용할 때 최대한 많은 문자를 일치시키려고 합니다. 게으른 수량자: 탐욕적인 수량자의 반대로, *?, +?, {n,}? 등을 사용할 때 최소한의 문자만을 일치시키려고 합니다. 이를 설명하는 예시로 <[Bb]>.?</[Bb]>를 들 수 있습니다. 이 정규표현식은 < B > 또는 < b >로 시작하는 태그를 찾으며, 태그 안에 있는 내용을 최소한의 문자만을 포함하여 찾습니다.

예시:

This offer is not available to customers
living in <B>AK</B> and <B>HI</B>
위의 예시에서는 <B>AK</B>와 <B>HI</B>를 각각 찾아냅니다.

단어 경계 지정하기

단어 경계는 특정 단어가 문장 내에서 딱 맞게 일치하는 부분을 찾을 때 사용됩니다. \bcat\b는 "cat"이라는 단어만을 찾아내며, 문장 내에서 "cat"이 딱 맞게 일치하는 부분을 찾습니다.

예시:

The cat scattered his food all over the room.

위의 예시에서는 "cat"을 찾아냅니다.

또한, \bcap와 cap\b는 각각 "cap"이라는 단어가 문장에서 딱 맞게 일치하는 부분을 찾습니다.

문자열 경계 지정하기

문자열 경계는 주어진 문자열의 시작 또는 끝을 찾을 때 사용됩니다. ^\s*<?xml.?>는 XML 선언부를 찾는 정규표현식입니다. 이 정규표현식은 문자열의 시작(^)부터 공백 문자(\s)가 나올 수 있고, 그 뒤에 XML 선언 문자열이 오는 패턴을 찾습니다.

예시:

<?xml version="1.0" encoding="UTF-8" ?>

위의 예시에서는 XML 선언 문자열을 찾아냅니다.

또한,

<\/[Hh][Tt][Mm][Ll]>\s*$

는 HTML 태그의 닫는 태그가 있는지를 찾는 정규표현식입니다. 이 정규표현식은 HTML 닫는 태그(

</html>

)와 문자열의 끝($)을 찾습니다.

예시:

<html>abcd</html>
위의 예시에서는 </html>을 찾아냅니다.

다중행 모드 활용하기

다중행 모드는 정규표현식이 여러 줄에 걸쳐 적용될 때 사용됩니다. 보통은 m 플래그를 사용하여 활성화됩니다. 이 모드를 사용하면 ^는 문자열의 시작과 각 줄의 시작을 나타내고, $는 문자열의 끝과 각 줄의 끝을 나타냅니다.

예를 들어, (m?)//.*은 다중행 모드를 사용하여 주석을 찾는 정규표현식입니다. 이 정규표현식은 //로 시작하는 주석을 찾아냅니다. 각 줄의 시작에 있는 //부터 그 줄의 끝까지의 내용을 일치시킵니다.

Function doSpellCheck(form, field) {
    // Make sure not empty
    if(field.value == '') {
        return false;
    }
    // Init
    var windowName = 'spellWindow';
    var spellCheckURL = 'spell.cfm?formname=comment&fieldname=' + field.name;
    //Done
    return false;
}

위의 코드에서는 //로 시작하는 주석을 찾아내고, 그 뒤에 오는 내용을 일치시킵니다. 이를 통해 주석 부분을 추출할 수 있습니다.

하위 표현식으로 묶기

하위 표현식은 괄호로 묶인 부분을 하나의 그룹으로 만드는데 사용됩니다. 이를 활용하면 그룹으로 묶인 부분에 대해 다양한 작업을 수행할 수 있습니다.

예를 들어,

( ){2,}

는  를 2번 이상 연속으로 나타나는 부분을 찾는 정규표현식입니다.

Hello, my name is Ben Forta, and I am
the author of books on SQL, SoldFusion, WAP,
Windows  2000, and other subjects.

위의 예시에서는

 

가 2번 이상 연속으로 나타나는 부분을 찾아냅니다.

중첩된 하위 표현식

정규표현식에서는 중첩된 하위 표현식을 사용하여 더 복잡한 패턴을 만들 수 있습니다. 중첩된 하위 표현식은 괄호로 묶인 부분 안에 또 다른 괄호로 묶인 하위 표현식을 포함하는 것을 말합니다.

예를 들어, IP 주소를 나타내는 패턴을 찾기 위해 중첩된 하위 표현식을 사용할 수 있습니다. 아래의 예제는 IP 주소를 찾는 정규표현식입니다.

(((1\d{2})|(2[0-4]\d)|(25[0-5])|(\d{1,2}))\.){3}((1\d{2})|(2[0-4]\d)|(25[0-5])|(\d{1,2}))

위의 정규표현식에서는 각각의 숫자 그룹이 0부터 255 사이의 값을 갖는지 확인합니다.

역참조로 찾기

역참조는 이전에 일치한 내용을 다시 참조하여 일치시키는데 사용됩니다. 역참조는 \1, \2, \3 등의 형태로 사용됩니다.

예를 들어,

[ ]+(\w+)[ ]+\1

은 중복되는 단어를 찾는 정규표현식입니다. 이 패턴은 공백으로 구분된 단어가 두 번 이상 반복되는 부분을 찾아냅니다.

This is a block of of text,
several words here are are
repeated, and and they
should not be.

위의 예시에서는 "of of", "are are", "and and"를 찾아냅니다.

마치며,

정규 표현식 다 기억하지 않아도 좋습니다. 책 읽고 다시 잊어버려도 괜찮습니다. (사실 제가 그렇습니다..) 그렇지만 그럼에도 한 번은 정규 표현식을 공부해야 하는 이유라면 구글링을 하고, chat gpt에게 물어볼 때 어떤 작동원리를 가지는지 알고 있다면, 원하는대로 커스텀해서 쓸 수 있기 때문입니다.

여타의 다른 개발 서적과 달리 아주 가벼운 책이니 아직 정규 표현식과 친해지지 않으셨다면 이번 기회에 친해져보는 건 어떨까요..? 😃😃

💪 블로그를 옮기니 폭풍 성장한 나의 모습

기술 블로그를 이리저리 옮겨다니다가 (티스토리, 네이버), 결국 이번 회고록과 함께 다시 벨로그로 돌아왔다. 아무래도 다른 개발자들의 소식을 쉽게 접하게 되는 건 벨로그 같아서 아쉬운 대로 여러 글을 놔두고 새롭게 시작! 오랜만에 다시 들어오니, 21년도에 다른 일을 하며 개발을 접했던 나의 기록이 있었다. 이는 지난하게 느껴졌던 지난 시간동안 내가 꽤 성장했음을 알려주는 좋은 자료가 되었다. 과거의 나를 들여다보는 건 항상 부끄럽지만, 또 언젠가 나에게 큰 힘이 되어주기도 하기 때문에 지난 글들을 살려두고 오랜만에 휴가를 맞아 지금의 나에 대해 적어보려고 한다.

24년도 기준 나는, 신입으로서 1년을 무난하게 넘기고, 이제 1년 4개월 정도 일한 웹개발자 주니어다.

❓ 지난 1년간 나는 무얼 했을까?

2개의 자격증 취득, 3개의 프로젝트, 150건 이상의 운영

누군가에겐 와닿지 않는 수치일 수 있겠지만, 지나고 나니 뿌듯한 기록이다.

✒️ 2개의 자격증 취득

지난 1년 나는 정보처리기사와 SQLD 취득을 위해 총 3번의 시험을 치뤘다. 23년 4월 SQLD, 5월 정처기 필기, 7월 정처기 실기. 단 한 번의 miss도 허락하지 않겠다는 마인드로 공부했더니 모두 단박에 붙었다.

개발자가 무슨 자격증~? 이라고 말해주는 분들도 많지만, 반대로 자격증은 그냥 기본 같은 것이라며 조언해주시는 분들도 많았다. 그리고 막상 내가 공부해보니 정말 너무너무 좋았던 경험이었다. 물론 실무에서 사용하지 않는 내용들도 왕왕 있곤 했지만 (온갖 종류의 디자인 패턴을 달달 외운다든지...) 컴공을 전공하지 않았던 나로서는 정처기를 공부하며 알게 된 내용들이 어렴풋이 실무에서 쓰이고 어떤 맥락인지 이해하게 되는데 큰 도움이 되었다.

또한 SQLD를 공부하며 취준 시절에도, 실무를 하면서도 내가 정말 좋아하는 SQL에 푹 빠질 수 있었고, 특히 실무에서 수많은 데이터를 다루며 '테이블은 어떻게 구축해야하지?', '이런 단순무식한 방법 말곤 없을까?' 고민했던 지점들을 이론으로 배우고 (특히 정규화!), 코드로 이해할 수 있는 좋은 경험이었다.

우리 팀 신입들 중에서는 내가 유일한 비전공자여서 그런지, 신입 중에서 일부는 비전공자를 무시하는 태도를 보인 사람도 있었는데 당시 정처기가 불시험으로 나오며, 우리 회사에서 한번에 합격한 사람은 나뿐이었다... 자격증이 별거 아닐 순 있지만, 나도 나만의 길을 가고 있고 잘했다고 나 자신을 긍정해줄 수 있는 시간이었던 것 같다.

(시험에 대한 TMI, 시험을 준비하는 사람만!!) 참고로 개인적으로 SQLD을 따고 정처기를 공부하니 데이터 파트는 따로 공부하지 않아도 돼서 좋았다. 또한 국비 과정에서 C언어까지 인강을 듣게 하는 걸 보고... 이렇게 다양한 걸 배워서 도움이 될까? 라고 생각들었지만 그럼에도 그냥 틀어놓지 않으려고, 내용을 이해하려고 노력했던 과정들이 정처기 시험에 매우 큰 도움이 되었다. 개념 자체를 이해하고 있으니 실기 문제 정도는 금방 해결되었던 거 같다. => 4과목에서 점수를 가지고 갈 수 있었던 요인 :)

💻 150건의 운영과 3개의 프로젝트

회사에 입사했을 당시 팀은 업무 과부화 상태였다. 일이 너무 많아 입사한지 얼마 안되자마자 바로 실무에 투입되었다. 이 과정에서 쉽지 않았던 건 배웠던 java 대신 다른 언어를 써야 했으며, 백엔드 위주로 공부를 해오다가 프론트 업무량이 많아지게 되었다. 회사에 있는 동안은 주어진 업무에 열중했고, 퇴근하고나서는 새로운 언어에 대한 책들을 닥치는 대로 읽었다. 처음엔 어려웠다. 책과 실무에 있는 코드는 간극이 컸으니까. 무엇보다 프로젝트 구조나 객체에 대한 내용들이 배운 것들과 달라서 실무의 코드가 낯설게 느껴지기도 했다. (사실 이런 부분은 실무에 잔존하는 레거시 코드였다는 걸 시간이 지나며 알게 되었다.)

3개월이 지나고 운영에 속도가 붙기 시작했고, 6개월이 지났을 때 비지니스에 대해 조금은 이해하게 되었다. 그때부터 A-Z까지 내가 맡아서 프로젝트를 진행할 수 있게 되었다. 대량의 데이터도 다뤄보고, 메인으로 프로젝트를 이끄는 경험까지 하게 되었다. 다른 회사들은 1년동안 주니어가 어디까지 경험하는지 모르겠다. 나로서는 회사에서 제공하는 서비스의 한 사이클을 경험할 수 있었다는 게 개인적으로 좋았다.

특히 친하지 않았던 프론트엔드의 매력을 이해하게 되고, Vue 라는 언어를 도입함에 따라 프론트엔드로도 레거시 코드를 리팩토링 하는 경험을 하게 된 것 같다. 그리고 내가 참 좋아하는 sql도, 마음껏 다뤄보고 실무의 수많은 예외적인 데이터들과 싸워봄으로서 (사용자나 정책에 의해 데이터는 다양하게 영향을 받는다) 분명히 많이 성장했음을 느끼고 있다.

어쩌면 벨로그의 글을 올리던 당시의 나와는 비교할 수 없을 만큼 나도 좋은 개발에 대해 고민하게 된, 어엿히 개발직군에서 웹개발자로서 1년을 보낸 것 같다.

🔎 앞으로는?

취준하기 전에 프론트? 백엔드? 어플? 데이터베이스? 어디쪽으로 가는 게 좋을까요. 이런 막연한 생각들을 했었는데, 지금은 주어진 길에 최선을 다하며 기회가 오면 잡아보려고 한다. 아직까지는 아주 파릇파릇한 주니어이므로, 비교적 업무비중이 높지 않았던 백엔드 쪽으로 알고리즘 공부를 해보려고 한다. 그리고 비전공자로서 부족한 cs 지식도 넓혀가보고 싶다.

그리고 tmi로, 취미가 코딩이라는 사람들을 조금은 이해하게 되었다. 앞으로의 나는 업무가 아니어도 재밌는 코딩이 있다면 이것저것 도전하고 싶은 마음이 크다. 업무적으로도 삶적으로도 개발과 함께 꾸준히 갔으면 하는 바람이다. 개발이 즐겁고, 또 이런 내가 좋은 영향을 미치는 사람이었으면 한다 :)

pandas 라이브러리를 이용해 excel 데이터 merge 하기

서론) 직장에서 일을 하던 나는... 두가지 excel 파일을 합쳐야 하는 상황이 되었다. 데이터 값이 많아서 수작업으로 하면 바보가 될 거 같은 이런 느낌. 그래서 공대동생에게 help 요청~ pandas 라이브러리를 추천받았다.

두가지 엑셀 파일 합치기. 이보다 쉬울 순 없다. 딱 5줄이면 됨.

# pandas와 openpyxl 라이브러리 다운로드 후, import 해준다.
import pandas as pd

# 원하는 엑셀 파일을 pd.read_excel('') 함수를 이용해 데이터프레임으로 만들어준다.
df1 = pd.read_excel('파일명1.xlsx')
df2 = pd.read_excel('파일명2.xlsx')

# merge 함수를 이용해 합쳐준다. left는 df1 기준으로 df2가 붙는다는 뜻.
df3 = pd.merge(df1, df2, on="식별자", how="left")

# 해당 데이터프레임을 엑셀로 저장해준다.
df3.to_excel('test_save.xlsx', index=False)

참고한 블로그 사이트

1. 원하는 엑셀 파일을 데이터 프레임으로 만들기 https://hogni.tistory.com/93
2. merge 함수 사용하기 https://nittaku.tistory.com/121
3. 데이터프레임을 엑셀로 저장하기 https://ybworld.tistory.com/42

객체는 init이라는 특별한 멤버 함수를 가지고 있습니다. 이 멤버 함수는 생성자(Constructor) 라고 불립니다. 객체가 생성될 때 생성자는 자동으로 호출됩니다.

FACES = list(range(2, 11)) +
['Jack', 'Queen', 'King', 'Ace']
SUITS = ['Clubs', 'Diamonds', 'Hearts', 'Spades']

Class Card(object):
    """A Blackjack card."""
    def __init__(self, face, suit):
        assert face in FACES and suit in SUITS  
        self.face = face
        self.suit = suit

문자열 변환

card_string()함수를 사용하지 않고도 카드 내용을 문자열로 바꾸는 방법이 있습니다. str(card) 는 card의 특별한 멤버 함수 str 를 호출합니다.

class Card(object):
    """A Blackjack card."""
    """Already defined __init__ and value methods"""
    def __str__(self):  
        article = "a "
        if self.face in [8, "Ace"]:
                article = "an "
        return (article + str(self.face) + " of" + self.suit)

그러면

class Card(object):
    """A Blackjack card."""
    """Already defined  __init__ and value methods"""
    def string(self):
        article = "a "
        if self.face in [8, "Ace"]:
            article = "an "
               return (article + str(self.face) +  " of " + self.suit)


for card in hand:
    print(card.string(), "has value", card.value())

    # card.string() 대신에 간편하게 card를 쓸 수 있다.

for card in hand:
    print(card, "has value", card.value())

부등식

객체에서 비교 연산자 (==, !=, < 등)를 사용하면 예상과 다른 결과가 나올 수 있습니다. 사용자의 생각대로 비교 연산자를 통해 객체를 비교하기 위해서는 다음과 같이 정의를 해야 합니다.

class Card(object):
    """A Blackjack card."""
    """Already defined other methods"""
    def __eq__(self, rhs):
        return (self.face == rhs.face and self.suit == rhs.suit)
    def __ne__(self, rhs):
        return not self == rhs

코딩을 시작할 당시 데스크탑과 노트북 왔다갔다 하면서 배웠던 터라 동일한 방식의 디스크를 원했고, 결론적으로 맥북에 부트캠프를 깔아 윈도우를 사용했다.

그러나 용량이 귀엽고 연차가 있는 나의 맥북에게 파티션을 두개로 나눈다는 건 용량부족의 지름길이었다. 용량이 부족하면 작업속도가 느려지게 된다. 결국 더 손대기 어려워지기 전에 포맷했다.

매번 맥os 업데이트 할 때마다 느낀다. 뭐 이렇게 오래 걸리는가... 맥북에어 15년형 + 핫스팟 조합은 극악무도했고 그래도 3시간 컷으로 포맷 및 맥os 설치를 마쳤다. 고성능이라 조금 느려진 기분. 다운그레이드 해야할까?(당장은 no... 너무 힘뺐다.)

아무튼 다시 맥os로 돌아왔고, 포맷 후 작업할 환경을 만드는 중이다. 나중에 다시 포맷할 수 있으니 잘 정리해두자.

1. 파이참 프로 설치

라이센스를 입력할 것

1-1. 젯브레인 가입

1-2. AWS 가입

2. 파이썬 설치

파이썬 없이는 파이참이 돌아갈 수 없다^^

2-1. jsonview

https://chrome.google.com/webstore/detail/jsonview/chklaanhfefbnpoihckbnefhakgolnmc?hl=ko 크롬에 설치해주기

3. mongoDB 설치

1. 맥북 비밀번호 설정

   MongoDB를 설치하기 위해 Homebrew 라는 프로그램을 이용할 건데, 이 때 반드시 컴퓨터 비밀번호가 있어야 합니다. 비밀번호가 없으신 분들은 맥북의 비밀번호를 먼저 설정하시고 진행해주세요.

2. potlight 에서, "terminal" 또는 "터미널"로 검색해 터미널을 열어줍니다.

3. Homebrew 설치하기

   Homebrew는 무엇인가요?

   ****새로운 것이 참 많죠? 지금부터 맥의 편리함에 빠져드신 겁니다. Homebrew는 '다운로드 패키지'를 관리할 수 있는 툴이에요.

   brew install 프로그램이름

   을 입력하면, 프로그램을 자동으로 다운로드 받아 설치해준답니다. 엄청나죠?

   터미널 창에 아래 코드를 복사, 붙여넣기 하고 엔터!

    /bin/bash -c "$(curl -fsSL [https://raw.githubusercontent.com/Homebrew/install/master/install.sh](https://raw.githubusercontent.com/Homebrew/install/master/install.sh))"

   근데 이 부분 코드가 안 먹는 거다... 맥 os를 monterey 버전으로 깔게 되면서, 자꾸 오류가 났다. 그래서 즉문즉답하러 갔는데, 나와 똑같은 에러가 있는 사람 발견! 그 사람은 M1를 사용하는 중이었는데, 혹시나 해서 코다음 코드를 따라 넣었다.

   /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

   그랬더니 해결되었다는 이야기~ 나는 M1이라고 하기엔 구식 맥북이지만.. 너무 높은 버전을 설치해서 그런 거 같다.

   그러면 아래와 같이 패스워드 입력칸이 나옵니다. 내 맥북 패스워드를 입력하고 엔터! (패스워스를 입력하더라도 화면에 나타나진 않아요. 사실 잘 입력되고 있으니 걱정 마세요! 😜)

   엔터 누른 후에 만약 맥 소프트웨어(Xcode) 업데이트 알림이 뜨면 업데이트를 해주세요.

모든 설치가 완료되면 아래와 같은 화면이 나옵니다. Homebrew 설치 끝!

4. mongoDB 설치하기

   터미널 창에 아래 코드 입력 후 엔터 (한줄씩 복사-붙여넣기 하세요)

    brew tap mongodb/brew

    brew install mongodb-community

   몽고DB 설치가 완료되면 다음 화면이 나옵니다.

   5. mongoDB 실행해보기

      brew services start mongodb-community

      아래와 같은 화면이 나옵니다.

앗, 혹시 brew services start mongodb-community 실행이 안되시나요?

- 안될 경우 대처 방안

    아래 내용을 차례대로 실행해보세요

    ```bash
    brew update
    ```

    ```bash
    brew services start mongodb-community
    ```

6. 마지막으로, mongoDB 실행이 잘 되었는지 확인하기

   http://localhost:27017 에 접속했을 때, 아래와 같은 화면을 만나면 잘 된 것입니다!

4. robo3T 다운로드

https://robomongo.org/download 프로버젼 말고 기본 설치하면 된다. 런치패드에 아이콘이 생겼으면 설치가 완료된 것.

5. 파일질라 다운로드

https://filezilla-project.org/download.php

5-1. 가비아 링크

https://www.gabia.com 다음 링크에서 도메인을 구매할 수 있다.

Q 파일 읽기 2

numbers.txt 파일에는 다음과 같이 숫자가 나열되어 있습니다.

324
103
90
...

이 파일을 읽어서 파일안에 등장하는 모든 숫자들 중 짝수의 합을 구하려 합니다.
다음중 코드의 빈칸에 알맞는 코드는 무엇인가요?

sum = 0
f = open("numbers.txt", "r")
for line in f:
    number = int(line.strip())
    if number % 2 != 0:
    ____________
    sum += number
f.close()

해당 빈칸에 들어갈 답은 continue다. 처음엔 break를 골랐음... 그러면 반복문 자체가 깨지는 건데, 답을 몰랐다.

Python 기본 문법에 있어 pass, continue break의 차이점

1. pass : 실행할 코드가 없는 것으로 다음 행동을 계속해서 진행합니다.
2. continue : 바로 다음 순번의 loop를 수행합니다.
3. break : 반복문을 멈추고 loop 밖으로 나가도록합니다.

출처) https://chancoding.tistory.com/7

Q 이미지를 다루는 코드 읽기

다음 함수는 무엇을 하는 함수인가요?

def foo(canvas, img, x1, y1):
    w,h = img.size()
        for y in range(h):
            for x in range(w):
                canvas.set(x1 + x, y1 +y, img.get(x,y))

나의 오답 : 이미지의 크기를 변경하는 함수 정답 : 이미지를 복사하여 다른 이미지에 붙여넣는 함수 틀린이유 : canvas와 image가 따로 있는 것을 알아차리지 못함 추가적으로 상기하고 가면 좋을 내용 : x1과 y1은 img 값을 놓을 위치다. : img.get(x,y)는 x,y 점에 있는 색깔을 얻는 함수다.

Q 파일 파일 읽기 1

planets.txt 파일에는 다음과 같이 행성의 이름이 나열되어 있습니다.

Mercury
Venus
Earth
Mars
Jupiter

이 파일을 읽어서 행성의 이름으로 이루어진 리스트를 만드려 합니다. 다음 코드의 빈칸에 알맞는 코드는 무엇인가요?

planet = []
f = ____________
for line in f:
    planets.append(line.strip())
f.close()

내가 선택한 답 : "planets.txt".readlines() 정답 : open("planets.txt", "r") 틀린 이유 : readlines()의 개념을 몰라서.

이해해야 하는 부분 : 뒤에서 for 반복문을 통해 line.strip()를 append 해주고 있으므로, open만 하기!

readlines 함수는 파일의 모든 줄을 읽어서 각각의 줄을 요소로 갖는 리스트로 돌려준다. 따라서 위 예에서 lines는 리스트 ["1 번째 줄입니다.\n", "2 번째 줄입니다.\n", ..., "10 번째 줄입니다.\n"]가 된다.

출처) https://wikidocs.net/26 (해당 링크를 참고하자)

리눅스는 윈도우 같지 않아서, '쉘 명령어'를 통해 OS를 조작한다. (일종의 마우스 역할)

리눅스 커널에서 윗화살표를 누르면 바로 전에 썼던 명령어가 나온다.

ls: 내 위치의 모든 파일을 보여준다.

pwd: 내 위치(폴더의 경로)를 알려준다.

mkdir: 내 위치 아래에 폴더를 하나 만든다.

cd [갈 곳]: 나를 [갈 곳] 폴더로 이동시킨다.

cd .. : 나를 상위 폴더로 이동시킨다.

cp -r [복사할 것] [붙여넣기 할 것]: 복사 붙여넣기

rm -rf [지울 것]: 지우기

sudo [실행 할 명령어]: 명령어를 관리자 권한으로 실행한다.
sudo su: 관리가 권한으로 들어간다. (나올때는 exit으로 나옴)

일하면서 공부하는 습관을 들인 한주였다. 평일 주말 가리지 않고 시간이 나면 켜두기라도 하자! 한 번이라도 보자! 이런 마음으로 한주를 보냈다. 9시 출근해서 5시 퇴근. 공부 목표시간은 3시간이었다. 그 이상 해낸 날도 있었고, 그것도 못한 날도 있었다. 그렇지만 3시간은 이제 할 수 있겠다, 그런 생각이 드는 한주였달까. 다음주는 목표시간을 4시간으로 해봐야겠다. 시간이 공부의 양이나 질을 결정하지는 않지만, 시간을 카운팅하면서 내가 엉덩이 붙이고 앉아 화면을 들여다보는 습관을 들일 수 있어서 좋다.

💻 솔직히 어려웠던 4주차

아직 프론트엔드와 백엔드의 개념을 완벽하게 이해한 건 아니지만, 4주차는 그 두 가지를 맛보는 주차였던 것 같다. 막연하게 html 파일만 다루다가, python을 이용하여 db를 보내주는 건 정말 재밌었다. 파이썬... 운 좋게 스타트를 잘해서인지, 직관적인 언어 덕인지 재미를 보고 있다. 앞으로도 계속 공부하고 싶다.

❓ javascript에서 흔히 일어나는 error

내가 겪은 에러를 검색하니, 해당 제목으로 글이 나왔다. 흔히들 겪는 에러 중 하나가 내가 겪는 에러라고 해서 직접 해결할 수 있으리란 용기가 들었다. 그렇지만 밤새 삽질만 했고~ 다음날 다시 켜봤을 때는 지긋지긋했다.

cannot read property 'length' of undefined 내가 겪었던 에러다. 중간에 db를 삭제했는데 그게 array(사실 이게 뭔지 아직 모름)에 영향을 미친 건가 싶었다. 근데 아예 프로젝트 새로 열고, 돌려도 에러가 나서 이건 아니구나 했다. 답은 간단했다.

url 경로를 지정해줘야 하는데 모두 다 기존에는 /로 되어 있었다.

근데 나 이거 건들었다가 다시 되돌리기도 했는데..? 그땐 오류났는데?(잠결에 뭔가 실수한 모양) 아무튼 그 부분을 다시 /get과 /post로 지정해주니 잘 돌아갔다(허무) 역시 개발은 문제 해결했을 때 허무하고 또 동시에 시원하고, 하나 더 배워가는 기분이다.

튜터분의 말을 빌리자면, '이 부분은 주소를 설정해주는 것입니다~ 예를 들면 서버가 아파트라고 할 때 각각 집에 있는 사람이 다르잖아요? 마찬가지로 , 몇층 몇호에 있는 사람을 데리고 와서 일을 시킨다 라고 생각해주시면 됩니다~ 각각의 개별적인 기능의 주소를 지정해주는 것이에요~' 라고 한다.

비유를 들으니 개념이 확장되는 거 같기도 하고~ 그러나 아직 갈 길이 멀다. 그래도 숙제 완료해서 너무 뿌듯하다!! 확실히 숙제를 하면서 내가 성장을 많이 하는 거 같다. 수업 들을 땐, 아 이거 다시 들어야겠다. 진짜 모르겠다. 싶었는데 숙제하면서 이거 무슨 순서로 하셨지? 복기해보면서 코드를 하나하나 뜯어보는 재미가 있다. 😊

5주차를 향해 가포챠코!