• 인텔리제이 환경에서 깃풀을 받았는데 임포트(import)가 갑자기 되지 않는 상황이 발생하였습니다.
• 로컬 실행은 정상적으로 이루어집니다.
• 하지만 에디터에서는 User 클래스를 불러오지 못하였습니다.
• UserService에 모든 user관련 메서드가 빨간색이 뜹니다, 생성자도 마찬가지였습니다.
• notification에 뜬 것을 확인해보고, 재시작했습니다. -> 그래도 안됩니다

해결

개발자들의 친구, chat gpt한테 물어보니, 여러 답변을 내줍니다.

1. Import 문 확인 -> import문은 정상적으로 써져있으니 문제가 아닌 것 같습니다.

2. 의존성 확인 -> build.gradle로 활용 중인데, build는 온전히 이루어지기 때문에 gradle의 문제는 아닌 것 같습니다.

3. 클래스 경로 확인 -> import문을 확인했으나 문제없습니다.

4. 컴파일 확인 -> 빌드를 했지만 되지 않습니다.

5. 캐시 및 재시작 => 결과(해결)

   IntelliJ의 내부적으로 클래스 정보를 저장하는 캐시가 문제였습니다, 캐시를 삭제하고 재시작하니 해당 문제가 해결되었습니다. 오늘도, ChatGPT, Thanks!

공부 한 곳 : 자바 프로그래밍 입문(박은종 저)

인터페이스 -> 구현 코드X

정의 : 자바 프로그래밍 언어에서 클래스들이 구현해야 하는 동작을 지정하는데 사용되는 추상 자료형

• 클래스 혹은 프로그램이 제공하는 기능을 명시적으로 선언하는 역할
• 추상 메서드, 상수로만 이루어져 있음 => 구현 코드 없음 -> 인터페이스로 인스턴스를 생성할 수 없음

package interfaceex;

public interface Calc {
    // 변수이지만 컴파일 과정에서 상수로 인식됨
    // public static final이 자동으로 붙게됨
    double PI = 3.14;
    int ERROR = -9999999;

    // 추상 메서드
    // public abstract가 자동으로 붙게됨
    int add(int num1, int num2);
    int substract(int num1, int num2);
    int times(int num1, int num2);
    int divide(int num1, int num2);
}

클래스를 통한 인터페이스 구현1-추상클래스

인터페이스를 클래스에서 사용하는 것 = 클래스에서 인터페이스를 구현(implements)하다.

인터페이스를 구현한 클래스는 2가지를 선택할 수 있다.

• 인터페이스의 추상 메서드를 모두 구현하여, 구체적인 클래스로서 존재 => 인스턴스 생성가능
• 인터페이스의 추상 메서드 중 일부만 구현하여, 추상 클래스로서 존재 => 인스턴스 생성 불가능 => 구현체를 만드려면 추상 클래스를 상속한 구체적인 클래스를 만들어야함

  package interfaceex;
  

public abstract class Calculator implements Calc {

@Override    // 상속받아서 구현
public int add(int num1, int num2) {
    return num1 + num2;
}

@Override
public int substract(int num1, int num2) {
    return num1 - num2;
}

}

![](https://velog.velcdn.com/images/dev_zzang/post/ea0f53cd-5ef6-48d8-80ca-ef9b0df60f48/image.png)
* 추상클래스이기 때문에 위와 같이 표현한다
* 화살표 뜻 : Calculator가 Calc을 구현했다(점선-추상클래스)
---
### 클래스를 통한 인터페이스 구현2-클래스 완성
위에서 인터페이스를 구현하여 추상클래스를 만들었다.
이제, 추상클래스를 상속(extends)받아 구체적인 클래스를 만들어본다.
```java
package interfaceex;

public class CompleteCalc extends Calculator{

    @Override
    public int times(int num1, int num2) {
        return num1 * num2;
    }

    @Override
    public int divide(int num1, int num2) {
        if(num2 != 0)
            return num1/num2;
        else
            return Calc.ERROR;
    }

    // CompleteCalc에서 추가로 구현한 메서드
    public void showInfo() {
        System.out.println("Calc 인터페이스를 구현하였습니다.");
    }
}    

이제, 위에서 구현해 놓은 CompleteCalc를 실행해보자

package interfaceex;

public class CalaulatorTest {

    public static void main(String[] args) {
        int num1 = 10;
        int num2 = 5;

        CompleteCalc calc = new CompleteCalc();
        System.out.println(calc.add(num1, num2));        // 15
        System.out.println(calc.substract(num1, num2));    // 5
        System.out.println(calc.times(num1, num2));        // 50
        System.out.println(calc.divide(num1, num2));    // 2
        calc.showInfo();    // Calc 인터페이스를 구현하였습니다.
    }
}

new CompleteCalc()를 보면 알 수 있듯이, 구체적인 클래스인 CompleteCalc 클래스만 인스턴스를 생성할 수 있음

• 이제 위와 같이 구현된 것이다.
• CompleteCalc는 Calc를 구현한 Calculator을 상속받은 '구체적인 클래스'로서, 인스턴스를 생성할 수 있다.

인터페이스 구현과 형 변환

• 하위 클래스의 형 변환이 어떻게 이루어질까? Calc <----- Calculator <------ CompleteCalc
• 상속 관계에서 하위 클래스는 상위 클래스 자료형으로 묵시적 형 변환할 수 있음 => 인터페이스도 마찬가지다. => CompleteCalc는 Calculator형 이면서, Calc형이다. = 사람은 동물이면서 생명체이다.(사람 < 동물 < 생명체)

// 위의 코드에 이어서
// CompleteCalc calc = new CompleteCalc(); 위의 구현체
Calc newCalc = calc;

=> 인터페이스를 구현한 클래스가 있을 때, 그 클래스는 해당 인터페이스형으로 묵시적 형 변환이 이루어지며, 형 변환되었을 때 사용할 수 있는 메서드는 인터페이스에서 선언한 메서드 뿐이다! => Calc에는 showInfo()는 없음을 확인할 수 있다.

정리

• 인터페이스는 클래스들이 구현해야할 기능을 명시적으로 선언해둔 추상 자료형이다. => 연극에서의 "대본"이다. 즉, 대본은 연기할 연기자(인스턴스)가 필요하다.
• 인터페이스에는 추상 메서드와 상수만 존재한다. (public static final, public abstract를 안써도 자동으로)
• 구현은 implements로 수행한다.
• 인터페이스를 구현할 클래스가 있을 때, 그 클래스는 해당 인터페이스형으로 묵시적 형 변환이 이루어지며 형 변환이 되었을 때 사용할 수 있는 메서드는 인터페이스에서 선언한 메서드 뿐이다.

공부한 곳 : 김영한 스프링 DB 핵심강의1 -> 정말 이해가 잘갑니다,,강추,,!

Driver Manager

• JDBC가 제공하는 말 그대로 "드라이버 관리자"이다.
• 라이브러리에 등록된 DB 드라이버들을 관리하고, 커넥션을 획득하는 기능을 제공한다.

cf) Connection 인터페이스 cf) DriverManager

• 등록된 JDBC 드라이버 리스트를 파악하는 것을 확인할 수 있다.

DriverManager 커넥션 요청 흐름

1. DriverManger.getConnection()에 필요한 연결정보를 매개변수로 집어넣고 커넥션을 호출한다.
2. DriverManager가 등록된 드라이버 목록을 순서대로 지나면서 커넥션을 획득할 수 있는지를 찾는다.
   • 앞선 예제에선 jdbc:h2를 통해서 h2 DB랑 연결됨을 확인할 수 있었다.
   • id, 비밀번호, 주소 등이 맞으면 해당 커넥션을 반환한다.
   • 만약 h2 DB앞에 다른 DB의 드라이버에 커넥션을 요청했었다고 한다면, 이 드라이버들은 본인들이 처리할 수 없다는 결과를 반환하여, DriverManager는 다음 드라이버로 이동한다.
3. 찾은 커넥션 구현체를 애플리케이션에 반환한다.

java.sql.Connection 인터페이스를 구현한 h2 driver

공부한 곳 : 김영한 스프링 DB 핵심강의1 -> 정말 이해가 잘갑니다,,강추,,!

오늘은 JDBC 공부한 내용을 직접 코드로 쳐보면서 적용해 보겠습니다. 복습하자면, JDBC는 DB마다 달랐던 커넥션 연결, SQL 전달, 결과 응답을 인터페이스를 하나 두고, 각 DB사 마다 구현체를 만들게 해서 개발자가 JDBC 활용법만 알면 쉽게 DB 연결을 할 수 있도록 하기 위해서 나왔다는 것을 기억해봅시다!

1. Springboot로 파일 생성

• 스프링부트로 파일을 생성할 때, 아래의 두 가지를 dependancy에 넣어서 받습니다.
  1. Spring JDBC API
     2. h2 driver -> h2 db 구현체
• 추가적으로 @어노테이션을 쉽게 활용할 수 있도록 lombok정도를 추가적으로 넣어주세요!

2. 데이터베이스 켜기

• h2 데이터베이스를 이용하겠습니다.
• 버전은 각자의 spring 버전에 맞게 받아주시면 될 것 같습니다. (종종 버전이 안맞아서 오류가 뜨는데, 그럴 땐 1.4.200을 추천드립니다.)
• 추가로 먼저 DB파일을 구성하고, 연결하는 과정이 있기는 하지만, 생략하겠습니다.
• 아래와 데이터베이스 연결할 수 있는 상태를 만듦니다.
• 여기서 사용자명, 비밀번호는 알아서 지정해주시되, 기억해주세요. -> 스프링 서버에서 DB를 접속할 때, 알아야할 데이터들입니다!
• JDBC URL은 해당 DB의 URL이므로, 이 또한 DB 접속 때 사용하니, 기억해주세요!

3. 연결에 필요한 상수 선언

public abstract class ConnectionConst {
    public static final String URL = "jdbc:h2:tcp://localhost/~/test";
    public static final String USERNAME = "sa";
    public static final String PASSWORD = "";
}

• 추상 클래스로 선언한 것은 인스턴스로 만들어지는 것을 막기 위해서입니다.
• 모든 곳에서 이 클래스의 멤버 변수를 사용하게 하기위해 static을 썼습니다.
• 바뀌는 값이 아니기 때문에 final을 추가했습니다.
• ""안의 값은 데이터베이스를 연결할 때 정해준 값입니다.(JDBC URL, 사용자 명, 비밀번호)

  4. 데이터베이스와 연결하는 코드 작성

  // ConnectionConst에 있는 멤버변수들을 정적선언해줌
  import static hello.jdbc.connection.ConnectionConst.*;
  

@Slf4j public class DBConnectionUtil { public static Connection getConnection() { try { Connection connection = DriverManager.getConnection(URL, USERNAME, PASSWORD); log.info("get connection={}, class={}", connection, connection.getClass()); return connection;

    } catch (SQLException e) {
        throw new IllegalStatementException(e)
    }
}

}

* 데이터베이스와의 연결을 하기 위해서 JDBC가 제공하는 ```DriverManager.getConnection(..)```을 이용했다.
-> 아까 위에서 다운받아주었던 DB 드라이버를 찾고, 해당 드라이버가 제공하는 커넥션을 반환해준다.

### 5. 연결 테스트하기
* 테스트 코드는 test파트에서 해준다.
```java
// 정적 선언
import static org.assertj.core.api.Assertions.assertThat;

@Slf4j
class DBConnectionUtilTest {
    @Test
    void connection() {
        Connection connection = DBConnectionUtil.getConnection();
        assertThat(connection).isNotNull();
    }
}

아래와 같은 결과가 나온다.

DBConnectionUtil - get connection=conn0: url=jdbc:h2:tcp://localhost/~/test
user=SA, class=class org.h2.jdbc.JdbcConnection

• conn0: ~ user=SA가 반환된 connection이다.
• class는 class org.h2.jdbc.JdbcConnection임을 확인할 수 있다. -> java.sql.Connection인터페이스를 H2전용으로 구현한 것이다.

6. 정리

정리

• JDBC는 java.sql.Connection 표준 커넥션 인터페이스를 정의한다.
• 각 DB마다 해당 인터페이스를 구현한 구현체가 존재하며, Driver를 라이브러리로 받아서 활용할 수 있다. -> 위의 경우, org.h2.jdbc.JdbcConnetion이 그 구현체이다.

공부한 곳 : 김영한 스프링 DB 핵심강의1

이전 글에서 언급했듯이, JDBC는 한계점을 지녔다.

• 데이터베이스마다 SQL이 달라서 SQL부분을 바꿔줘야 했다.
• 추가로, 1997년에 출시된 오래된 기술로서, 사용법이 복잡하다 => 이러한 바탕에서 나온 것이 SQL Mapper와 ORM기술이다.

JDBC만 직접 사용

SQL Mapper

• 객체와 RDBMS의 데이터를 개발자가 작성한 SQL로 매핑시켜주는 프레임워크
• 개발자는 SQL을 직접 작성하고, SQL Mapper는 SQL문을 실행하여 얻은 데이터를 객체로 매핑시켜줌
• JDBC API 사용코드를 많이 줄일 수 있음
• MyBatis, JdbcTemplate

  장점

1. SQL을 안다면, 금방 프로젝트에 적용할 수 있음
2. SQL의 세부사항들을 변경하기 편함

   단점

3. 여전히 SQL을 써야함(CRUD)
4. DBMS에 종속적임
   • DBMS 변경시 SQL문의 재사용이 어려움
   • 2개 이상의 DBMS 지원시 유지 보수가 어려움

ORM(Object-Relation Mapping)

• 객체를 관계형 데이터베이스의 테이블과 자동으로 매핑시켜주는 프레임워크
• 설정된 객체 간의 관계를 바탕으로 자동으로 SQL을 생성시켜주고, 실행함 => 따라서 SQL을 직접 작성할 필요가 없다.
• JPA, 하이버네이트, 이클립스링크

  장점

1. 반복적인 CRUD SQL을 알아서 처리해줌
2. 객체 모델링과 관계형 DB 사이의 차이점을 해결해줌
3. 객체 중심의 개발 -> 생산성, 유지보수 good
4. SQL을 사용하지 않다보니, DB에 독립적이다. -> DB가 바뀌어도 코드가 바뀌지 않는다!

   단점

5. 높은 러닝커브
6. 잘못 적용시 속도저하 문제
7. 복잡한 SQL은 사용하지 못할 수도 있다. -> 이 점은 네이티브 SQL로 해결됨

위의 모든 기술 아래에 JDBC가 존재한다. JDBC의 기본 동작 원리를 알아두자!

cf) JPA의 높은 러닝커브에 대한 추가 내용

• JPA를 활용하는 것 자체는 배우는데에 러닝커브가 크진 않다.
• 하지만 영속성 등 깊은 내용을 익히는데에는 러닝커브가 있다.
• 문제 상황에서는 결국 깊은 내용을 알아야 하기에 러닝커브가 존재.
• 물론 여러 DB의 SQL을 배워야하는 러닝커브를 줄여준다는 장점은 존재한다.

공부한 곳 : 김영한 스프링 DB 핵심강의1

JDBC

• Java Database Connectivity
• 자바에서 데이터베이스에 접속할 수 있도록 하는 자바 API이다.
• 데이터베이스에서 자료를 쿼리하거나 업데이터하는 방법을 제공한다. (위키백과)

JDBC 등장 이유

• 애플리케이션 개발은 아래와 같은 모양을 띄게 된다.

• 클라이언트가 서버를 통해 데이터를 저장하거나 조회하면, 서버는 데이터베이스와 아래와 같은 과정을 진행한다.

• 그런데 이 때, 문제는 DB마다 커넥션을 연결하는 방법, SQL 전달 방법, 결과 응답 받는 방법이 모두 다르다.

  여기에 따른 2가지 큰 문제

  1. 데이터베이스를 변경하면, 애플리케이션 서버에 개발된 데이터베이스 사용코드를 모두 변경해야함
  2. 개발자의 learning curve - 모든 DB에 대한 커넥션 연결, SQL, 결과 응답을 공부해야함

이러한 문제때문에 "표준"이 필요하게 되었고, JDBC가 등장하게 되었다.

JDBC 표준 인터페이스

JDBC는 연결, SQL을 담은 내용, SQL요청응답을 인터페이스로 정의해서 제공한다.

• java.sql.Connection - 연결
• java.sql.Statement - SQL을 담은 내용
• java.sql.ResultSet - SQL요청 응답

JDBC 표준 인터페이스를 통해서 개발을 하면 된다. 하지만 인터페이스는 구현체가 있어야 기능이 동작 할 수 있다. 이 때, 구현체는 각 DB벤더(회사)에서 라이브러리로 제공한다. -> JDBC 드라이버. ex) MySQL JDBC 드라이버, Oracle JDBC 드라이버

-> DB에 따라서 해당 회사에서 제공하는 Driver library를 활용하면 된다.

-> Spring initializer의 디펜던스를 통해 여러 드라이버가 있음을 확인할 수 있다.

그래도 부족한 "표준"

JDBC가 많은 부분을 편리하게 해주었지만, DB마다 일부부분이 다르다. SQL의 경우 표준화를 시키려는 노력이 있었지만, 차이는 여전히 존재한다. 따라서, JDBC 코드는 유지시키더라도, DB가 바뀔 경우에 SQL은 다시 바꿔야한다. -> 차 후에 정리할 것이지만, 이 문제를 해결한 것이 JPA(Java Persistence API)이다.

BFS 문제를 앞으로도 쭉 풀 것이지만, 다른 단원으로 넘어가기 전 마지막 문제를 풀어보겠습니다. 숨바꼭질 문제인데요. 이 문제의 경우, 2차원 grid로 풀었던 기존의 문제와는 다른 양상이기 때문에 BFS로 풀어야함을 쉽게 인지하기 쉽지 않았던 것 같습니다. 하지만 BFS의 기본 개념, 너비로 뻗어나감을 좀 더 다른 측면에서 볼 수 있는 문제이므로 한 번 풀어보겠습니다.

문제 출처 : https://www.acmicpc.net/problem/1697

접근방법

• 수빈이와 동생이 N, K점에 각각 있다고 한다. -> 1차원 배열
• 수빈이가 현재 위치가 X일 때 1초 후, X-1, X+1, 2*X위치로 이동할 수 있다.
• 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하자. -> 수빈이가 t초에 특정 점에 있다고 하자. 해당 점에서 X-1, X+1, 2*X위치로 이동 했을 때는 t + 1초 일 것이다. -> 모든 점에 대해서 시간을 계산한 후, 혹은 동생의 점에 있에 도착했을 때, 그 값을 출력하면 정답일 것이다.
• 한 가지 주의해야할 점이 있다. 수빈이와 동생의 현재 위치는 한정되어 있지만, 이동 중에는 한정되어 있지 않다. -> 따라서 수빈이는 10만이라는 위치에서 x2를 해서 20만 위치에 있을 수도 있다. -> 물론 이 문제에서는 x2를 하고 -1을 여러번 한 것이, -1을하고 x2를 한 것 보다 손해이다. -> 8만을 간다고 했을 때, 5만 -> x2 -> -20000, 5만 -> -10000 -> x2 두 개를 비교해보면 오른쪽이 훨씬 더 빠르다는 것을 알 수 있다. -> 9만을 간다고 해도, 5만 -> x2 -> -10000, 5만 -> -5000 -> x2 이 와 같이 결국에는 -를 하고 x를 진행하는 것이 빠르다. -> 따라서, 10만을 배열로 잡아도 충분하다.
• 마찬가지로 음수의 위치를 다녀오는 것도 굳이?가 될 수 있다.
• 시간복잡도를 봐보자. N이 10만까지므로 O(N)은 10만. BFS로 충분하다.

시간복잡도 : O(N)

#include<iostream>
#include<queue>
using namespace std;

int n, k;
int arr[100002];    // 배열 변수를 바로 visited 처리하는 데에 활용할 것이다.

int main() {
    cin >> n >> k;
    fill(arr, arr + 100002, -1);    // 방문 안한점 -1처리
    queue<int> q;
    q.push(n);
    arr[n] = 0;
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        if (curr == k) break;
        int np = curr + 1;
        int np2 = curr - 1;
        int np3 = curr * 2;
        // 해당 점이 범위 안이고, 방문하지 않았던 점이라면
        // &&을 통해서 앞의 값이 거짓이라면 뒤의 값을 판단하지 않도록해서
        // array 범위가 넘어가는 일을 없도록 방지한다.
        if (np >= 0 && np < 100002 && arr[np] == -1) {
            arr[np] = arr[curr] + 1;
            q.push(np);
        }
        if (np2 >= 0 && np2 < 100002 && arr[np2] == -1) {
            arr[np2] = arr[curr] + 1;
            q.push(np2);
        }
        if (np3 >= 0 && np3 < 100002 && arr[np3] == -1) {
            arr[np3] = arr[curr] + 1;
            q.push(np3);
        }
    }
    cout << arr[k];
    return 0;
}

추가로 공부한 부분

• BFS에서 np, np2, np3를 판단할 때, else if를 썼어서 오류가 났다. -> 각각 판단해야 하는 부분이라 if를 쓰는 것이 맞았다.

오늘도 이어서 BFS를 풀어보고자 합니다. BFS는 참 아이러니 합니다. 공부를 그렇게 해도, 조금만 비틀면 헤깔리니, 문제 수로 눌러서 개념을 머리에 박는 수밖에. 뜬금없지만, 저는 공부스타일도 BFS인 것 같습니다. 전반적인 지식의 흐름을 다 알고 그 다음, DFS로 진행합니다. 뭔가 쭉 흐름을 알고 시작하는게 마음 편하더군요. 여튼! 오늘 풀 불 문제 또한, 저 번 토마토 문제처럼 여러 곳에서 BFS가 시작하는 문제입니다. 단, BFS를 시작하는 지점마다의 차이가 조금 있는데요, 같이 봐보시죠!

문제출처 : https://www.acmicpc.net/problem/4179

접근방법

• 미로의 행렬이 입력값으로 주어진다. -> grid 문제임을 확인할 수 있다.
• 불이 매분마다 수평또는 수직으로 네 방향 확산된다는 표현이 있다. -> BFS를 활용해야겠다.
• 지훈이는 미로의 가장자리에 접한 공간에서 탈출가능 -> 경계조건에서 지훈이가 탈출한 로직을 구현해야겠다.
• 입력값이 string으로 주어진다. 2차원 배열이긴 한데, string으로 2차를 채워야겠다.
• 문제에 조건이 좀 부족했는데, 지훈이는 한 명이지만, 불은 여러 곳에서 날 수 있다.
• 먼저 불로 BFS를 돌리고, 해당 vis값과 지훈이의 BFS값을 비교하면서 지훈이의 BFS를 넓혀나가는 식으로 하자. -> 지훈이는 뻗어나갈 때, 불과 동시에 혹은 불보다 느리게 갈 경우, 해당 지점으로는 갈 수 없기 때문에
• 입력으로 주어지는 행(R)과 열(C)가 1이상 1000이하이다. BFS로 100만이 나온다. -> 시작복잡도를 보았을 때, O(R*C)라 100만으로 해결가능하다.

시간복잡도 : O(R*C) -> O(N) : 100만

#include<iostream>
#include<queue>
#define MX_I 987654321
using namespace std;

int r, c;
string arr[1002];
int dist_j[1002][1002];
int dist_f[1002][1002];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int ret = MX_I;    // 지훈이의 탈출 최소 시간

int main() {
    cin >> r >> c;
    string S;
    queue<pair<int, int>> Qj;
    queue<pair<int, int>> Qf;
    for (int i = 0; i < r; i++) {
        fill(dist_j[i], dist_j[i] + c, -1);
        fill(dist_f[i], dist_f[i] + c, -1);
    }
    for (int i = 0; i < r; i++) {
        cin >> S;
        arr[i] = S;
        for (int j = 0; j < c; j++) {
            if (S[j] == 'J') {
                Qj.push({ i, j });
                dist_j[i][j] = 0;
            }
            else if (S[j] == 'F') {
                Qf.push({ i, j });
                dist_f[i][j] = 0;    // 0이상일 경우 visited이다.
            }
        }
    }

    // 불의 영역으로 먼저 bfs를 돌린다.
    while (!Qf.empty()) {
        auto curr = Qf.front(); Qf.pop();
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (arr[nx][ny] == '#' || dist_f[nx][ny] != -1) continue;
            dist_f[nx][ny] = dist_f[curr.first][curr.second] + 1;
            Qf.push({ nx, ny });
        }
    }

    // 이제 지훈이로 bfs를 돌린다.
    while (!Qj.empty()) {
        auto curr = Qj.front(); Qj.pop();
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            // 탈출할 수 있는 순간    -> queue가 거리순으로 채워지기 때문에 이 지점 들리면 함수 종료
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
                cout << dist_j[curr.first][curr.second] + 1;
                return 0;
            }
            if (arr[nx][ny] == '#' || dist_j[nx][ny] != -1) continue;
            // 다음 점에서 불이 먼저, 혹은 동시에 점거 했어도 이동할 수 없다.
            // dist_f[nx][ny]를 붙여준 것은 불이 점령한 지점만 체크해야하므로.
            if (dist_f[nx][ny] != -1 && dist_f[nx][ny] <= dist_j[curr.first][curr.second] + 1) continue;
            dist_j[nx][ny] = dist_j[curr.first][curr.second] + 1;
            Qj.push({ nx, ny });
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

추가적으로 알아야할 부분

• BFS에서는 Queue가 채워질 때, 거리 순으로 채워지게 된다.
• 예를 들어 불이 난 지점 부터 '000111122222' 이와 같이 채워지는 것이다.

오늘도 BFS문제를 풀어보겠습니다. BFS를 풀다보면 방문배열을 다르게 다뤄야하는 경우가 종종 있는 것 같습니다. 이번에는 그 방문배열을 다르게 하는 유형을 풀어보도록 하겠습니다. 더해서 너비탐색을 시작하는 점이 여러개인 경우 입니다.

문제 출처 : https://www.acmicpc.net/problem/7576

접근방법

• 문제를 보시면, 바로 grid꼴의 그림을 확인할 수 있습니다. -> 2차원 배열을 이용하겠구나, BFS를 사용할 가능성이 높음을 확인할 수 있습니다.
• 익은 토마토의 영향을 해당 토마토의 받아 상, 하, 좌, 우에 있는 익지 않은 토마토가 익게 됨을 볼 수 있습니다. -> BFS, 너비로 확장함을 확인할 수 있습니다.
• 입력을 보시면 익은 토마토가 여러개임을 확인할 수 있습니다. 입력을 받을 때, 여러 개의 토마토를 받을 수 있도록 Q를 미리 설정해서 풀이를 진행해야할 것 같습니다.
• 출력에서 요구하는 바는 모든 토마토가 익을 때까지의 최소 날짜를 출력하는 것입니다. 또한 저장될 때부터 모든 토마토가 익어있다면 0을 출력해야합니다. 모두 익지 못할 경우 -1을 출력해야합니다. -> BFS 마무리 후, vis를 순회하면서 아직 익지 않은 토마토로 지정해놓은 값이 있다면, -1을 출력하도록 합니다. -> 시작점이 0일이 됩니다. vis[시작점의 x좌표][시작점의 y좌표] 값이 0이 되게 됩니다. -> 이 값을 1로 시작해두고, 마지막에 1값을 빼주는 식으로 하면 입력의 값들을 그대로 활용할 수 있습니다. -> -1은 비어있는 공간, 0은 익지 않은 토마토로 말이죠. 그러면 마지막에 vis를 순회하면서 0의 값이 발견될 경우에 -1을 출력하면 되고, 아닐 경우, 최대값 - 1을 출력하면 됩니다.
• 시간복잡도를 고려해보겠습니다. M, N이 모두 2~1000의 값을 가집니다. O(N*M)이면 대략 1,000,000의 값으로 100만이 나오는군요. O(NM)으로 해결해야겠습니다. -> BFS가 적절한 것 같습니다.

시간복잡도 : O(N*M)

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int m, n;
int arr[1002][1002];
int vis[1002][1002];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
    cin >> m >> n;
    queue<pair<int, int>> Q;    // 토마토의 위치를 담을 큐
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                vis[i][j] = 1;
                Q.push({ i, j });
            }
            else if (arr[i][j] == -1) {
                vis[i][j] = -1;    // 벽은 -1 처리를 해준다.
            }
        }
    }

    // BFS로직을 수행해보자. -> 이미 앞서서 아래의 두 로직수행했다.
    // 1. 익은 토마토 시작점 점을 Q에 집어넣기
    // 2. 익은 토마토의 좌표 방문처리
    while (!Q.empty()) {
        auto curr = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[nx][ny] != 0) continue;    // vis[nx][ny]가 0이 아니면, 방문한 점이거나, 벽이다.
            vis[nx][ny] = vis[curr.first][curr.second] + 1;
            Q.push({ nx, ny });
        }
    }

    // 안익은 토마토가 있는지 확인한다.
    // 안익은 토마토가 있으면 -1출력한다.(0이 있는 경우)
    // 안익은 토마토가 없으면 최대값 -1을 출력한다.
    int ret = -1;    // 날짜 결과값 담을 변수
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j] == 0) {
                cout << -1;
                return 0;
            }
            ret = max(ret, vis[i][j]);
        }
    }
    cout << ret - 1;
    return 0;
}

이번에도, BFS를 풀어보겠습니다. BFS는 워낙 자주 나오는 문제 유형이고, 조금씩 변형되서 나오다 보니, 변형 예제들을 많이 익히면서 변경 사항을 적용하는 것이 중요하다 생각이 듭니다.

문제 출처 : https://www.acmicpc.net/problem/2178

접근 방법

• 문제 시작부터 N*M 배열이 나온다. -> grid 문제임을 확인할 수 있다.(BFS? DFS?)
• 문제에서 구하고자 하는 것은 (1, 1)에서 시작하여 (N, M)위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 것이다.
• N, M(2 ~ 100)으로, O(N^2)까지는 괜찮을 것 같다.
• DFS도 익히기 위해서, DFS, BFS 두 풀이를 모두 도전해볼까 한다.

BFS 풀이

#include<iostream>
#include<queue>
using namespace std;

int n, m;
int arr[102][102];
int vis[102][102];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
string S;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> S;
        for (int j = 0; j < m; j++) {
            if (S[j] == '1')arr[i][j] = 1;
            else if (S[j] == '0')arr[i][j] = 0;
        }
    }
    // BFS수행
    queue<pair<int, int>> q;
    q.push({ 0, 0 });
    vis[0][0] = 1;
    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[nx][ny] != 0 || arr[nx][ny] == 0) continue;
            q.push({ nx, ny });
            vis[nx][ny] = vis[curr.first][curr.second] + 1;
        }
    }
    cout << vis[n - 1][m - 1];
    return 0;
}

DFS 풀이 -> 공부하고 풀어볼 예정이다.

BFS 문제는 코테에서 정말 많이 나온다. 살짝 꼬아서 자주 등장하는 것 같은데, 그럴 때마다 못알아 채는 경우도 있다. 그래서 왜 BFS로 풀이를 한 것인지, 접근 법부터 공부를 해보고자 한다.

문제 출처 : https://www.acmicpc.net/problem/1926

접근 방법

• 우선 도화지가 주어진다(n(1500), m(1500))

• 이 점에서 우선 좌표를 활용한 문제임을 확인할 수 있다.

• 그림의 넓이, 그림의 갯수를 물어보는 문제이다.

• "넓이"의 단어부터 너비우선 탐색 문제임을 확인할 수 있다.

• 500 * 500 = 250000(25만)

• O(NlogN)까지는 가능한 문제이다.

• 하지만 BFS는 기본적으로 O(N)이므로 시간 복잡도도 충분해 보인다.

시간 복잡도 : O(N * M)

#include<iostream>
#include<queue>
using namespace std;

int n, m, p_count;
int arr[502][502];
int vis[502][502];
int psize = 0;    // psize의 최대값을 구해야 한다. 없는 경우 0
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };


void BFS(pair<int, int> start) {
    int temp = 1;
    queue<pair<int, int>> Q;
    Q.push(start);
    vis[start.first][start.second] = 1;
    while (!Q.empty()) {
        auto curr = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
            if (vis[nx][ny] != 0 || arr[nx][ny] == 0)continue;
            vis[nx][ny] = 1;
            temp++;
            Q.push({ nx, ny });
        }
    }
    psize = max(psize, temp);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1 && vis[i][j] == 0) {
                p_count++;
                BFS({ i, j });
            }
        }
    }
    cout << p_count << "\n" << psize;
    return 0;
}

문제

여러 숫자가 주어졌을 때, 해당 숫자 중 2개를 골라 100을 만들 수 있는지 여부를 판단하여라

input

처음 주어지는 숫자는 전체 숫자의 개수(n <= 100) 나머지는 숫자 하나씩 주어진다.(각각의 수는 1이상 99이하의 수, 서로 다른 수가 주어짐)

5 
1 23 53 77 60

접근방법

• 카운팅 배열을 하나 더 둬서 더해서 100을 만들 수 있는지 여부를 판단한다. ex) 77을 판단할 때, 23이 있는지를 확인할 수 있도록한다.
  • 만약 23이 있으면 100을 만들 수 있다.
  • 만약 23이 없으면 77을 카운팅 배열에 추가한다.
• 위와 같이 풀면 입력 값(N)만큼의 시간복잡도로 문제를 풀 수 있게된다.

시간 복잡도 : O(N)

풀이

#include<iostream>
using namespace std;

int n;
int arr[100];

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    int occur[100] = {};
    for(int i = 0; i < n; i++) {
        if(occur[100 - arr[i]] == 1) {
            cout << "100 만들 수 있음";
            return 0;
        }
        occur[arr[i]] = 1;
    }
    cout << "100 만들 수 없음";
    return 0;
}

문제 출처 : https://www.acmicpc.net/problem/10808

접근방법

• 아스키코드를 활용하여 배열의 인덱스에 넣고자함
• 카운팅 정렬을 이용한 풀이

시간 복잡도 : O(N) - N은 주어지는 문자열 길이

#include<iostream>
using namespace std;

string S;
int arr[26];    // 알파벳은 26글자(소문자만 다룸)
int main(){
    cin >> S;
    for(char s : S)
        arr[s - 'a']++;    // 자동 형변환을 활용함

    for(int i = 0; i < 26; i++)
        cout << arr[i] << " ";
    return 0;
}

cf) 참고로 기억해야할 부분

• 아스키코드: A(65), a(97)

이번 시간에는 자료구조 첫 번째, 배열에 대해서 알아보겠습니다.

배열이란?

: 연속된 메모리 주소에 데이터를 저장한 자료구조

배열의 종류

• 정적 배열 : 크기가 정해져 있는 배열
• 동적 배열(vector) : 크기가 정해져 있지 않은 배열

  배열의 특징

1. 데이터를 연속된 메모리 주소에 저장
2. Cache hit rate가 높음 (따로 정리 예정)
3. overhead가 거의 없음 - 추가적인 데이터 저장 필요X
4. 특정 위치에 접근이 빠름 -> O(1)

   배열 관련 시간 복잡도

• 배열 마지막에 원소 추가 : O(1)
• 배열 마지막의 원소 삭제 : O(1)
• 배열 중간에 원소 추가 : O(N)
• 배열 중간에 원소 삭제 : O(N) why? => 중간에 추가(insert)하면 뒤로 나머지 원소들을 밀어야함(for 랜덤 엑세스) => 중간에 삭제(erase)하면 뒤의 나머지 원소들을 당겨야함(for 랜덤 엑세스)

  정적배열의 선언

  int a[4];
  int a[] = {1, 2, 3, 4};

  정적 배열 함수 구현(중간에 원소삽입, 중간의 원소삭제)

// idx: 삽입할 공간, num: 넣을 원소, arr: 해당 배열, len: 배열의 길이
void insert(int idx, int num, int arr[], int len) {
    for(int i = len; i < idx; i--) {
        arr[i] = arr[i - 1];
    }
    arr[idx] = arr[num];
    len--;
}

// idx: 원소를 지울 공간
void erase(int idx, int arr[]), int len) {
    len--;
    for(int i = idx; i < len; i++) {
        arr[i] = arr[i + 1];
    }
}

배열 초기화 -> 3가지 방법

int a[30];
int b[30][30];

// 1. memset을 이용(#include<cstring>) -> 비추천
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

// 2. for문을 이용
for(int i = 0; i < 30; i++) 
    a[i] = 0;
for(int i = 0; i < 30; i++) 
    for(int j = 0; j < 30; j++) 
        b[i][j] = 0;

// 3. fill함수 이용(#include<algorithm>) -> 추천
fill(a, a+30, 0);
for(int i = 0; i < 30; i++) 
    fill(b[i], b[i]+30, 0);

동적배열의 선언

#include<iostream>
#include<vector>
vector<int> v1(3, 4);    // {4, 4, 4}
vector<int> v2(3);        // {0, 0, 0}
vector<int> v3 = {1, 2, 3, 4}    // {1, 2, 3, 4}
vector<int> v4;            // {}

동적배열 관련 메서드

v1.push_back(5);    // {4, 4, 4, 5}    시간복잡도: O(N)
v3.pop_back();        // {1, 2, 3}    시간복잡도: O(N)

cf) 전역에서 선언한 배열과 지역에서 선언한 배열은 다르다?

• 지역에서 선언한 배열의 주소는 따로 정해져서 특이한(알고리즘 풀땐 쓰레기..)값이 나옴

  #include<iostream>
  using namespace std;
  

int a[4];

int main(){ int b[4]; for(int i = 0; i < 4; i++) cout << a[i] << " "; // 0 0 0 0 cout << "\n"; for(int i = 0; i < 4; i++) cout << b[i] << " "; // -858993460 -858993460 -858993460 -858993460 return 0; }

C++언어는 개발자에게 유용한 여러 함수, 클래스를 표준 라이브러리로 제공한다.->STL

표준 템플릿 라이브러리(Standard Template Library, STL) : 템플릿으로 작성된 많은 제네릭 클래스와 함수라이브러리 STL에 포함된 제네릭 클래스와 함수들은 다음과 같이 3종류가 있다.

• 컨테이너(Container) - 템플릿 클래스 : 자료구조를 구현한 클래스 ex) list, queue, stack, dequeu, set, vector 등
• 반복자(iterator) - 컨테이너 원소에 대한 포인터 ex) 원소를 읽을 때 사용하는 iterator, 원소를 쓸 때 사용하는 iterator
• 알고리즘(algorithm) - 템플릿 함수 ex) 복사(copy), 검색(find, search), 삭제(remove), 정렬(sort)

   // 활용법
   #include<vector>        // 벡터 컨테이너를 내려받음
   #include<algorithm>        // 템플릿 함수를 내려받음