문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 문제 풀이 - 프림 알고리즘(최소 신장트리) 사용하여 풀이 - 시간 복잡도 : O(ElogV) 절차 1) 모든 컴퓨터(노드)를 연결하는 최소 랜선 길이(비용)을 구한다. 2) 다솜이가 가진 총 랜선 길이에서 최소 랜선 길이 뺀 나머지를 기부 한다 알파벳이 소문자인지, 대문자인지 구분하는 방법이 조금 애매했는데 이번 문제를 통해 Character 클래스에 유용한 메서드를 알게 되었다..

문제 링크 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 풀이 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위의 지문이 조금 이해가 안되었는데, 사이클이 발생하는 경우에 대해 설명하는 것으로 이해했다. - 크루스칼/프림 알고리즘 (최소 신장트리,MST) 사용하여 최소 비용을 구한 후 전체 비용과의 차..

문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제 풀이 크루스칼 알고리즘을 사용하기 위해 노드와 노드 사이의 비용 정보가 필요한데, 2차원 좌표(X, Y)가 주어질 때 노드로 생각하지 못했고, 거리 계산 또한 생각을 하지 못했다. 해당 문제를 통해 시야가 또 좁아진 점을 반성한다.. 입력 예시 4 1 // 노드 수, 연결된 노드 수 1 1 // 노드 1 3 1 // 노드 2 2 3 // 노드 3 4 3 ..

문제 링크 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제 풀이 문제 지문에 " 무게가 중간이 절대로 될 수 없는 구슬의 수 " 키워드 였다. 풀어서 적어보자면 자기보다 크거나 작은 구슬의 개수가 중간 개수가 넘어가면 절대 중간이 될 수 없는 구슬이다. - 플로이드 워셜 풀이 - 시간 복잡도 : O(N^3) + O(N^2) // 플로이드 워셜 알고리즘 + 각 구슬별로 크거나 작은 구슬 카운팅 - 구슬 절반 개수 : ( N..

문제 링크 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 관심사는 기능에 따..