문제 링크 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^3) - 플로이드 워셜 공식 활용하여 각 노드별 최단 경로는 구한다 floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j] i -> j로 바로가는 비용과 k 를 거쳐 가는 i -> k -> j 비용 중 작은 값을 구한다 경로 추적 - (1,1) ~ (N, N) 까지 경로 추적하는 부분에서 시작과 끝 ..

문제 링크 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 문제 풀이 - 플로이드 워셜 기본 문제 - 시간 복잡도 = 플로이드 워셜 수행 + 친구 별 방에 대한 최단 거리 합산 + 최소 비용 가지는 방 번호 구하기 = O(N^3) + (N^2) + (N) (최대 친구 수는 N 이하, N번 방) 절차 1) 각 노드별 다른 노드에 대한 최단 경로를 플로이드 워셜 알고리즘으로 구한다, 시간 복잡도 O(N^3) 2) 친구별 방에 대한 최단 거리 비용을..

문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 문제 풀이 플로이드 워셜로 각 노드별 다른 노드에 대한 최단 경로를 구할 수 있었다. 그런데 출발 행성 K 위치가 주어졌을 때 다른 행성을 탐색하는데 걸리는 시간을 어떻게 구할 지에서 삽질을 여러번 하였다. 결국 재귀 함수 사용한 완전 탐색으로 구하면 방문 여부 체크하며 구하면 되는 문제였다. "이미 방문한 행성도 중복해서 갈 수 있다"는 문제 지문이 함정이 아니었나 싶다 스스로 ..

문제 링크 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 문제 풀이 - 단방향 그래프 - 주어진 입력에 따라 인접 행렬을 초기화 및 입력 가중치(1) 설정 - 플로이드 워셜 알고리즘을 실행해서, 각 노드별로 다른 노드 갈 수 있는지 구한다. - 시간 복잡도 : O(N) 각 케이스에 대해 1) 0 인 경우는 (i, j), (j, i) 둘다 INF로 확인 불가를 뜻함 // 입력 2) 1 인 경우 j와 i 두 값중 i 사건이 더 먼저 발생한..

문제 링크 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 문제 풀이 - 직접 풀이하지 못하여 아래 기술 블로그 참고 후 풀이 - 최소라는 단어에 매몰되어 이진 탐색 후 완전탐색을 해야 하나하고 삽질함 (당연히 시간초과) https://steady-coding.tistory.com/105 [BOJ] 백준 1507번 : 궁금한 민호 (JAVA) 문제 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, ..

문제 링크 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 풀이 1) 각 노드별로 다른 노드에 대한 최단 거리를 구한다 (양방향 관계, 플로이드 워셜 알고리즘 사용) - 이때 시간복잡도 O(N^3) 2) 각 노드별 최단 거리를 구한 후 그 중 최대값이, 해당 노드의 회장 점수가 된다 3) 회장 점수가 최소가 되는 번호를 구해서 출력한다 문제에서 아래 부분이 조금 이해가 안 되었는데 결론은 각 노드별 최단 거리를 구해라는 의미였다 각 회원의..

문제 링크 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 풀이 - 플로이드 워셜 카테고리 문제 (카테고리 몰랐으면 과연 풀었을까 싶다) - 노드별 사이클 발생할 경우 최단 거리 구함(시작 노드를 포함하는) - 시간 복잡도 : O(N^3) 플로이드 워셜의 경우 각 노드별로 다른 노드로 가는 최단 거리를 구하게 된다 이때 사이클이 발생한다는 것은 각 시작 노드의 최단 거리 값이 INF가 아니게 된다는 의미로..

문제 링크 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘 문제 - 1 -> N 노드 까지 최단 거리 구하면 된다 - C_i마리 소 = 간선의 가중치 - 시간 복잡도 : O(ElogV) - 노드와 간선이 최대 50,000개 있으므로 O(50,000log50,000) = O(50,000 * 약 15.6) , 고로 1초만에 가능 제출 코드 import java.util.*; import java.io.*; public cl..

문제 링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 - 다익스트라 카테고리 분류되어 있어 다익스트라 알고리즘 방식으로 풀었다 - (1,1) -> (N, M) 까지 벽을 최소로 부숴야 하므로 우선 순위 큐를 사용 (부숴버린 벽돌 수에 대해 오름차순 정렬) 제출 코드 import java.util.*; import java.io.*; public class Main { static int n, m; stati..

문제 링크 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 문제 풀이 중복 방문을 허용하고, 상하좌우 대각선(8개 방향) 방향으로 이동하여 문자열을 만듦 참고. 시간 복잡도 행 * 열 * (8방향으로 이동^최대 단어 길이 5) = 100 * (8^5) = 3,276,800 (1초안에 수행 가능) 참고. 방향 이동 관련하여 ( 3 x 3 ) (0, 0) 좌표에서 아래 대각선 방향으로 이동할 경우 맵의 범위를 벗나게 될 것이다 (-1, -1) (-1, 0) (-1, 1) (0, -1) 시작 (0, 1) (1, -1) (1, 0) (..

문제 링크 https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 문제 풀이 하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다. 1. 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다. 2. 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다. 3. 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다. 4. 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로..

메모리 초과의 경우 - 재귀 호출로 인한 스택 오버 플로우 발생할 경우 종료 조건 확인 - 변수 타입이 범위 초과할 경우 (long인데 int로 선언하거나) 시간 초과의 경우 (1초에 1억번 연산을 가정했을때) - 시간 복잡도가 적철지 못한 문제 풀이 했을 때 - 주어진 query에 대한 결과나, 조합에 대한 결과를 구할 때 전처리 후 사용하기 결과 값을 구해지는데 실패가 케이스가 뜨는 경우 - 변수 타입, 최대치, 초기화 확인 문제 링크 https://www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이..

목차 @Nested 사용하여 테스트 그룹화 - simple 하게 내부 클래스 선언 - @Nested Annotation 추가하면 됨 - 그룹화할 테스트 메서드를 이동 사용 예시 @ActiveProfiles("test") @AutoConfigureMockMvc @SpringBootTest(webEnvironment = SpringBootTest.WebEnvironment.MOCK) class RestControllerTest { // .. 테스트 작성 @Nested @DisplayName("계좌 입금 테스트") @TestMethodOrder(MethodOrderer.MethodName.class) class AccountDeposit { // .. 테스트 작성 } } Controller, Service 테..

목차 AOP (Aspect Oriented Programming) 관점 지향 프로그래밍은 어떤 로직을 기준으로 핵심적인 관점, 부가적인 관점으로 나누어서 보고 그 관점을 기준으로 각각 모듈화 하겠다는 의미이다. 여기서 모듈화란 어떤 공통된 로직이나 기능을 하나의 단위로 묶는 것을 만한다. 예로들어 핵심적인 관점(core concerns)은 결국 우리가 적용하고자 하는 핵심 비즈니스 로직이된다. 또한 부가적인 관점은 핵심 로직을 실행하기 위해서 행해지는 로깅, 실행시간 측정, 시큐리티, 트랜잭션 등이 될 수 있다. A Concern is a term that refers to a part of the system divided on the basis of the functionality 관심사는 기능에 따..

HashMap - 내부적으로 hash 값을 인덱스로 하여 자료 구조 관리 - Key 중복 x , Value 중복 허용 - hash 값의 중복이 발생하는 경우 LinkedList, Tree 자료 구조 사용하여 해결하고 있음  Method 살펴보기put()- key 로 만든 hash 값에 해당하는 bucket이 없는 경우 신규 Node 저장, 있는 경우 value를 덮어씌움- 동일한 hash 값이 있는 경우 ThreadHold 값에 따라 LinkedList, Tree 로 자료 연결되어 관리 참고. HashMap put() 살펴보기  예시테스트 파일에서 공통으로 사용할 Map의 데이터를 초기화public class HashMapTest { Map map = new HashMap(); @BeforeE..

Set ? - 집합을 다루는 자료구조- 중복 x, 순서 x- 대표적인 구현체 : HashSet / TreeSet / LinkedHashSet / EnumSet- 내부적으로 Map 자료 구조에 Key에 데이터를 담는다 (Map은 Key의 중복 허용하지 않음)//java.util.HashSet.classprivate transient HashMap map;private static final Object PRESENT = new Object();public HashSet() { this.map = new HashMap();}//..public boolean add(E e) { return this.map.put(e, PRESENT) == null; // HashMap의 Key에 element를 담..

Array (배열)- 동일한 자료형(Data Type)의 데이터를 연속된 공간에 저장하기 위한 자료 구조- 기본형(Primitive Types) 또는 인스턴스(Reference Type)을 저장하기 위해 배열 사용- 처음 선언시 길이를 지정하기 때문에 런타임 환경에서 크기를 변경할 수 없다 (정적 할당, static allocation) Array 선언 및 초기화 예시# 1int[] arr = new int[10];arr[1] = 1; // .. 이하 생략# 2int[] arr = new int[] {1, 2, 3, 4};# 3 int[][] arr = {{1, 0}, {0, 1}, {-1, 0}, {-1, 0}}; 장점구조가 간단하고, 인덱스로 해당 element에 접근할 경우 시간 복잡도 O(1) 소..

목차 출처 (망나니 개발자 기술 블로그) https://mangkyu.tistory.com/116 [Java] Stream API 연습문제 풀이 (5/5) 이번에는 Stream API를 연습해볼만한 문제를 제공해보고자 합니다. 자동화된 테스트를 통해 정답을 확인하도록 제공하고 있으니 직접 문제를 풀어서 정답을 확인해보실 분들은 아래 내용을 참고 mangkyu.tistory.com *자료 받으실 때 Star 는 필수 수행 - 소요 시간 1일차 1시간 40분 2일차 40분 3일차 20분 4일차 15분 5일차 15분 암기보다는 [stream 생성 -> 중간 연산 -> 최종 연산] 과정에 집중해서 연습 Quiz1 1-1. 각 취미별 선호 인원 수 구하기 - csv 파일의 경우 readCsvLines() 통해서 ..