매일 조금씩

#문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net #풀이 Stack을 이용하여 풀었다. 순서대로 Stack에 막대바의 height, index 정보를 push하면서, 만약 현재 막대바의 height가 Stack의 top원소보다 작을 경우 Stack의 원소를 pop하면서 넓이를 계산해준다. #소스코드 package stack; import java.io.BufferedReader; i..

#문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net #풀이 백트래킹, DFS를 이용하여 풀었다. 1. 스도쿠 정보를 2차 배열에 담는다. 2. 0값의 좌표를 ArrayList로 들고 있는다. 3. 특정 좌표에 특정 Value가 할당 될 수 있는지 체크하는 함수를 생성한다. (isPossible()로 구현) - 좌표가 속한 세로, 가로, 3*3 정사각형 좌표에서 Value가 이미 존재하는지 체크한다. 4. ArrayList의 0번째 index..

#문제 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net #풀이 bitmask 문제로 x의 범위가 20까지이기 때문에 21사이즈의 배열을 생성하여 1~20의 값을 1과 0으로 저장할 수 있게끔 하였다. 연산의 수가 최대 300만건이 될 수 있기 때문에 출력을 유의해야 한다. #소스코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io...

#문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net #풀이 Kruscal 알고리즘을 이용하여 문제를 풀었다. 두 정점 간의 비용이 주어지지 않기 때문에 간선 정보를 직접 만들어줘야 한다. 이중 For문으로 모든 정점을 순회하면서 쌍을 만들어 Edge를 생성해주었고 이때 distance를 계산해서 가지고 있게 했다. (다행히 별의 개수가 100개로 제한되어 있기 때문에 시간 초과 문제는 없었다.) 그리고 EdgeList를 distance 오름차..

#문제 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #풀이 LCA 알고리즘을 이용해 풀었다. 입력 시 parent, child 관계를 명시해주기 때문에 인접 노드 리스트에 정보를 양쪽으로 넣어주지 않았다. child 방향으로 인접 노드 리스트가 구성되었기 때문에, depth 갱신 시 계산된 node에 대해 calculated 여부를 체크하지 않았다. parent 정보가 이미 있기 때문에 d..

#문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #풀이 트리의 두 노드가 주어지고 최소 공통 조상을 찾는 문제이다. (Lowest Common Ancestor) 입력받은 노드의 연관 관계를 인접 노드 리스트로 저장해둔다. root node를 시작으로 dfs로 모든 node의 parent와 depth를 갱신한다. 그리고 입력 받은 두 점의 depth를 비교하여 depth의 차이가 있을 경우 depth가 더 큰 node 값을 해당 no..

#문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net #풀이 위상정렬 알고리즘으로 풀 수 있다. 문제노드 간의 관계는 DAG(Directed Acyclic Graph) 로 표현될 수 있다. (방향성은 있으나 Cycle이 없는 것을 의미) 이 경우 indegree가 0인 Node부터 제거해가면서 순서를 정할 수 있다. 0인 Node가 제거되면 해당 Node가 가리키고 있었던 인접 Node의 indegree를 감소시..

#문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #풀이 M개의 선분이 주어지고 Cycle이 발생하는 순간의 차례를 리턴하는 문제이다. Union-find 기법의 대표적인 문제이다. MakeSet(): parent, rank 초기값 설정 parent는 자기 자신, rank는 0으로 초기화 Find(a): 원소 a의 parent node (root node)를 리턴 path-compression 기법으로 중간 가지를 없애고 parent..

#문제 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net #풀이 유클리드 호제법을 사용한다. 2개의 자연수의 최대공약수(GCD)를 구하는 알고리즘 이다. 자연수 a와 b (a > b)에서 a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a, b) = GCD(b, r) 이며, r이 0이 되는 순간 b가 최대 공약수가 된다. 최소 공배수는 두 수를 곱한 후 최대 공약수로 나눠주면 구할 수 있다. #소스코드 package math; import java.io.BufferedReader; import java.io.I..

#문제 https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr #풀이 N진수 변환 함수를 한참 구현하고 제출했는데 절반 정도가 틀렸다. 찾아보니 Java 자체에서 N진수 변환 기능이 있어서 해당 함수로 바꿨더니 잘된다. Integer.toString(int num, int N진법) 요렇게 넣으면 해당 진수가 리턴된다. 코딩 문제에서 진수 변환할 일이 많은데 알아두면 좋을 것 같다. #소스코드 clas..