https://www.acmicpc.net/problem/22866

문제

일직선으로 다양한 높이의 건물이 총 $N$개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다. $i$번째 건물 기준으로 $i - 1$, $i - 2$, ..., $1$번째 건물은 왼쪽에, $i + 1$, $i + 2$, ..., $N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 $L$이라고 가정하면 높이가 $L$보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가 $L$인 건물 뒤에 높이가 $L$이하인 건물이 있다면 가려져서 보이지 않는다.

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 $N$이 주어진다.

두번째 줄에는 $N$개의 건물 높이가 공백으로 구분되어 주어진다.

출력

  $i(1 \le i \le N)$번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 $i$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

풀이

[1] 나이브한 접근

z번째 빌딩보다 왼쪽에 있는 빌딩 중 높은 빌딩(y)을 찾는다.
y번째 빌딩보다 왼쪽에 있는 빌딩 중 높은 빌딩(x)을 찾는다.
x번째 빌딩보다 왼쪽에 있는 빌딩 중 높은 빌딩(w)을 찾는다.

위를 반복하면 z번째 건물에서 볼 수 있는 왼쪽 건물들을 알 수 있다.

[2] DP 관점

w > x > y > z 인 건물이 순서대로 주어 졌을 때,
각 건물에서 볼 수 있는 왼쪽 건물의 수는 아래 표와 같다.

만약 중간에 가장 높은 건물이 추가 된다면 어떻게 될까?

위의 그림과 같이 y와 z의 결과가 바뀌게 된다.

특정 빌딩(z) 보다 왼쪽에 높은 빌딩(y)이 있는 경우,
높은 빌딩(y)의 dp값 +1이 특정 빌딩(x)의 dp값이 된다.

[3] 결과

왼쪽 빌딩의 결과를 구한 것과 같이, 오른쪽 빌딩의 결과 또한 DP로 구한다.
출력 조건 중 아래와 같은 문구가 있다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 $i$번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다. DP 테이블이 갱신 되는 경우에 높은 빌딩(y)의 인덱스를 저장해두면 된다.

// 왼쪽 빌딩 확인 코드 중 일부
if(buildings[j] > buildings[i]){
    dp[i][0] = dp[j][0]+1;
    dp[i][2] = j+1; // 인덱스 저장
    break;
}
>
// 오른쪽 빌딩 확인 코드 중 일부
if(dp[i][0] == 0 || (i - dp[i][2]+1) > (j-i)){
    dp[i][2] = j+1;
}

[4] 최적화

특정 빌딩(z) 보다 왼쪽에 높은 빌딩(y)이 있는 경우는 반복문을 통해 알 수 있다. 단, 특정 빌딩(z)이 왼쪽에 있는 모든 빌딩 보다 높은 빌딩이라면 어떻게 될까?
0번째 빌딩까지 높이를 다 확인해야 한다!

이는 0부터 i번째 빌딩까지 높이를 확인할 때, 가장 높은 빌딩의 높이를 변수에 저장해두면 최적화 할 수 있다.

if(max < buildings[i]){
    max = buildings[i];
    continue;
}

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_22866_탑보기 {

    static int N;
    static int[] buildings;
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력| N, buildings
        N = Integer.parseInt(br.readLine()); 
        StringTokenizer stk = new StringTokenizer(br.readLine());

        buildings = new int[N];
        for(int i=0; i<N; i++)  buildings[i] = Integer.parseInt(stk.nextToken());

        // 초기화| dp
        dp = new int[N][3]; // [i][0]: i기준 왼쪽 빌딩, [i][1]: i기준 오른쪽 빌딩, [i][2]: 가장 가까운 빌딩

        // 왼쪽 빌딩 확인
        int max = buildings[0];
        for(int i=1; i<N; i++){
            if(max < buildings[i]){
                max = buildings[i];
                continue;
            }

            for(int j=i-1; j>=0; j--){
                if(buildings[j] > buildings[i]){
                    dp[i][0] = dp[j][0]+1;
                    dp[i][2] = j+1;
                    break;
                }
            }
        }

        // 오른쪽 빌딩 확인
        max = buildings[N-1];
        for(int i=N-2; i>=0; i--){
            if(buildings[i] > max){
                max = buildings[i];
                continue;
            }

            for(int j=i+1; j<N; j++){
                if(buildings[i] < buildings[j]){
                    dp[i][1] = dp[j][1]+1;

                    if(dp[i][0] == 0 || (i - dp[i][2]+1) > (j-i)){
                        dp[i][2] = j+1;
                    }

                    break;
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            int sum = dp[i][0] + dp[i][1];

            sb.append(sum).append(" ");
            if(sum != 0) sb.append(dp[i][2]);
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

말 그대로 정적인 HTML 컨텐츠를 제공하는 것이다.Spring boot는 tomcat에 의해 적절한 컨트롤러가 로드된다. 클라이언트의 요청과 맞는 스프링 컨테이너가 없다면 정적 컨텐츠가 로드된다.

기존에 작성된 HTML을 따로 가공하지 않고, 순수 제공하는 것으로 Web Server에서 제공하는 경우 사용할 수 있다. Spring 정적 컨텐츠는 resources하위 폴더를 칭한다. 단순 static 폴더만을 지칭하지 않는다. 물론 변경도 가능하다.

spring.mvc.static-path-pattern=/resources/**

나중에 Web Serverd와 WAS를 정리해둬야겠다.

[ MVC & 템플릿 엔진]

MODEL VIEW CONTROLLER의 약자로, 컨텐츠 제공을 위한 3가지 컴포넌트를 활용한다. Model: 컨텐츠의 정보를 나타내며, 데이터의 가공을 책임지는 컴포넌트이다. View: 컨텐츠의 사용자 인터페이스 부분을 담당한다. 데이터를 기반으로 사용자들이 볼 수 있는 화면을 구성한다. Controller: 데이터와 사용자 인터페이스를 연결한다. 즉, 모델과 뷰를 연결한다.

스프링에서는 아래의 사진과 같이 tomcat에 의해 스프링 컨테이너가 적절한 controller를 로드한다. controller는 모델을 viewResolver에게 전달한다. 템플릿 엔진(Thymeleaf)가 동적으로 view를 처리하고 사용자에게 보여진다. 즉, 서버 사이드 랜더링 방식으로 동작한다.

[ API ]

클라이언트에게 데이터만을 보낸다. XML, JSON과 같은 데이터 형식을 보냄으로서 클라이언트에게 랜더링을 맡긴다. 즉, 클라이언트 사이드 랜더링 방식으로 동작하게끔 한다.

스프링은 객체를 ResponseBody에 반환한다. 이때, 당연하게도 객체를 바로 보낼 순 없다. 스프링 컨테이너는 HttpMessageConverter를 선택해 객체를 컨버팅 할 수 있도록한다. 기본 문자 처리는 StringHttpMessageConverter, 기본 객체 처리는 MappingJackson2HttpMessageConverter를 사용한다.

참고

김영한님의 스프링 입문 - 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술을 참고해 작성했습니다.

[ 프로젝트 생성 ]

start spring io로 접속한다. 아래의 사진으로 한번에 이해 가능하다.

위의 사진처럼 뭐가 많지만 사실 간단하다. 5가지만 잘 선택해주면 된다.

• project
• Language
• Spring Boot 버전
• Project Metadata
• Dependencies

[ Project ]

Project를 통해 빌드 관리 도구를 선택할 수 있다. Gradle과 Maven의 차이는 Maven과 Gradle의 개념 및 비교를 참고

[ Spring Boot ]

Spring Boot에서 스프링 부트의 버전을 선택한다.

• Snapshot: 데일리 빌드 버전, 안정화가 되어있지 않다.
• GA(General Availability): 정식 릴리즈 버전
• M(Milestone): 프로젝트의 주기마다 배포하는 버전, 주요 기능이 구현되면 릴리즈를 진행하고 개발자들에게 피드백을 받는다.
• RC(Release Cadidate): M의 상위 버전으로, 정식 릴리즈는 아니다. RC버전을 거치고 GA로 배포된다.

[ Project Metadata ]

프로젝트를 설명하는 데이터이다.

• Group: 기업 도메인명
• Artifact: Build 결과물(프로젝트명)
• Name: Build 결과물(프로젝트명)
• Description: 프로젝트 설명
• Package name: 루트 패키지. Group.Artifact가 자동으로 입력된다.

[ Dependencies ]

프로젝트에 필요한 라이브러리 선택한다.

스터디 형식

• 문제는 주5회 출제(스터디원)
• 각 문제마다 이슈로 생성(관리자)
• 주차별 마일스톤을 생성하고, 해당 주의 이슈와 연결(관리자)
• 문제풀이 Pull Request(스터디원)
• Approve된 PR merge(관리자)

1. 마일스톤 생성

월요일마다 마일스톤을 생성한다. Github-Issue-Milestones에서 생성할 수 있다. Title은 주차에 맞게 설정하고, Due date를 일요일로 설정한다.

2. 이슈 생성

평일 스터디원이 문제를 출제하면 Issue를 생성하고 마일스톤과 연결한다. Github-Issue에서 생성하고, 템플릿을 사용해 문제에 맞게 {}를 수정한다.

3. Pull Request Merge

스터디원이 문제를 해결하고 PR을 요청하면, 관리자는 확인하고 merge한다. PR마다 지정된 페어가 코드 리뷰를 통해 Approve를 해주어야 merge 가능하다.

Files changed에서 파일명(네이밍,주차,특수문자 여부)이 적절한지 확인한다. 위의 조건들이 만족 했다면, 아래 3가지를 설정한 뒤 merge한다.

• Labels: 풀이에 사용된 알고리즘
• Assignees: PR작성자
• Milestone: 해당 주차

Action을 사용해 Assignees와 Milestone 할당을 자동화하려했지만 실패했다.. 성공하면 수정해야지

4. 이슈 & 마일스톤 close

일주일이 마무리 되면 생성한 이슈와 마일스톤을 close한다.

1. [PerfumePedia] SearchResultService 테스트
2. [PerfumePedia] PerfumeDetailService 테스트
3. [SSAFY] PT면접 주제(OTT) 내용 추가
4. [SSAFY] 면접 예상 질문 확정답안 준비

해결한 일

기존 코드

매개변수로 객체의 타입과 해당 객체의 ID가 전달된다. WordType은 PERFUME, BRAND, NOTE를 name으로 갖는 enum이다

List<Word> findByTypeAndTypeId(Long typeId, WordType wordType)

public List<Word> findByTypeAndTypeId(Long typeId, WordType wordType){
    String jpql = "SELECT w FROM Word w " +
            "LEFT JOIN w.brand b " +
            "LEFT JOIN w.note n " +
            "LEFT JOIN w.perfume p " +
            "WHERE w.wordType = :wordType " +
            "AND (b.id = :id OR n.id = :id OR p.id = :id)";

    return em.createQuery(jpql, Word.class)
            .setParameter("wordType", wordType)
            .setParameter("id", typeId)
            .getResultList();
}

Join을 사용했고, 결과를 정상적으로 반환 받을 수 있었다. 하지만 Hibernate에 의해 binding 되는 값이 4개이고, where절의 and와 or를 줄일 수 있을 것 같았다.

수정된 코드

WordType의 name을 적극 활용하기로 했다.

WordType은 PERFUME, BRAND, NOTE를 name으로 갖기에, Word 테이블의 perfume, brand, note 열의 이름과 같다.(대문자,소문자 차이)

public List<Word> findByTypeAndTypeId(Long typeId, WordType wordType) {
        String jpql = "select w from Word w where " + "w." +
                wordType.name().toLowerCase() +
                ".id = :id";

        return em.createQuery(jpql, Word.class)
                .setParameter("id", typeId)
                .getResultList();
    }

Word 테이블에서 Type에 맞는 열만을 비교하므로, 쿼리를 줄일 수 있었다.

결론?

이 방법이 더 나은 로직인지는 확실치 않다. 다만, 확실히 쿼리가 줄었고 고민해서 코드를 고안해냈으니 다음엔 더 좋은 방법이 떠오르지 않을까.. 하는 기대를 가져보자!

1. [PerfumePedia] Contoller Service 테스팅(진행중) 2. [SSAFY] PT면접 주제(OTT) 내용 추가

해결한 일

1. Controller Service 테스팅

• WordRepository JPQL 쿼리 수정

  • Join 사용 대신, Enum의 값 자체를 사용하도록 수정했다.

    public List<Word> findByTypeAndTypeId(Long typeId, WordType wordType) {
      String jpql = "select w from Word w where " + 
              "w." + wordType.name().toLowerCase() +
              ".id = :id";
    
      return em.createQuery(jpql, Word.class)
              .setParameter("id", typeId)
              .getResultList();
    }

  • [Spring Boot] JPA - JPQL 동적쿼리에서 자세히 볼 수 있다.

  • AutoCompleteService 테스트 완료

    • 자동완성 기능에서 반환값 수정: 별칭 값에서 이름 값으로 수정

  • 자동완성 기능 → 정상

  • 가중치에 따른 정렬 → 정상

프로젝트 진행 중 A브랜치와 B브랜치를 병합하려 했는데 오류가 발생했다. 그리고 브랜치 그래프가 아래와 같았다. (사실 오류는 다른 부분에서 발생했다. 방법은 해결로!)

동일한 내용의 커밋이 각 브랜치에 따로 존재했다. 이유를 알아보자

커밋 순서가 바뀌었다.

커밋을 자세히 보면 순서가 이상하다. 브랜치별로 구분하기 편하도록 색상으로 나눴다.

refactor: AutoCompleteWordDto 수정 커밋 내용이 A브랜치에서는 feat: Service 기반 작성 커밋 보다 하위에 위치하고 B브랜치에서는 feat: Service 기반 작성 커밋 보다 상위에 위치한다.

왜 바뀌었지?

왜 이러한 문제가 발생한건지 chatGPT에 물어봤는데 아래와 같았다.

chatGPT의 답변을 기반으로 했을때, 가능성 있는건 Rebase, Amend, ForcePush이다. 확실치는 않지만 commit중 amend를 진행한 적이 있는데, 그때 순서가 바뀌었을 것이라고 추측한다.

해결

기본적으로 커밋 순서가 다르다 해서 git의 병합이 실패하지는 않는다. 그냥 merge해도 잘 작동한다.

나도 병합할 때 오류가 발생해서 원인이 커밋 순서에 있는 줄 알았지만, 사실 문제는 따로 있었다.

# Conflicts:
#    src/main/java/com/perfumepedia/PerfumePedia/service/SearchResultService.java

각 브랜치에서 SearchResultService.java 코드가 둘 다 수정되어 오류가 발생했을 뿐... 문제를 알았으니 됐다!

1. [PerfumePedia] Controller 브랜치 병합 충돌 해결(완료) 2. [PerfumePedia] Service 기반 작성

해결한 일

1. Controller 브랜치 병합 충돌

• 동일한 브랜치를 팀원과 같이 수정하다보니, 브랜치 병합에서 충돌이 일어났다. git에서 병합오류와, 사진과 같이 같은 내용의 커밋이 2번 나타났다.

• git rebase를 통해 main과 병합 시켜 해결했다. [Git] 원격 저장소의 브랜치가 origin에 없을 때 해결

• 모든 브랜치를 다 rebase 시켜서 늘어난 내 PR은 덤..

  
  

2. Service 기반 작성

1. [PerfumePedia] React - Spring boot Cors 해결 (완료) 2. [PerfumePedia] Controller를 위한 Service 기반 작성 (진행중)

해결한 일

1. React - Spring boot Cors 해결

• React에 아래의 코드 추가

  const { createProxyMiddleware } = require('http-proxy-middleware');

• [Spring & React 개발환경 연동] (https://velog.io/@kyeongzow/Spring-React-%EA%B0%9C%EB%B0%9C%ED%99%98%EA%B2%BD-%EC%97%B0%EB%8F%99)에서 자세히 볼 수 있음(경은 땡큐)

  
  

2. Controller를 위한 Service 기반 작성

• Dto를 감싸기 위한 Record ResponseData 생성 Record에 대해 공부 필요.

  public record ResponseData<T>(T data) {
    /**
     * 생성 및 초기화 진행
     * @param data T 객체
     */
    public ResponseData {
    }
  }
  

• 자동완성 서비스 작성

  @Service
  @Transactional(readOnly = true)
  @RequiredArgsConstructor
  public class AutoCompleteService {
  
    private final WordRepository wordRepository;
  
    /**
     * 사용자가 입력한 keyword에 해당하는 검색어목록을 반환하는 함수입니다.
     * <p> word 엔티티로부터 weight 기준 내림차순으로 반환합니다.
     * @param keyword 사용자가 입력한 keyword입니다. 예) 조말론
     * @return AutoCompleteWordDto 객체를 반환합니다.
     */
    public ResponseData findKeywords(String keyword){
        AutoCompleteWordDto autoCompleteWordDto = new AutoCompleteWordDto();
  
        // WordRepository #findByAlias 사용
        // #findByAlias에 의해 Word 객체 List 반횐됨
        // 자동으로 5개 이하의 결과가 반환되며, desc sort 돼 있음
        List<Word> words = wordRepository.findByAlias(keyword);
  
        // AutoCompleteWordDto #set 메소드들을 활용해 초기화 진행
  
        // ResponseData 객체화
        ResponseData data = new ResponseData(autoCompleteWordDto);
  
        // 객체화한 ResponseData 반환
        return data;
    }
  }

1. [PerfumePedia] Repository 코드 작성(완료) 2. [PerfumePedia] Service 코드 틀 작성(완료)

해결한 일

1. Repository 코드 작성

• @Repository 를 사용해 작성 완료
• Notion - Repository 설계 참고
• 추후 extends로 수정 여부 판별 및 test 예정

2. Service 코드 틀 작성

• 수집한 데이터를 DB에 저장하기 위한 Service 작성
  • Brand Service
  • Note Service
  • Perfume Service
  • PerfumeNote Service
  • Word Service

• 깃 원격 저장소 새로운 브랜치 생성시 local 파일의 remote와 연동되지 않는 문제 해결 [Git] 원격 저장소의 브랜치가 origin에 없을 때 해결

원격 저장소에 'feature/service' 브랜치를 생성했고, 이를 이용해서 local 브랜치도 생성할 생각이었다.

하지만, 기존에 작업하던 파일에는 새로 생성한 'feature/service' 브랜치가 보이지 않았다...

멍청한 해결(Clone)

원격 저장소에서 새로 Clone 해온다! 간단 명료하다.

기존에 작업하던걸 Commit & Push 하고, 새로 Clone 하면 된다. 근데.. 이럴거면 Git 왜 쓰지?

해결(Update)

origin을 업데이트 시키면 된다.

커맨드 라인으로 처리한다면 아래의 명령어를 입력하면 된다.

git remote update

Intellij를 사용중이라면 하단 오른쪽 Git Branches에서 파란색 화살표를 클릭하면 된다.

그럼 아래와 같이 Remote Branches에 'feature/service'가 보인다!

이 중 Service 작성을 재우에게 맡기기로 했다.

Service의 역할

1. 수집 데이터 저장

Domain과 Repository를 기반으로 수집한 데이터 저장 로직을 처리해야한다.

• Json파일을 읽고, 데이터베이스에 저장해야하는데 이 과정에서 검증이 필요하다.
• 기존에 데이터베이스에 저장된 내용인지, 수정된 내용이 있는지 확인 해야한다.

2. DTO 생성 및 초기화

데이터베이스에 저장된 데이터를 DTO에 저장하고, 반환할 수 있어야한다.

• Repository를 이용해 데이터베이스에 저장된 값을 Domain으로 읽고 이를 DTO에 저장해야한다.
• Controller에 따라 필요한 DTO가 다르므로, Controller와 상의해서 미리 DTO를 설계 해야한다. -> 이부분은 경은이가 미리 작성해 뒀다.

고려사항

1. TDD

코드 작성시 누락된 부분이 생길 수 있으므로 TDD를 기반으로 작성한다.

• 기능 테스트 케이스를 작성한다.
• Service 코드를 아직 작성하지 않았으니, 오류가 발생한다.
• 기본적인 Service 코드를 작성하고, 오류를 해결한다.
• refactoring을 통해 코드를 개선한다.
• 다음 기능을 위와 같이 반복하여 작성한다.

2. 주석작성

자바의 /**/ 주석을 이용하여 작성한다.

1. 카카오 인턴십 지원(완료) 2. PerfumePedia 프로젝트 feature/domain 병합(완료) 3. PerfumePedia 프로젝트 Service 설계 필수 내용 작성 및 전달(Service 코드 팀원이 작성 예정)(완료) 4. PerfumePedia 프로젝트 Repository 코드 작성

해결한 일

1. 카카오 인턴십 지원

• 서버 포지션으로 지원 완료
  

2. PerfumePedia 프로젝트 feature/domain 병합

• feature/domain 브랜치를 main 브랜치로 병합 완료
• MySQL Workbanch에서 스키마 및 테이블 생성 확인 완료
  

3. PerfumePedia 프로젝트 Service 설계 필수 내용 작성 및 전달

• 설계에 필요한 TDD와 주석 관련 내용 정리 [PerfumePedia] JPA Service 설계

내가 왜 이걸 사용했지? 그리고 왜 id를 long이 아닌 Long이지? 라는 의문이 들었다.

    @Entity
    @NoArgsConstructor(access = AccessLevel.PROTECTED)
    public class Perfume {
        @Id
        @GeneratedValue(strategy = GenerationType.IDENTITY)
        @Column(name = "PERFUME_ID")
        private Long id;
    }

    @Test
    public void ID_자동생성_확인() throws Exception{
        //given
        String name = "향수이름";

        //when
        Perfume perfume = new Perfume(name);

        //then
        assertNull("id는 자동 생성됩니다.", perfume.getId());
    }

Long과 long의 차이

long은 원시 타입(primitive type), Long은 래퍼 클래스(Wrapper class) 이다.

id를 long으로 사용하는 경우, 별도의 초기화 과정이 없다면 0으로 초기화 된다. 반면, Long으로 사용하는 경우엔 초기값은 Null이다.

그래서 test case에서 assertNull을 사용했다!

참조

인프런 질문 - Long 타입에 대한 질문입니다.

1. 당근 Winter Tech Internship 지원하기(완료) 2. PerfumePedia 프로젝트 Domain 코드 작성(완료) 3. PerfumePedia 프로젝트 Repository 코드 작성 3. PerfumePedia 프로젝트 Service 설계

해결한 일

1. 당근 Winter Tech Internship 지원하기

2. PerfumePedia 프로젝트 Domain 코드 작성

Domain 작성 중 정리한 내용

• [Spring Boot] JPA - Entity 설계에서 Long과 long의 차이

[데이터 전처리]에서 자세히 볼 수 있다.

수집한 데이터를 기반으로 학생들이 이용하는 정류소와 이를 경유하는 노선을 추렸다. 정류소 8개와 이를 경유하는 노선 8개이다.

정류소

• 중화중학교삼거리(면목본동파출소 방면)
• 용마문화복지센터(서일대학교 방면)
• 용마문화복지센터(종점 방면)
• 서일대정문(중화중학교삼거리 방면)
• 서일대학교(혜원여중고후문 방면)
• 서일대학교(용마문화복지센터 방면)
• 새마을금고(서일대정문 방면)
• 공판장(새마을금고 방면)

노선

• 271
• 320
• 1213
• 2012
• 2013
• 2212
• 2230
• 중랑02

이에 대한 정보를 JSON파일로 저장했다. 형식은 아래와 같다.

{
  "bus_stops": [
    {
      "stop_name": "정류소 이름",
      "stop_number": "정류소 번호",
            "x_coordinate": "정류소 x 좌표 값",
            "y_coordinate": "정류소 y 좌표 값",
      "next_stop_name": "다음 정류소 이름",
      "routes": [
        {
          "route_name": "노선명",
          "route_number": "노선 고유번호",
                    "departure":  "기점 출발여부"
        },
        {
          "route_name": "노선명",
          "route_number": "노선 고유번호",
                    "departure":  "기점 출발여부"
        }, ...(다음 노선)...
      ]
    },
    ...(다음 정류소)...
  ]
}

2. 데이터베이스 설계

[데이터베이스 설계]에서 자세히 볼 수 있다.

“정류소”와 “노선”에 대해 테이블을 설계했다. “정류소”와 “노선”의 다대다 관계를 해결하기 위해 “경유노선” 테이블을 설계했다.

기점 출발 노선인 경우 BIS를 사용해 정보를 요청 하더라도 대부분 “도착 정보 없음” 이라는 값만 출력되므로 이를 해결하기 위해 “배차정보”테이블을 설계했다. “경유노선”의 ‘기점 출발 노선’ 값이 true인 경우에 한하여 “배차정보”테이블에 값을 채울 예정이다.

20초마다 BIS에 접속해 배차가 되었는지 값을 얻어와 ‘접속시간’, ‘남은시간’을 저장한다. 이를 이용해 인공지능을 학습해 남은시간을 예측한다.

매번 버스를 통해 통학하면서 불편한점이 있다.

도착 정보가 없다.... 아무리 새로고침을 해도 버스가 언제 올지 알 수가 없다.. 학교 바로앞 버스 정류소가 기점이기에, 내가 타는 2013번 버스는 언제 올지 알 수 없고 나는 그저 기다렸다.

3년동안 너무나 불편했다 그러니까 내가 고쳐야지

모바일 기반 웹 서비스를 만들어보자! 우리대학 주변 정류소를 경유하는 버스의 도착 예정 시간을 알려주고, 도착 정보가 없다면 인공지능의 힘을 빌려보자

1. 문제점 파악

버스 운행정보 소외지역을 위한 버스정보시스템(BIS) 개선에 대한 제언 을 참고해 작성했다.

1.1. BIS(버스정보시스템)의 한계

각 지자체에서는 버스정보시스템(Bus Information System, 이하 BIS)를 제공하고있다. BIS는 해당 정류소 이전에 운행중인 버스가 있는 경우에 한하여 버스 도착예정 시간을 제공한다.

이는 정류소 이전에 운행중인 버스가 없는 경우, 버스의 도착예정시간을 제공할 수 없다는 문제가 있다.

기점 주변 정류소는 이러한 문제로 인해 도착예정정보를 얻지 못한채 “도착 예정 정보 없음”이라는 문구만을 반복한다.

2.2. 서일대학교 주변 버스

서일대학교의 경우 근처 2개의 기점이 존재한다. 진로아파트앞.종점과 용마문화복지센터

2개의 기점으로부터 출발하는 버스는 총 4개이다.

3.3. 결론

서일대학교를 중랑02, 271, 1213, 2013을 이용해 통학하는 학생들의 경우 버스의 도착예정시간을 확인하지 못한채 기다리는 경우가 허다하다.

서울의 경우 버스의 운행시간과 배차간격에 대한 정보만을 제공하기에, 기점 주변 정류소는 도착 예정 시간을 제공할 수 없고 이로인해 해당 정류소를 이용하는 사람들은 기다림에만 집중할 수 밖에 없다.

대략적인 도착 예정 시간을 알 수 있다면 다른 교통수단을 이용하거나 시간을 효율적으로 사용할 수 있을 것이다.

그렇기에 기점에서 출발하는 버스의 시간을 예측하는 서비스가 필요하다.

2. 서비스 기능

• 정류소 위치 제공

  • 네이버 혹은 카카오 지도를 활용해 주변 정류소 위치 제공

• 버스 도착 예정 시간 제공

  • 정류소별 버스 도착 예정 시간 제공
  • BIS를 통해 예정 시간을 제공할 수 있는 경우, BIS 활용

• 버스 도착 예측 시간 제공

  • BIS를 통해 제공할 수 없는 경우, 인공지능을 통해 예측
  • 예측 시간 제공시, 예측 확률 같이 제공
  • ℹ️와 같은 아이콘을 추가해 예측 확률을 확인할 수 있도록 함

• 선호 정류소 및 노선 저장 기능

  • 사용자가 선호하는 정류소를 체크한 경우 웹 페이지 접속 시 해당 정류소를 먼저 제공함
  • 사용자가 선호하는 노선이 있는 경우 정류소 선택 시 해당 노선의 정보가 최상단에 위치함

사실 기능상 별 내용은 없다. BIS를 사용해서 도착 정보를 제공하는 서비스는 워낙 많기 때문.

주 기능은 예측 시간 제공에 있다. 예정이아닌 '예측'! 인공지능이 잘 작동하리라 믿어보자..

3. 예상 레이아웃

왼쪽 레이아웃 선택해 제작하기로 했다.

오른쪽은 기획하자마자 내가 디자인 한건데 동기가 공대냄새 난다고 바꿔줬다. 고마워...

4. 데이터 수집

공공데이터와 네이버 지도에서 버스 정류소와 버스에 대한 정보를 수집했다.

4.1. FILE: 버스 노선별 ID 수집

• 공공데이터 - 서울특별시_버스노선ID 정보에서 버스 노선별 ID값이 포함된 엑셀 파일 수집 했다.
• 2023년 10월 26일자 최신 데이터 다운로드
• 파일 이름은 [서울시버스노선ID정보(20231026)]이며, 내용은 아래와 같다.

4.2. FILE: 버스 정류소 ID 수집

• 서울특별시_버스정류소 좌표 데이터에서 버스 정류소별 번호값이 포함된 엑셀 파일 수집했다.
• 2023년 10월 26일자 최신 데이터 다운로드
• 파일 이름은 [서울시버스정류소위치정보(20231026)]이며, 내용은 아래와 같다.

4.3. API: 노선의 전체 정류소 도착 예정 정보 조회

• 서울특별시_버스도착정보조회 서비스에서 노선별 정류소 도착 예정 정보를 얻을 수 있다.
• 한 번의 검색을 통해 한 노선(버스)의 전체 위치를 확인할 수 있다.
• API의 [getArrInfoByRouteAll] 이용

4.4. API: 정류소 버스 도착 정보 조회

• 서울특별시_정류소정보조회 서비스에서 정류소별 버스 도착 정보를 얻을 수 있다.
• API의 [getStationByUid] 이용

4.5. 기타

학교 근처에 어떠한 정류소와 노선이 있는지 확인하기 위해 네이버 지도를 활용했다.

• 정류소: 중화중학교삼거리[07436: 면목본동파출소 방면]
  • 노선: 320, 2012, 중랑02
• 정류소: 면목본동파출소[07315: 중화중학교.다문화가족지원센터 방면]
  • 노선: 320, 2012
• 정류소: 용마문화복지센터[07195: 서일대학교 방면]
  • 노선: 271, 1213, 2013, 2212, 2230, 중랑02 등등 여러개

마무리

사실 9월에 이 프로젝트를 시작 했다가 바로 폐기했었다. 기획없이 바로 도메인부터 우다다 작성했었는데 서비스에서 생각해야될게 많아지니까 하기가 싫어지더라..

현재 팀 프로젝트를 하는 것이 있는데, 기획부터 쌓아올리니까 팀원들이랑 소통도 잘 되고 고려해야할게 명확히 보이니까 오히려 편했다.

그래서 이번에 기획, 설계부터 차근차근 시작해보려 한다.

인공지능을 잘 학습시킬 수 있을지 모르겠지만.. 우선 해보자!

프로젝트 노션 주소

여기!

카카오 로그인 공식문서와 카카오 로그인 REST API에서 OAuth2.0 로그인에 대해 자세한 내용을 볼 수 있다.

1. 카카오 개발자 페이지

1.1. 회원가입 및 로그인

Kakao Developers에 접속해 회원가입을 하고 로그인한다.

1.2. 애플리케이션 추가

카카오 개발자 기능을 사용하기 위해 애플리케이션을 추가한다.

아이콘은 선택사항이며, 추후 비지니스 앱으로 전환시 아이콘은 필수다. 비지니스 앱으로 전환시 사용자의 정보를 더 요구할 수 있다.(이메일, 이름 등..)

앱 설정 > 앱 키에서 Rest API 키를 확인할 수 있다. Rest API 키가 서버에서 사용할 client_id값으로 사용된다.

1.3. 로그인 활성화 및 Redirect URI 설정

제품 설정 > 카카오 로그인에서 활성화를 설정하고 Redirect URI를 설정한다. local 환경에서 테스트하기 위해 host와 port를 localhost와 8080으로, path는 /local/oauth2/code/kakao로 설정한다.

1.4. 보안 설정

제품 설정 > 보안에서 client secret을 발급받고, 활성화 상태를 사용함으로 설정한다. 서버에서 client_secret 값으로 사용된다.

1.5. 동의항목 설정

제품 설정 > 동의항목에서 필수 동의 항목과 선택 동의 항목을 설정한다. 닉네임과 프로필 사진은 접근 권한이 있으나 이메일, 이름 등 사용자의 정보를 더 얻고싶다면 비지니스 앱으로 등록해야한다.

아이콘을 등록하면 이메일까지는 얻을 수 있지만 그 이후에는 사업장을 등록해야하더라.. 우선 이메일까지만 해보자..

2. Spring boot 설정

2.1. 의존성 추가

설정한 의존성은 아래와 같다.

• Spring Web
• Thymeleaf
• Spring Security
• OAuth2 Client

2.2. yml 수정

spring:
  security:
    oauth2:
      client:
        provider:
          kakao:
            authorization-uri: https://kauth.kakao.com/oauth/authorize
            token-uri: https://kauth.kakao.com/oauth/token
            user-info-uri: https://kapi.kakao.com/v2/user/me
            user-name-attribute: id
        registration:
          kakao:
            client-id: 여기에 Client Id 입력
            client-secret: 여기에 Security Id 입력
            client-authentication-method: client_secret_post
            redirect-uri: https://localhost:8080/login/oauth2/code/kakao
            authorization-grant-type: authorization_code
            client-name: kakao
            scope:
              - profile_nickname
              - profile_image
              - account_email(필요시 동의항목에서 설정한 ID 임력)

client-id와 security-id, redirect-uri를 개발자 페이지에서 설정한 것과 같은 값으로 설정하면 된다.

마지막 scope 값은 동의항목에서 필수 또는 선택으로 설정한 항목의 ID를 입력하면 된다. 비지니스 앱을 등록한 경우 profile 외의 다른 값들을 요청할 수 있다.

2.3. 로그인 페이지 렌더링: Contoller와 html

LoginContoller.java와 login.html 파일을 생성한다. html파일의 경우 src/main/resources/templates 디렉토리에 생성한다.

카카오 로그인을 클릭시 /oauth2/autorization/kakao로 요청을 보내게 된다. 이는 OAuth2 Client 의존성 기본 설정 경로이며, 필요시 수정할 수 있다.

2.4. Service

package com.oauth_kakao.service;

import org.springframework.security.core.GrantedAuthority;
import org.springframework.security.core.authority.AuthorityUtils;
import org.springframework.security.oauth2.client.userinfo.DefaultOAuth2UserService;
import org.springframework.security.oauth2.client.userinfo.OAuth2UserRequest;
import org.springframework.security.oauth2.core.OAuth2AuthenticationException;
import org.springframework.security.oauth2.core.user.DefaultOAuth2User;
import org.springframework.security.oauth2.core.user.OAuth2User;
import org.springframework.stereotype.Service;
import java.util.List;

@Service
public class OAuth2UserService extends DefaultOAuth2UserService {
    @Override
    public OAuth2User loadUser(OAuth2UserRequest userRequest) throws OAuth2AuthenticationException {
        OAuth2User oAuth2User = super.loadUser(userRequest);

        // Role generate
        List<GrantedAuthority> authorities = AuthorityUtils.createAuthorityList("ROLE_ADMIN");

        // nameAttributeKey
        String userNameAttributeName = userRequest.getClientRegistration()
                .getProviderDetails()
                .getUserInfoEndpoint()
                .getUserNameAttributeName();

        // DB 저장로직이 필요하면 추가

        return new DefaultOAuth2User(authorities, oAuth2User.getAttributes(), userNameAttributeName);
    }
}

OAuth2UserService 클래스를 생성한다.(DefaultOAuth2UserService 클래스 상속)

package com.oauth_kakao.security;

import com.oauth_kakao.service.OAuth2UserService;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.http.MediaType;
import org.springframework.security.config.annotation.method.configuration.EnableMethodSecurity;
import org.springframework.security.config.annotation.web.builders.HttpSecurity;
import org.springframework.security.oauth2.core.user.DefaultOAuth2User;
import org.springframework.security.web.SecurityFilterChain;
import org.springframework.security.web.authentication.AuthenticationSuccessHandler;
import java.io.PrintWriter;
import java.nio.charset.StandardCharsets;

@Configuration
@EnableMethodSecurity
public class SecurityConfig {
    private final OAuth2UserService oAuth2UserService;

    public SecurityConfig(OAuth2UserService oAuth2UserService) {
        this.oAuth2UserService = oAuth2UserService;
    }

    @Bean
    public SecurityFilterChain securityFilterChain(HttpSecurity http) throws Exception {
        http.csrf().disable();
        http.authorizeHttpRequests(config -> config.anyRequest().permitAll());
        http.oauth2Login(oauth2Configurer -> oauth2Configurer
                .loginPage("/login")
                .successHandler(successHandler())
                .userInfoEndpoint()
                .userService(oAuth2UserService));

        return http.build();
    }

    @Bean
    public AuthenticationSuccessHandler successHandler() {
        return ((request, response, authentication) -> {
            DefaultOAuth2User defaultOAuth2User = (DefaultOAuth2User) authentication.getPrincipal();

            String id = defaultOAuth2User.getAttributes().get("id").toString();
            String body = """
                    {"id":"%s"}
                    """.formatted(id);

            response.setContentType(MediaType.APPLICATION_JSON_VALUE);
            response.setCharacterEncoding(StandardCharsets.UTF_8.name());

            PrintWriter writer = response.getWriter();
            writer.println(body);
            writer.flush();
        });
    }
}

Security config를 작성한다. 로그인 페이지를 /login으로 설정하고, 정상 실행시 id를 반환한다.

2.5. 실행

localhost:8080/login 접속시 왼쪽과 같은 창이 출력된다. 카카오 로그인 클릭후 로그인 하게 되면 우측과 같이 id값이 반환된다.

참고자료

카카오 로그인 공식문서 Spring Boot 3.x 버전에서 OAuth2 라이브러리를 이용하여 카카오 로그인 구현 및 OAuth2 동작원리 살펴보기 [Spring Boot] 카카오 OAuth2.0 구현하기

https://www.acmicpc.net/problem/14002

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

풀이

이전 문제 가장 긴 증가하는 부분 수열과 같이 DP를 사용한다.

수열에서 어떠한 수(x)는 왼쪽에 위치한 수들과 비교해 큰 경우 "증가하는 부분 수열"을 이룰 수 있다.

이때, "가장 긴" 증가하는 부분 수열을 찾아야 하므로 왼쪽에 위치한 수들 중 "가장 길고, 어떠한 수(x)보다 작은" 수을 찾아 연결해야 한다.

그림에서 30은 10, 20, 10과 부분수열을 이룰 수 있다. 그리고 20은 10과 부분수열을 이룰 수 있다. 30을 기준으로 10-20-30이 "가장 긴 증가하는 부분수열"이다.

아래의 패턴을 반복하면 특정 수(x) 기준 가장 긴 증가하는 부분 수열을 찾을 수 있다.

1. 왼쪽의 수들 중 특정 수(x) 보다 작은 수(y)를 찾는다.
2. 작은 수(y)들 중 가장 긴 수열을 찾는다.
3. 가장 긴 수열을 찾기 위해 작은 수(y)를 기준으로 1, 2를 반복한다.
   그러나 위의 패턴은 부분 수열의 마지막 값(최대값)을 알아야한다. 최대값을 모르는 경우 특정 수가 바뀌므로, 이전에 했던 작업을 다시 수행해야한다.

이를 배열에 값을 저장하는 방법으로 해결할 수 있다. 인덱스와, 값, 값이 포함된 수열의 이전 인덱스, 수열의 길이를 저장하는 배열을 선언한다. 각 수는 자기자신이 부분 수열을 이루며, 이전 수의 인덱스를 자기 인덱스로 한다.

1번 인덱스부터 시작해 5번 인덱스까지 왼쪽의 수들과 비교해 값을 채운다.

1. 왼쪽 수의 값이 작아야 한다.
2. 왼쪽 수의 부분 수열의 길이가 같거나 커야한다.
   1,2번을 만족하는 경우 이전 수의 인덱스를 왼쪽 수의 인덱스로 채우고,

부분 수열의 길이를 왼쪽 수의 부분 수열의 길이 값+1로 저장한다.

마지막 인덱스까지 비교한 후, 부분 수열의 길이 중 가장 큰 값을 출력한다. 그리고, 가장 큰 값의 이전 수의 인덱스를 이용해 역으로 값을 출력한다.

20(1: 괄호 안 숫자는 인덱스 번호)과 왼쪽 숫자 비교 10(0)과 비교시 1,2번 조건을 만족하므로 20(1)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

10(2)과 왼쪽 숫자 비교 왼쪽 숫자들과 비교시 조건을 만족하는 숫자가 없으므로 수정하지 않는다.

30(3)과 왼쪽 숫자 비교 10(0), 20(1)과 비교시 1,2번 조건을 만족하므로 30(3)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

20(4)과 왼쪽 숫자 비교 10(0), 10(2)과 비교시 1,2번 조건을 만족하므로 20(4)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

50(5)과 왼쪽 숫자 비교 10(0), 20(2), 30(3)과 비교시 1,2번 조건을 만족하므로 50(5)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input | N -> int, stk -> stringToken
        int N = Integer.parseInt(br.readLine());
        StringTokenizer stk = new StringTokenizer(br.readLine());

        /** init | Ai = int[N][3]
         * [][0]: 수열
         * [][1]: 길이
         * [][2]: 이전 수(인덱스)
         */
        int[][] Ai = new int[N][3];
        for(int i=0; i<N; i++){
            Ai[i][0] = Integer.parseInt(stk.nextToken());
            Ai[i][1] = 1;
            Ai[i][2] = i;
        }

        // solve
        // len: 가장 긴 수열의 길이
        // index: 가장 긴 수열의 마지막 인덱스
        int len = 1; 
        int index = 0;
        //loop | 왼쪽 수들과 비교 
        for(int i=1; i<N; i++){
            for(int j=0; j<i; j++){
                if(Ai[j][0]<Ai[i][0] && Ai[j][1]>=Ai[i][1]){
                    Ai[i][1] = Ai[j][1]+1;
                    Ai[i][2] = j;

                    if(Ai[i][1]>len){
                        len = Ai[i][1];
                        index = i;
                    }
                }
            }
        }

        // make indexs | 
        int[] indexs = new int[len];
        for(int i=len-1; i>=0; i--){
            indexs[i] = index;
            index = Ai[index][2];
        }


        // print
        String answer = "";
        for(int i=0; i<len; i++)
            answer +=  Ai[indexs[i]][0] + " ";

        System.out.println(len);
        System.out.println(answer);
    }
}