Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁

스프링부트와 리액트를 활용해 로그인을 구현 프로젝트를 진행합니다. 순서는
1. 프로젝트 초기화
2. 쿠키를 이용한 로그인 구현
3. 세션을 이용한 로그인 구현
4. JWT 토큰을 활용한 로그인 구현
입니다. 

첫번째는 프론트와 백엔드 설정입니다.

서론

로그인은 현대 웹 애플리케이션에서 필수적인 기능으로 자리 잡았습니다. 사용자 인증은 단순히 애플리케이션에 접근하기 위한 절차를 넘어, 보안, 데이터 보호, 그리고 맞춤형 서비스 제공의 핵심 역할을 담당합니다. 따라서 신뢰할 수 있고 효율적인 로그인 시스템을 설계하고 구현하는 것은 개발자의 중요한 과제 중 하나입니다.

이 포스팅에서는 로그인 시스템을 체계적으로 정리하고자 합니다. 이를 통해 로그인 시스템의 기본 원리부터 실제 구현 방법까지 폭넓게 다루고자 합니다.

프론트는 react를 사용하고 백엔드는 Spring Framework를 활용하여 다음과 같은 방식으로 로그인 시스템을 구현할 예정입니다:

1. 쿠키와 세션을 이용한 상태 관리
2. Spring Security를 활용한 인증 및 권한 부여
3. OAuth2를 통한 소셜 로그인 연동

Frontend 설정

프론트는 리액트를 활용하고 언어는 TypeScript를 이용할 것입니다. 리액트 프로젝트를 생성하기 위해
npx create-react-frontend를 통해 프로젝트를 생성합니다.

해당 프로젝트에서 TypeScript를 사용하기 위해 tsconfig.json을 설정해줍니다.

tsconfig.json

{
    "compilerOptions": {
      "target": "es5",
      "lib": [
        "dom",
        "dom.iterable",
        "esnext"
      ],
      "allowJs": true,
      "skipLibCheck": true,
      "esModuleInterop": true,
      "allowSyntheticDefaultImports": true,
      "strict": true,
      "forceConsistentCasingInFileNames": true,
      "noFallthroughCasesInSwitch": true,
      "module": "esnext",
      "moduleResolution": "node",
      "resolveJsonModule": true,
      "isolatedModules": true,
      "noEmit": true,
      "jsx": "react-jsx"
    },
    "include": [
      "src"
    ]
  }

App.js 파일에서는 react-router-dom 라이브러리를 사용하여 애플리케이션의 라우팅을 설정합니다.
이 설정은 SPA(Single Page Application) 형태의 웹사이트에서 페이지 간 전환을 빠르고 부드럽게 구현할 수 있도록 해줍니다.
BrowserRouter, Routes, Route 등의 컴포넌트를 사용하여 라우트 경로와 해당 경로에 매핑된 컴포넌트를 정의합니다.

npm install react-route-dom을 통해 라이브러리 설치를 진행해줍니다.

App.js

import AppRoutes from "./pages/AppRoutes";

function App() {
  return (
      <AppRoutes />
  );
}

export default App;

AppRoutes.ts

import {BrowserRouter as Router, Route, Routes} from 'react-router-dom';
import { RoutePath } from '../interface/RoutePath';
import HomePage from './home/HomePage';

const AppRoutes = () => {
    return (
      <Router>
          <Routes>
              <Route path={RoutePath.HOMEPAGE} element={<HomePage />} />
          </Routes>
      </Router>
    )
  }
  
  export default AppRoutes

RoutePath.ts

export enum RoutePath {
    HOMEPAGE = "/",
}

HomePage.tsx 파일은 애플리케이션의 메인 페이지 역할을 하는 컴포넌트를 정의합니다.

이 페이지는 사용자가 사이트에 처음 방문했을 때 렌더링되는 기본 화면을 제공합니다.
HomePage 컴포넌트는 React를 사용하여 작성되며, 사용자가 볼 수 있는 다양한 콘텐츠와 네비게이션 링크들을 포함할 수 있습니다.

HomePage.tsx는 github를 참조하시길 바랍니다.

Backend 설정

백엔드는 Spring Boot 프레임워크를 기반으로 하며, 데이터 관리를 위해 JPA(Java Persistence API)를 사용하여 객체-관계 매핑을 지원합니다. 이를 통해 데이터베이스와의 상호작용을 더욱 간편하고 직관적으로 구현할 수 있습니다.

데이터베이스는 경량화된 H2 데이터베이스를 활용하여, 개발 및 테스트 단계에서 빠르고 효율적인 데이터 관리를 수행할 예정입니다. 이를 통해 초기 설정 및 테스트 과정을 간소화하고 생산성을 높일 수 있습니다.

start.spring.io에 해당 프로젝트를 생성해줍니다.

build.gradle은 다음과 같습니다. swagger를 위한 dependency는 넣어주지 않으셔도 됩니다.

build.gradle

plugins {
	id 'java'
	id 'org.springframework.boot' version '3.3.5'
	id 'io.spring.dependency-management' version '1.1.6'
}

group = 'com.example'
version = '0.0.1-SNAPSHOT'

java {
	toolchain {
		languageVersion = JavaLanguageVersion.of(17)
	}
}

configurations {
	compileOnly {
		extendsFrom annotationProcessor
	}
}

repositories {
	mavenCentral()
}

dependencies {
	implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
	implementation 'org.springframework.boot:spring-boot-starter-web'
	compileOnly 'org.projectlombok:lombok'
	runtimeOnly 'com.h2database:h2'
	annotationProcessor 'org.projectlombok:lombok'
	testImplementation 'org.springframework.boot:spring-boot-starter-test'
	testRuntimeOnly 'org.junit.platform:junit-platform-launcher'
	implementation group: 'org.springdoc', name: 'springdoc-openapi-starter-webmvc-ui', version: '2.6.0'
}

tasks.named('test') {
	useJUnitPlatform()
}

데이터베이스 h2 생성

경량화된 h2 데이터베이스를 사용할 것입니다. 해당 설치하기 위해 h2 데이터베이스를 다운로드 사이트로 이동합니다.

압축 파일을 해제 한 후 h2가 설치한 곳으로 이동하여 chmod 755 ./bin/h2.sh로 h2를 실행할 수 있는 권한을 설정해줍니다. bin 폴더로 이동 후 ./h2.sh를 통해 h2 데이터베이스를 실행해보면

다음과 같은 콘솔창이 뜹니다. JDBC URL을 설정은 데이터베이스 생성입니다. 저는 auth라는 데이터베이스를 생성하기 위해 url을 auth로 변경해줍니다. 이후 연결을 해줍니다.

💡 만약 해당 창이 뜨지 않는다면 도메인 앞쪽을 localhost로 변경해줍니다.
http://218.38.137.27:8082/(...)
=> http://localhost:8082/(...)

Spring 프로젝트를 이동하여 application.yml을 다음과 같이 설정해줍니다.

application.yml

spring:
  datasource:
    url: jdbc:h2:tcp://localhost/~/auth
    username: sa
    password:
    driver-class-name: org.h2.Driver

  jpa:
    hibernate:
      ddl-auto: create
    properties:
      hibernate:
        show_sql: true
        format_sql: true

logging.level:
  org.hibernate.SQL: debug
#  org.hibernate.type: trace

서버가 제대로 띄워졌는지 확인하기 위한 healthCheck를 위한 컨트롤러를 만들어줍니다.

StatusController

@Slf4j
@RestController
@RequestMapping("/status")
@Tags(value = @Tag(name = "StatusController", description = "Retrieve any status"))
public class StatusController {

    @GetMapping
    public ResponseEntity<?> serverStatusCheck() {
        log.info("this server is health");
        return ResponseEntity.ok("ok");
    }

    @GetMapping("/all")
    public ResponseEntity<?> anyOneCanAccess() {
        log.info("all people can access");
        return ResponseEntity.ok("all people can access");
    }
}

서버가 제대로 실행되었는지 확인하기 위해 postman을 통해 확인해보면

다음과 같이 제대로 띄워져 있는 결과를 얻을 수 있습니다.

데이터베이스와의 연동 확인

데이터베이스와의 연동을 확인하기 위해 간단한 create 요청을 만들어 디비에 제대로 적제되었는지 확인해보겠습니다.

AccountDto와 SignUpRequest는 Java의 record를 사용해 생성됩니다. record는 Java 16 이상에서 제공되는 기능으로, 불변 객체를 간결하게 정의할 수 있게 해줍니다. 이를 통해 DTO(Data Transfer Object)와 요청 객체를 더 짧고 명확한 코드로 작성할 수 있습니다.

SignUpRequest

public record AccountDto() {
    @Data
    @NoArgsConstructor
    @AllArgsConstructor
    public static final class SignUpRequest {
        private String username;
        private String password;
    }
}

다음은 controller를 생성합니다. @RequestBody를 통해 받은 SignUpRequest를 통해 service의 joinMember를 호출합니다.

TestController

@Slf4j
@RestController
@RequiredArgsConstructor
@RequestMapping("/test")
@Tags(value = @Tag(name = "TestController", description = "check database"))
public class TestController {

    private final TestService testService;

    @PostMapping("/members")
    public ResponseEntity<String> createUser(@RequestBody SignUpRequest signUpRequest) throws Exception {
        log.info("Controller: createUser");
        String createName = testService.joinMember(signUpRequest.getUsername(), signUpRequest.getPassword());

        return ResponseEntity.ok(createName);
    }
}

엔티티 Member를 생성합니다.

Member

@Entity
@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
public class Member {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    private String username;
    private String password;

    public Member(String username, String password) {
        this.username = username;
        this.password = password;
    }
}

TestService는 서비스 계층으로 Repository와의 상호작용을 담당하고 비즈니스 로직을 담당하는 부분입니다.

TestService

@Slf4j
@RequiredArgsConstructor
@Service
public class TestService {

    private final MemberRepository memberRepository;

    public String joinMember(String username, String password) throws Exception {
        log.info("Service: joinMember");
        if (memberRepository.existsByUsername(username)) {
            throw new RuntimeException("fail join member");
        }

        Member member = new Member(username, password);

        memberRepository.save(member);

        return member.getUsername();
    }
}

MemberRepository는 Spring Data JPA의 JpaRepository 인터페이스를 확장하여 데이터베이스와 상호작용하는 저장소(Repository)입니다. 이 인터페이스를 구현함으로써, 기본적인 CRUD(생성, 읽기, 업데이트, 삭제) 기능을 자동으로 제공받을 수 있습니다. 이를 통해 개발자는 복잡한 SQL 쿼리 작성 없이 간단한 메서드 호출만으로 데이터베이스 작업을 수행할 수 있습니다.

MemberRepository

@Repository
public interface MemberRepository extends JpaRepository<Member, Long> {
    boolean existsById(Long id);
    boolean existsByUsername(String username);
    Member findByUsername(String username);
}

포스트맨을 통해서 확인해본 결과는 다음과 같습니다.

Spring의 SQL문은 다음과 같습니다.

데이터베이스에 잘 적제된 것을 확인할 수 있습니다.

깃허브 및 참조

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

잃어버린 결과표에서 순위를 알 수 있는 선수의 수를 구하는 문제였습니다.
순위를 안다는 것은 누군가에게 지고 이겼는지에 대한 모든 결과를 알고 있으면 되므로 wins 배열과 loses 배열을 통해 확인합니다.

소스코드

import java.util.*;

class Solution {
    List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        for(int i = 0; i <= n; i++) {
            wins.add(new ArrayList<>());
            loses.add(new ArrayList<>());
        }
        
        for(int[] result: results) {
            int win = result[0];
            int lose = result[1];
            wins.get(win).add(lose);
            loses.get(lose).add(win);
        }
        
        for(int i = 1; i <= n; i++) {
            boolean[] visited = new boolean[n + 1];
            Queue<Integer> q = new LinkedList<>();
            
            visited[i] = true;
            q.add(i);
            while(!q.isEmpty()) {
                int win = q.poll();
                for(int lose: wins.get(win)) {
                    if (visited[lose]) continue;
                    visited[lose] = true;
                    q.add(lose);
                }
            }
            
            q.add(i);
            while(!q.isEmpty()) {
                int lose = q.poll();
                for(int win: loses.get(lose)) {
                    if (visited[win]) continue;
                    visited[win] = true;
                    q.add(win);
                }
            }
            
            boolean flag = true;
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    flag = false;
                }
            }
            if (flag) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  • List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    src가 이긴 desc가 진 배열이 wins 배열, src가 진 desc가 이긴 배열이 loses 배열입니다.

for(int i = 0; i <= n; i++) {
    wins.add(new ArrayList<>());
    loses.add(new ArrayList<>());
}

for(int[] result: results) {
    int win = result[0];
    int lose = result[1];
    wins.get(win).add(lose);
    loses.get(lose).add(win);
}

• wins 배열과 loses 배열을 초기화합니다.

for(int i = 1; i <= n; i++) {
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> q = new LinkedList<>();

    visited[i] = true;
    q.add(i);
    while(!q.isEmpty()) {
        int win = q.poll();
        for(int lose: wins.get(win)) {
            if (visited[lose]) continue;
            visited[lose] = true;
            q.add(lose);
        }
    }

    q.add(i);
    while(!q.isEmpty()) {
        int lose = q.poll();
        for(int win: loses.get(lose)) {
            if (visited[win]) continue;
            visited[win] = true;
            q.add(win);
        }
    }

• 첫번째 while문을 통해 i가 이긴 선수들과 이긴 선수들의 결과표를 통해 인덱스를 방문합니다.
• 두번째 while문을 통해 i가 진 선수들과 진 선수들의 결과표를 통해 인덱스를 방문합니다.

boolean flag = true;
    for(int j = 1; j <= n; j++) {
        if(!visited[j]) {
            flag = false;
        }
    }
    if (flag) {
        answer++;
    }
}

return answer;

• 모든 배열을 방문하였다면 순위를 알 수 있는 것이므로 answer를 증가하고 반복문 종료시 answer를 반환합니다.
•  

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

bfs 탐색을 통해 1번 노드에서 가장 먼 노드를 찾는 문제였습니다. 저는 visited 배열과 step 배열을 통해서 문제를 풀었습니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited;
    int[] step;
    List<List<Integer>> graph = new ArrayList<>();
    Queue<Integer> q = new LinkedList<>();
    
    public void bfs() {
        while(!q.isEmpty()) {
            int src = q.poll();
            for(int desc: graph.get(src)) {
                if (!visited[desc]) {
                    visited[desc] = true;
                    step[desc] = step[src] + 1;
                    q.add(desc);
                }
            }
        }
    }
    
    public void init(int n) {
        visited = new boolean[n + 1];
        step = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        q.add(1);
        visited[1] = true;
        step[1] = 1;
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 1;
        
        init(n);
        
        for(int[] vertex: edge) {
            int src = vertex[0];
            int desc = vertex[1];
            graph.get(src).add(desc);
            graph.get(desc).add(src);
        }
        
        bfs();
        
        Arrays.sort(step);
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if (max < step[i]) {
                answer = 1;
                max = Math.max(max, step[i]);
            } else if (max == step[i]) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  
  • boolean[] visited
    해당 인덱스의 노드를 방문했는지 확인하는 배열입니다.
  • int[] step
    해당 인덱스의 노드의 그래프의 깊이 입니다.
  • List<List<Integer>> graph = new ArrayList<>()
    src와 desc로 설정하여 graph를 설정합니다.
  • Queue<Integer> q = new LinkedList<>()
    bfs 를 위한 Queue를 선언합니다.
• bfs 메소드
  일반 bfs 메소드입니다.
  • src와 desc를 선언하여 방문하지 않은 desc면 q에 넣고 step도 초기화합니다.
• init 메소드
  변수들을 초기화하는 메소드입니다.

Arrays.sort(step);
int max = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
    if (max < step[i]) {
        answer = 1;
        max = Math.max(max, step[i]);
    } else if (max == step[i]) {
        answer++;
    }
}

return answer;

• 몇번 인덱스를 찾는 문제가 아니라 가장 먼 노드의 갯수를 구하는 문제이므로 Array를 정렬합니다.
• step이 가장 큰 노드를 찾으면 answer를 초기화 합니다.
• max와 step[i]가 같으면 answer을 1 증가합니다.
• 반복문 종료 후 answer를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

이 문제는 이분 탐색을 어떤 값으로 하느냐가 포인트였던 것 같습니다. 저는 바위 간의 거리의 최솟값을 기준으로 이분탐색을 진행하였습니다. 해당 바위 사이의 거리가 최솟값보다 크다면 삭제하고, 삭제한 값이 n보다 더 많으면 범위를 재탐색하는 로직으로 설계하였습니다.

하지만 해당 문제에서 제거한 바위의 갯수랑 n과 같을때로 설정하면 문제가 틀리고 제거한 바위가 n보다 작거나 같을때로 하면 정답이 되었습니다. 문제의 설명이 빠진 것인지 싶은데 혹시 해당 이유를 아시는 분 있으면 댓글달아주시면 감사드립니다😁

소스코드

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance;
        
        // 바위의 거리의 최솟값을 기준으로 이분탐색
        while(left <= right) {
            int mid = (left + right) / 2;
            int deleteRocks = 0;
            int prevRock = 0;
            
            for(int rock: rocks) {
                if (Math.abs(rock - prevRock) < mid) {
                    deleteRocks++;
                } else {
                    prevRock = rock;
                }
            }
            
            if (distance - prevRock < mid) {
                deleteRocks++;
            }
            
            if (deleteRocks > n) {
                right = mid - 1;
            } else if (deleteRocks <= n) {
                left = mid + 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 초기화
  • rocks: 바위 위치들을 정렬하여 바위들 사이의 거리를 쉽게 계산할 수 있도록 합니다
  • left: 최소 거리의 시작 값은 1로 설정합니다.
  • right: 최대로 가능한 거리 값은 전체 거리인 distance입니다.
• 이분탐색
  
  • mid: 현재 탐색 중인 거리 값입니다. 이 값은 최소 거리로 유지하면서 바위들을 제거할 수 있는지 확인하려는 값입니다.
  • deleteRocks: 제거된 바위의 갯수입니다.
  • prevRock: 이전 바위의 인덱스입니다. 처음에는 0으로 설정합니다.(초기값)
• 바위들 사이의 간격 체크
  
  • Math.abs(rock - prevRock) < mid: 현재 바위와 직전 바위 사이의 거리가 mid보다 작으면, 이 바위는 제거해야 하므로 deleteRocks를 증가시킵니다.
  • 그렇지 않으면, prevRock을 현재 바위로 업데이트하여 다음 바위와의 거리를 비교할 준비를 합니다.
• if (distance - prevRock < mid) { deleteRocks++; }
  마지막 바위와 거리 체크
• 범위설정
  • deleteRocks > n: 바위를 너무 많이 제거한 경우, mid값을 줄여야 하므로 right = mid - 1으로 범위를 좁힙니다.
  • deleteRocks <= n: 바위 제거 개수가 n개 이하인 경우, mid 값은 유효하므로 left = mid + 1로 범위를 확장하고, answer를 mid로 업데이트하여 더 큰 거리 값도 탐색할 수 있도록 합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

이분탐색을 이용하여 심사가 끝나는 시간을 기준으로 처리 가능한 총 인원을 계산하여 n보다 클 때에 값을 갱신하는
lowerbound(특정 조건을 만족하는 값 중에서 최솟값)를 사용했습니다. 

소스코드

import java.util.*;

class Solution {

    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0;
        long left = 1;
        long right = (long)times[times.length-1] * n; // 60
        
        while (left <= right) {
            long mid = (left + right) / 2; // 중간 시간
            long peopleProcessed = 0;

            // mid 시간 동안 처리 가능한 총 인원 계산
            for (int time : times) {
                peopleProcessed += mid / time;
                if (peopleProcessed >= n) break; // n명을 초과하면 더 계산할 필요 없음
            }

            if (peopleProcessed >= n) {
                answer = mid; // 더 작은 시간을 탐색
                right = mid - 1;
            } else {
                left = mid + 1; // 시간을 더 늘림
            }
        }

        return answer;
    }
}

코드 설명

• 변수 초기화
  • times: 각 심사대의 심사 시간이 들어있는 배열. 이 배열은 오름차순으로 정렬됩니다.
  • left: 가능한 시간의 최솟값 1입니다.
  • right: 최악의 경우 가장 느린 심사관이 n명을 모두 처리하는 시간(times[times.length-1] * n) 입니다.
• 이분탐색
  • mid: 현재 탐색 중인 시간입니다.
  • peopleProcessed: mid 시간 동안 각 심사관이 처리할 수 있는 총 인원 수를 계산합니다.
• mid 시간 동안 처리 가능한 인원 계산
  • mid / time: 각 심사관이 mid 시간 동안 처리 가능한 사람 수.
  • 총 처리 인원(peopleProcessed)이 n명을 넘으면 반복문을 종료합니다.
• 조건에 따라 탐색 범위 조정
  
  • peopleProcessed >= n: mid 시간이 충분히 길어 n명을 처리할 수 있는 경우, 더 작은 시간에서 조건을 만족하는지 확인합니다.
  • peopleProcessed < n: mid 시간이 부족하므로 시간을 늘려야 합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 결합법칙을 무시한 채 최대 값을 구하기 위한 문제입니다. - 연산에서는 왼쪽 값은 최댓값, 오른쪽 값은 최솟값이 되어야 최대값이 되고, + 연산에서는 두 값 모두 최대 값이 되어야 합니다. 이를 통해 dpMax 배열과 dpMin 배열을 통해 문제를 풀었습니다.

소스코드

class Solution {
        public int solution(String[] arr) {
            int n = arr.length / 2 + 1; // 숫자의 개수
            int[][] dpMax = new int[n][n];
            int[][] dpMin = new int[n][n];

            // 숫자 초기화
            for (int i = 0; i < n; i++) {
                dpMax[i][i] = Integer.parseInt(arr[i * 2]);
                dpMin[i][i] = Integer.parseInt(arr[i * 2]);
            }

            // 구간 길이
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    int j = i + len;
                    dpMax[i][j] = Integer.MIN_VALUE;
                    dpMin[i][j] = Integer.MAX_VALUE;

                    // i부터 j까지 연산자에 대한 분할 계산
                    for (int k = i; k < j; k++) {
                        String operator = arr[k * 2 + 1];
                        int maxLeft = dpMax[i][k];
                        int minLeft = dpMin[i][k];
                        int maxRight = dpMax[k + 1][j];
                        int minRight = dpMin[k + 1][j];

                        if (operator.equals("+")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
                        } else if (operator.equals("-")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
                        }
                    }
                }
            }

            return dpMax[0][n - 1]; // 전체 구간의 최댓값 반환
        }
    }

코드 설명

• int n = arr.length / 2 + 1; // 숫자의 개수 int[][] dpMax = new int[n][n]; int[][] dpMin = new int[n][n];
  • n: 숫자의 개수. 연산자는 숫자보다 항상 하나 적으므로, 전체 배열 길이의 절반(arr.length / 2)에 1을 더해 계산합니다.
  • dpMax[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최대값을 저장합니다.
  • dpMin[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최소값을 저장합니다.
• for (int i = 0; i < n; i++) { dpMax[i][i] = Integer.parseInt(arr[i * 2]); dpMin[i][i] = Integer.parseInt(arr[i * 2]); }
  
  • 각 숫자는 연산 없이 자기 자신이므로, dpMax[i][i]와 dpMin[i][i]를 해당 숫자로 초기화합니다.

for (int len = 1; len < n; len++) {
    for (int i = 0; i < n - len; i++) {
        int j = i + len;
        dpMax[i][j] = Integer.MIN_VALUE;
        dpMin[i][j] = Integer.MAX_VALUE;

• len: 현재 계산하려는 구간의 길이. 길이가 1부터 시작하여, 점차 늘어나며 모든 가능한 구간을 탐색합니다.
• i: 구간의 시작점.
• j: 구간의 끝점. 구간 길이가 len이므로, j = i + len으로 계산.

for (int k = i; k < j; k++) {
    String operator = arr[k * 2 + 1];
    int maxLeft = dpMax[i][k];
    int minLeft = dpMin[i][k];
    int maxRight = dpMax[k + 1][j];
    int minRight = dpMin[k + 1][j];

• k: 구간을 분할하는 기준점.
  • arr[k * 2 + 1]에서 연산자(+, -)를 가져옵니다.
  • k를 기준으로 왼쪽(i에서 k)과 오른쪽(k+1에서 j)의 최대/최소값을 가져옵니다.
    • maxLeft, minLeft: 왼쪽 구간 최대/최소값.
    • maxRight, minRight: 오른쪽 구간 최대/최소값.

if (operator.equals("+")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
} else if (operator.equals("-")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
}

• 연산자에 따라 결과를 계산
  • + 연산: 양쪽 구간의 최대/최소값을 더합니다.
  • - 연산: 왼쪽 최대값에서 오른쪽 최소값을 빼거나, 왼쪽 최소값에서 오른쪽 최대값을 뺍니다.
• 계산 결과를 갱신하며, dpMax[i][j]는 가능한 최대값, dpMin[i][j]는 가능한 최소값을 유지합니다.
• return dpMax[0][n - 1];
  • dpMax[0][n-1]: 입력 배열 전체(0번째 숫자부터 마지막 숫자까지)의 가능한 최대값을 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

모든 항공권을 사용해 가능한 여행 경로를 찾고, 사전순으로 가장 앞선 경로를 반환합니다.

소스코드

import java.util.*;

class Solution {
    int n;
    boolean[] visited;
    ArrayList<String> arr = new ArrayList<>();
    
    public void dfs(int cnt, String start, String path, String[][] tickets) {
        if(cnt == n) {
            arr.add(path);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if (!visited[i] && tickets[i][0].equals(start)) {
                visited[i] = true;
                dfs(cnt+1, tickets[i][1], path + " " + tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        n = tickets.length;
        visited = new boolean[n+1];
        
        dfs(0, "ICN", "ICN", tickets);
        
        Collections.sort(arr);

        return arr.get(0).split(" ");
    }
}

코드 설명

• 전역변수 초기화
  • int n;
    항공권의 개수입니다.
  • boolean[] visited;
    항공권이 이미 사용되었는지 여부를 기록하는 배열입니다.
  • ArrayList<String> arr = new ArrayList<>();
    가능한 모든 경로를 저장하는 리스트입니다.

public void dfs(int cnt, String start, String path, String[][] tickets) {
    if(cnt == n) {
        arr.add(path);
        return;
    }

    for(int i = 0; i < n; i++) {
        if (!visited[i] && tickets[i][0].equals(start)) {
            visited[i] = true;
            dfs(cnt+1, tickets[i][1], path + " " + tickets[i][1], tickets);
            visited[i] = false;
        }
    }
}

• dfs 메소드
  • cnt == n이면 모든 항공권을 사용한 경로가 완성된 상태입니다.
  • 현재 위치 start와 일치하는 출발지를 가진 항공권을 찾습니다. 아직 사용되지 않은 항공권(!visited[i])만 선택합니다.
  • 선택한 항공권을 사용(visited[i] = true)하고, 목적지(tickets[i][1])로 이동합니다.
  • 재귀 호출이 끝난 후, 현재 항공권 사용 상태를 복구(visited[i] = false)하여 다른 경로를 탐색할 수 있도록 합니다.

public String[] solution(String[][] tickets) {
    n = tickets.length;
    visited = new boolean[n+1];

    dfs(0, "ICN", "ICN", tickets);

    Collections.sort(arr);

    return arr.get(0).split(" ");
}

• solution 메소드
  • 탐색을 시작하기 위해 dfs(0, "ICN", "ICN", tickets)를 호출합니다.
  • Collections.sort(arr)로 모든 경로를 사전순으로 정렬합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 검은색 선을 따라서만 이동할 수 있다는 것이 포인트였습니다.
예를 들어, 도형의 변이 다음과 같을 때 BFS/DFS를 할 때에 문제가 발생할 수 있습니다.
(4,3) -> (4,4) -> (5,3) -> ...
왜냐하면 저희가 현재까지 사용했던 dx/dy 테크닉을 사용하게 되면 (4,3)에서 (5,3)으로 바로 이동할 수 있기 때문입니다.

따라서 저는 Scale(2)을 두어 더 정교하게 이동할 수 있도록 하였습니다.
나중에 답을 구할 때에도 Scale의 값만큼 나누어줘야하는 주의사항이 있습니다.

소스코드

import java.util.*;

class Solution {
    
    int answer = 0;
    final int SIZE = 101;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int[][] map = new int[SIZE][SIZE];
    boolean[][] visited = new boolean[SIZE][SIZE];
    Queue<Pair> q = new LinkedList<>();
    
    class Pair {
        int x, y, cnt;
        
        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public boolean inRange(int x, int y) {
        return 0 <= x && x < SIZE && 0 <= y && y < SIZE;
    }
    
    public boolean canGo(int x, int y) {
        if(!inRange(x, y)) return false;
        if(map[x][y] != 1 || visited[x][y]) return false;
        return true;
    }
    
    public void bfs(int startX, int startY, int itemX, int itemY) {
        visited[startX][startY] = true;
        q.add(new Pair(startX, startY, 0));
        
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            
            if(cur.x == itemX && cur.y == itemY) {
                answer = cur.cnt/2;
                return;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(canGo(nx, ny)) {
                    q.add(new Pair(nx, ny, cur.cnt + 1));
                    visited[nx][ny] = true;
                }
            }
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        int n = rectangle.length;
        // 도형 바깥쪽은 1, 안쪽은 2
        // map이 2이면 도달 불가능
        // map부분이 이상함. 다시 생각하기. 그림 그려야 할 듯?
        for(int i = 0; i < n; i++) {
            int x1 = rectangle[i][0] * 2;
            int y1 = rectangle[i][1] * 2;
            int x2 = rectangle[i][2] * 2;
            int y2 = rectangle[i][3] * 2;
            for(int p = x1; p <= x2; p++) {
                for(int q = y1; q <= y2; q++) {
                    if(p == x1 || p == x2 || q == y1 || q == y2) {
                        if(map[p][q] == 0) {
                            map[p][q] = 1;    
                        }
                    } else {
                        map[p][q] = 2;
                    }
                }
            }
        }
        
        bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
        
        return answer;
    }
}

코드 설명

• Pair 클래스
  • 좌표를 나타내는 x와 y를 저장하는 좌표와 현재 step의 값을 저장하는 클래스입니다.
  • BFS 탐색 시 현재 위치를 나타내기 위해 사용됩니다.

public boolean inRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

public boolean canGo(int x, int y) {
    if(!inRange(x, y)) return false;
    if(visited[x][y] || globalMaps[x][y] == 0) return false;
    return true;
}

• inRange 메소드
  다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
• canGo 메소드
  다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)

public void bfs(int startX, int startY, int itemX, int itemY) {
    visited[startX][startY] = true;
    q.add(new Pair(startX, startY, 0));

    while(!q.isEmpty()) {
        Pair cur = q.poll();

        if(cur.x == itemX && cur.y == itemY) {
            answer = cur.cnt/2;
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if(canGo(nx, ny)) {
                q.add(new Pair(nx, ny, cur.cnt + 1));
                visited[nx][ny] = true;
            }
        }
    }
}

• bfs 메소드
  • 큐에 현재 위치와 이동 횟수를 저장합니다.
  • 상하좌우 네 방향을 탐색하며 이동 가능(canGo)한 경우 큐에 추가합니다.
  • 목표 위치(itemX, itemY)에 도달하면 이동 횟수 / 2한 값을 저장합니다.

public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
    int n = rectangle.length;
    // 도형 바깥쪽은 1, 안쪽은 2
    // map이 2이면 도달 불가능
    // map부분이 이상함. 다시 생각하기. 그림 그려야 할 듯?
    for(int i = 0; i < n; i++) {
        int x1 = rectangle[i][0] * 2;
        int y1 = rectangle[i][1] * 2;
        int x2 = rectangle[i][2] * 2;
        int y2 = rectangle[i][3] * 2;
        for(int p = x1; p <= x2; p++) {
            for(int q = y1; q <= y2; q++) {
                if(p == x1 || p == x2 || q == y1 || q == y2) {
                    if(map[p][q] == 0) {
                        map[p][q] = 1;    
                    }
                } else {
                    map[p][q] = 2;
                }
            }
        }
    }

    bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);

    return answer;
}

• solution 메소드
  • 모든 사각형(rectangle)을 테두리(1)와 내부(2)로 분류하여 map에 저장합니다.
  • 좌표 확장
    • 좌표를 *2하여 지도 상에서 모든 이동을 정수 단위로 표현합니다.
  • BFS를 이용해 시작 위치에서 목표 위치까지 탐색합니다.
•