뽀루피의 개발스토리

위상정렬위상정렬은 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)에서 순서를 정렬하는 알고리즘이다. 위상정렬을 구현하기 위해서는 4가지 변수를 만들어줘야 한다.int[] indegree : 특정 노드에 대해서 다른 노드로부터 들어오는 간선의 개수List> array : 그래프의 간선 정보를 담은 2차원 리스트Queue q : indegree 값이 0이 된 노드들을 담기 위한 queueQueue result : 정렬된 순서를 보여줄 결과 queue. q에서 빠져나온 순서대로 정렬된다. 1. 맨 처음 indegree 값이 0인 노드들을 Queue에 담고 시작한다. 2. Queue에서 노드 1을 빼주며 1에서 가르킨 노드들의 indegree 값을 1씩 감소시킨다.즉, ..

나머지(모듈러) 연산나머지를 구하는 연산으로 예를 들어, 두 정수 A, B에 대해서 A를 B로 나누어서 C가 나왔다면A % B = C 또는 A mod B = C 이다. 나머지(모듈러) 연산에는 덧셈, 뺄셈, 곱셈 성질이 있다.덧셈 성질(A+B) mod C = (A mod C + B mod C) mod C뺄셈 성질(A-B) mod C = (A mod C - B mod C) mod C곱셈 성질(A*B) mod C = ((A mod C) * (B mod C)) mod C  우리는 이러한 성질을 이용해 int의 범위를 넘어서는 값을 int로 표현할 수 있거나 큰 값을 계산할 경우 분할정복을 통해 간단하게 표현할 수 있다. '백준 1629번 문제 곱셈' 이 이러한 성질을 이용한 문제이다.  백준 1629 곱셈ht..

체크 예외란?RuntimeException 클래스를 상속받지 않은 예외 클래스들을 말합니다. 체크 예외는 복구 가능성이 있는 예외이므로 반드시 예외를 처리하는 코드를 함께 작성해야 합니다. 예외를 처리하기 위해서는 catch 문으로 잡거나 throws를 통해 메소드 밖으로 던질 수 있습니다. 예외를 처리하지 않으면 컴파일 에러가 발생합니다. 반대로, 언체크 예외가 있습니다. RuntimeException 클래스를 상속받는 예외 클래스들은 복구 가능성이 없는 예외들이므로 컴파일러가 예외처리를 강제하지 않습니다. 즉, 에러를 처리하지 않아도 컴파일 에러가 발생하지 않습니다. 런타임 예외는 예상치 못했던 상황에서 발생하는 것이 아니므로 굳이 예외 처리를 강제하지 않습니다. RuntimeException에는 대..

Spring 프레임워크에서 쓰이는 어노테이션을 정리해보았다. @RequiredArgsConstructorfinal이 붙은 필드로 생성자를 하나 만들어준다.그리고 생성자가 하나만 있으면 @Autowired가 자동으로 붙는다.그래서 생성자와 @Autowired를 생략하여 코드를 깔끔하게 정리할 수 있다. @Transactional데이터베이스 상태를 바꾸는 쿼리들이 많이 있을 때, 중간에 오류가 나서 멈추게 되면 그동안 바꿨던 쿼리들을 되돌려야 할 것이다. 트랜잭션을 사용한 메소드는 쿼리들을 프록시 저장했다가 최종적으로 완료되면 커밋된다. 트랜잭션에 대해서 간단히 설명했지만 다루는 내용이 많다. 나중에 별도로 게시물을 만들어보겠다.   스프링 IoC(Inversion of Control) 관련 어노테이션스프링..

누적합누적합의 예제부터 살펴보자 [1, 2, 3, 4, 5] 배열이 있다고 할 때 각 구간까지의 합을 구하는 배열 [1, 3, 6, 10, 15]를 구한다고 가정해보면 두 가지 방법을 생각해볼 수 있다. 1. 완전 탐색으로 더하기11+21+2+31+2+3+41+2+3+4+5 2. 누적합을 이용한 더하기11+23+36+410+5 2가지 방법을 비교하면 2번째 방법이 효율적임을 알 수 있다. 누적합은 이처럼 시작점부터 n번째 원소까지 앞에서부터 누적으로 합해오는 알고리즘이다.모든 구간을 반복해서 더하는 것보다 이전 인덱스까지의 누적합에 현재 인덱스를 더하여 구현하는 것이 효과적인 방법이다. 큰 계산을 작게 효율적으로 만든다는 점에서 DP와도 상통하는 부분이 있다.누적합 알고리즘은 A~B 범위의 구간 합을 구..

투포인터1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘이다.  위의 예시처럼 2개의 포인터를 옮김으로써 이루어진다.완전탐색에 비해 시간복잡도를 많이 아낄 수 있다.while (start  코드 예시이다. while문 내에 탈출 조건문과 포인터를 옮겨주는 조건, 얼마나 옮길건지를 작성해주면 완성이다.어찌보면 for문에서 인덱스 초기 조건, 반복문 탈출 조건, 인덱스 이동을 작성하는 것과 같이 이루어지는데 다른 부분이라면 문법이 아닌 내가 직접 구현한다는데 차이점이 있는 것 같다.   백준 1806 부분합길이가 N인 수열이 주어지고 합이 S 이상인 부분합들 중 최단 길이를 구하라는 문제였다.문제를 읽었을 때 부분합이라는 단어와 길이가 ..

스프링 빈은 어디에 활용하는 것일까?객체지향언어를 배우다보면 싱글톤 객체를 만들어 필요한 곳마다 찾아넣어주는 의존성 주입을 구현해본 적이 있을것이다.이것을 간단화할 수 있는 @Autowired에 활용된다.생성자에 @Autowired 어노테이션이 있다면 스프링이 연관된 객체는 스프링 Container가 찾아서 넣어준다.  스프링 빈을 등록하는 방법컴포넌트 스캔과 자동 의존관계 설정자바 코드로 직접 스프링 빈 등록하기스프링은 스프링 컨테이너에 스프링 빈을 등록할 때 싱글톤으로 등록한다. 즉, 스프링 빈을 의존성 주입 받으면 모두 같은 인스턴스이다. 설정으로 싱글톤이 아니게 할 수 있지만 대부분 기본값인 싱글톤을 사용한다.  1. 컴포넌트 스캔@Component 어노테이션이 있다면 스프링 빈으로 자동 등록되는..

자동 import (alt + enter) 줄 복사 (ctrl + D) 반환타입, 이름 자동 생성 (ctrl + alt + V) 메소드 추출 (ctrl + alt + M) 메소드 내의 값들을 파라미터화 할 것인지도 물어본다. 파라미터 자동 생성 (ctrl + alt + P) 생성자, getter, setter, toString() 등 자동 생성 (alt + insert) Test 클래스 자동 생성 (ctrl + shift + T) 이름 동시 변경 (shift + F6)  이전에 찾아봤던 페이지 찾기 (ctrl + E)  변수를 반환 값으로 변환 (ctrl + alt + N)   파일 전체 제목 검색 (ctrl + N)  파일 전체 내용 검색 (Ctrl + Shift + F)  선택부분 파라미터 추가 (C..

BFS (너비 우선 탐색) BFS는 위의 그림과 같이 점차 탐색 영역을 확장시켜 나가는 알고리즘이다.BFS는 그래프 탐색 문제에 적합한 알고리즘인데 이번에 풀어본 아기상어가 그래프 탐색 문제이다.  BFS의 원리는 간단하다.1. Queue 자료구조에 그래프에서 현재 위치를 넣어준다.2. 방문했던 곳을 다시 가지 않도록 방문처리를 해준다.3. Queue에서 하나씩 Poll한다.4. Poll한 위치에서 이동할 수 있는 그래프의 위치들을 탐색하고 이를 또 Queue에 Add한다.5-1. 탐색 도중 조건에 맞는 위치가 나온다면 성공한 결과값과 함께 BFS 종료,5-2. Queue에 더 이상 이동할 위치가 남아있지 않다면 실패 결과값과 함께 BFS 종료  기본 형태는 다음과 같다.static boolean bfs..

https://www.acmicpc.net/problem/1167 트리에서 임의의 두 점 사이의 거리 중 가장 긴 거리를 구하는 문제다.트리의 정점의 개수 V가 주어지고 V개의 줄에 걸쳐 간선의 정보가 주어졌다. 이 문제를 풀기 위해 플로이드-워셜 등의 방법을 잠시나마 생각해봤지만 100,000개의 정점을 삼중 반복문으로 돌릴 생각을 하니 안 된다는 것을 깨닫기까지 그렇게 오래걸리지 않았다. 결국 트리의 지름 공식을 알아야 풀 수 있는 문제였다.트리의 지름 공식은 다음과 같다. 1. 임의의 점 A에서 가장 먼 지점 B를 찾는다.2. B에서 가장 먼 지점 C를 찾는다.3. B ~ C의 거리가 트리의 지름이다. 이 공식만 이용한다면 어렵지 않게 풀 수 있다.import java.io.*;import java..