문제 링크 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 번째 먹이..

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) 소..

설명 - 피벗을 기준으로 좌측에 피벗 보다 작은 값, 우측에 피벗보다 큰 값을 위치 시킴 - partition(파티션)을 나눠 행위를 반복한다 - partition을 최소 까지 나눴을 때는 이미 정렬이 완료된 상태이다. 파티션을 나누기 전에 pivot 기준으로 임의 정렬을 하고 partition을 나눠 행위 반복하면 더이상 나눌 수 없을 때 이미 정렬이 완료된다. 반대로 merge sort의 경우 제일 작은 크기 까지 파티션을 먼저 나눈 후 병합을 하면서 정렬 수행한다. *과정 (1) pivot 을 정함 (2) 양쪽 끝에 L, R 포인터를 두고 다음 수행 2-1) L < pivot 경우 포인터 증가 L += 1 (pivot 기준 좌변은 항상 작아야 하므로, 큰 값이 나올 때까지 포인터 이동) 2-2) p..

설명 1) 리스트의 길이가 1이 될 때 까지 나눈다(mergeSort()) 2) 왼쪽과 오른쪽 리스트를 대소 비교 하여 정렬된 결과(merge()) 반환 - 재귀 함수 호출하여 작은 문제로 나눈 후 큰 문제의 정답을 구한다 - 재귀 호출로 인해 스택 오버플로우 발생가능(단점) - Java의 경우 인스턴스 메서드 *.subList(int from, int to) 사용하여 쉽게 리스트 분할 가능하다 시간 복잡도 : O(NlogN) - 파티션을 나누는데 logN 만큼 걸리고, 다시 병합할 경우 N 만큼의 소요 공간 복잡도 : O(N) 영상 참고 https://www.youtube.com/watch?v=3j0SWDX4AtU 작은 문제로 나눠서 큰 문제의 해답을 구한다 코드 - 오름차순 정렬 기준으로 작성 - 내..

문제 링크 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 시간복잡도 - 상향식(Bottom-Up) 풀이시 O(N^2) = O(2000^2) - 하향식(Top-Down) 풀이시 O(N!) = O(2000!) 시간 초과 발생 가능 -> memorization 기법으로 시간내 풀이 가능 *팰린드롬 (PALINDROME) ? - 길이가 1일 때 자기 자신도 팰린드롬이다. (1, 2, 3, ...) - 길이가 2인 경우 두 숫자가 동일할때 팰린드롬이다. (11, 22) - 길이가..

문제 링크 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 백준 11066 파일 합치기와 비슷한 문제였으나 행렬 곱셉을 어떻게 DP 배열로 처리할 지에 대해 파악하기 힘든 문제였다. - 상향식(Bottom-Up)으로 풀 경우 시간 복잡도 O(N^2) - 하향식(Top-Down)으로 풀경우 O(N!) , memorization 기법 활용하여 시간 내에 풀이 가능 - 최대치는 Integer 범위 - 행렬 A (m x k) ,..

문제 링크 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 문제 풀이 - 인접 리스트 사용하여 시간 복잡도 O(V + E) = O(10,000 + 9,999) - 트리이기 때문에 간선의 수 = 노드의 수 - 1 - DFS 방식으로 리프 노드 구하는 문제에서 응용하는 문제로 2차원 배열로 방문 여부에 따라 조건 처리를 하게 된다 - 시작 노드는 1로 해서 최종적으로 DP[1][0], DP[1][1] 중 최대값이 최대 인구에 해당한다 DP..

문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 풀이 스스로 풀지 못하여서 기술 블로그를 참고 하였고, 이번 문제를 통해 DP 기법과 Two Poiner 기법 응용하는 방식에 대해 처음으로 알게 되었다. 풀이 후 몇일 있다가 손으로 그려보고 Top-Down, Bottom-Up 풀이하는데 역시나 쉽지 않은 문제인 것 같다. 가짜문제 정의, 초기화 항목 .. 단순히..