전체 글

[알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상을 찾는 알고리즘 → 두 정점이 만나는 최초 부모 정점을 찾는 것! 트리 형식이 아래와 같이 주어졌다고 하자 4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2' 4와 6의 LCA는? → 첫 부모 정점은 root인 '1' 어떻게 찾죠? 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다. [depth : 정점] 0 → 1(root 정점) 1 → 2, 3 2 → 4, 5, 6, 7 parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다. // 1 ~ 7번 정점 (root는 부모가 없기 때문에 0) int parent..

문제 출처 : 링크 Problem - C - Codeforces codeforces.com 문제 자체는 어렵지 않다. 처음으로 등록되는 문자열은 "OK"로 출력하고, 만약 똑같은 문자열이 또 입력되면 숫자를 붙여서 출력해야한다. ex) Input 4 abacaba acaba abacaba acab output OK OK abacaba1 OK abacaba가 3번째에 또 들어오면서 abacaba1로 출력하는 모습을 볼 수 있다. 만약 한번더 들어오면 abacaba2를 출력하면 된다. 이 문제는 시간초과에 빠지기 쉬운 문제다. 왜냐하면 N의 값이 1~100000이다. 만약 브루트포스로 진행하면 N^2으로 100억번의 연산을 해야하는데 문제에 주어진 제한 시간 5초로는 불가능하다. 이 문제는 따라서 해시 테이..

문제 출처 : 링크 Input으로 요일 수(d)와 최대 시간(sumTime)이 주어진다. 그리고 d만큼 하루에 공부할 수 있는 최소 시간과 최대 시간이 각각 한 줄씩 들어온다. 모든 요일에 주어진 최소 시간만큼은 공부를 해야 하고, 최대 시간과 일치하는 공부 시간을 출력해야 한다. 주어진 요일의 공부시간동안 최대 시간만큼 할 수 없으면 "NO"를 출력하고, 가능하면 "YES"와 함께 요일별 공부시간을 출력해야 한다. 예) 2 5 0 1 3 5 d = 2고, sumTime = 5다. 이틀동안 5시간의 공부를 해야한다. 첫째날은 0~1시간 공부를 할 수 있고, 둘째날은 3~5시간을 공부할 수 있다. 첫째날에 1시간 공부 & 둘째날에 4시간 공부 or 첫째날 0시간 공부 & 둘째날에 5시간 공부 두가지 경우로..

문제 출처 : 링크 아주 간단한 문제다. input 값이 들어오면, 2명이서 나눠가질 때 둘다 짝수 값으로 가질 수 있으면 'YES' 아니면 'NO'를 출력해야한다. 예를 들면 2는 1과 1로 밖에 못나눠서 NO 6은 2와 4로 나누면 짝수라 YES 7은 짝수로 나눌 수 없어서 NO N이 1~100 사이에 수가 들어오므로, 1이 아닌 경우에 둘로 나눈 값이 모두 짝수로 나오는 경우가 있는지 판단하면 된다. 나는 N이 들어오면, for문에서 N을 2로 나누고 1씩 감소하며 두 수가 짝수인지 체크하는 방식으로 해결했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 package CodeForces; impor..

알고리즘 문제를 풀면서 최적화에 신경을 써야할 때가 있다. (시간이나 메모리를 줄이는 것이 중요한 B형처럼..) 1. for문의 ++i와 i++ 차이 for(int i = 0; i < 1000; i++) { ... } for(int i = 0; i < 1000; ++i) { ... } 내부 operator 로직을 보면 i++은 한번더 연산을 거친다. 따라서 ++i가 미세하게 조금더 빠르다. 하지만 요즘 컴파일러는 거의 차이가 없어지게 되었다고 한다. 2. if/else if vs switch case '20개의 가지 수, 10억번의 연산이 진행되면?' if/else 활용 : 약 20초 switch case : 약 15초 switch case가 더 빠르다. (경우를 찾아서 접근하기 때문에 더 빠르다) if..

[Spring Boot & React] Polling 웹애플리케이션 만들기 - 2부 1부 : 프로젝트 생성 및 기본 도메인 모델과 레포지토리 생성 최종적으로 만들어지는 페이지는 아래와 같다. 지난 시간에 이어서, 이번에는 JWT 인증과 함께 Spring Security 구성 및 로그인과 회원가입에 대한 API를 만들어보도록 하겠다. 처음 접하면 상당히 내용이 어렵고 복잡해보인다. 일단 진행과정을 익히며 익숙해지도록 노력해보자! Spring Security와 JWT를 통한 사용자 인증 구축하기 사용자가 웹 애플리케이션에 회원가입하고, 로그인할 수 있는 API를 만들 것이다. 우선 진행하기에 앞서, 어떤 식으로 인증과정을 설계할건지 요약해보자 - 새로운 사용자를 Full Name, UserName, Emai..

[Spring Boot & React] Polling 웹애플리케이션 만들기 - 1부 Spring Boot와 React를 연동하여 Polling 웹앱을 만들어보려고 한다. CalliCoder에서 진행하는 Tutorial을 참고해서 다시 재구성해봤다. (링크) 최종적으로 만들어지는 페이지는 아래와 같다. [구성] Back-End - Spring Boot (Spring Security와 JWT 인증을 활용한 백엔드 서버 구축) - Database는 MySQL 활용 (JPA) Front-End - React 스프링 부트 프로젝트 생성하기 http://start.spring.io/에 접속해서 프로젝트를 생성해보자 자신의 프로젝트에 맞게 설정해주면 된다. 기본적으로 Dependencies는 Web, JPA, MyS..

[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기 사이클을 찾기 위해서는 DFS를 활용한다. (정점 : v, 간선 : e) - visited[] : 점들의 방문여부가 저장된 배열 - recur[] : v가 지금까지 방문한 점이 저장된 배열 for(v 수 만큼) { dfs(v, visited, recur) } DFS 수도코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 boolean dfs(v(a), visited, recur) { visited[v(a)] = true recur[v(a)] = true for(v(a)와 연결된 점의 수만큼) { b = 연결된 점 if(!visited[b] && dfs(v(b), visited, recur){ // b가 방문상태..

[알고리즘] XOR 비트 연산을 활용하기 비트 연산을 활용해서 문제에 적용하면 상당히 효율적으로 코딩이 가능한 경우가 있다. 특히 코딩테스트와 같이 문제를 풀 때 비트 연산을 활용하면 좋다. 이번에 살펴볼 예시는 보통 네이버나 카카오 등 프로그래머스를 이용해 코딩테스트를 보게 되는데, 테스트 환경에서 연습해보는 1번 문제로 등장하는 유형이다. 직사각형의 3개 점이 주어진다. 나머지 하나의 점의 좌표를 구하라. (직사각형은 항상 평행한 상태) ex) (2, 0) (6, 0) (6, 6) 정답 : (2, 6) 다양한 방법을 이용해 푸는 것이 가능하지만, 가장 신박했던 방법은 비트연산을 활용해 푸는 것이었다. XOR은 입력 값 중 하나만 true일 때 true를 리턴해준다. 따라서 주어진 3점의 x좌표와 y좌..

React + Spring Boot 연동하여 환경 구축하기 프로젝트 진행에 앞서 연습해보자! Front-end : React Back-end : Spring Boot 스프링 부트를 통해 서버 API 역할을 구축하고, UI 로직을 React에서 담당 ( React는 컴포넌트화가 잘되어있어서 재사용성이 좋고, 수많은 오픈소스 라이브러리 활용 장점 존재) 개발 환경도구 (설치할 것) - VSCode : 확장 프로그램으로 Java Extension Pack, Spring Boot Extension Pack 설치 (메뉴-기본설정-설정에서 JDK 검색 후 'setting.json에서 편집'을 들어가 `java.home`으로 jdk 경로 넣어주기) "java.home": "C:\\Program Files\\Java\..