본문 바로가기

알고리즘

💚트리 1. 문제 설명 1068번: 트리 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. www.acmicpc.net 트리에서 A번 노드를 없앴을 때 리프 노드의 개수를 구하여라 2.푸는 원리 위의 설명 처럼, 나는 제거되는 중간 노드가 가진 leaf 노드에 -111 이란 가상의 노드를 새로 더해주었고, 그렇게 해서 leaf 노드가 아닌 것으로 만들었다. 그리고 다시 전체 노드에서 자식 노드가 없는 노드의 개수를 세어줘서 리프 노드의 개수를 구했다. 하지만 이 알고리즘에서 예외가 되는 지점이 존재했다. 만약 위의 예시의 노드 2처럼 자신이 가진 모든 leaf 노드가 -111이란 가상의 노드를 가진다면, 실질적으로 2가 가진 모든 자식 노드가 제거 되었다는 소리임으로 2가 leaf 노드가 된다. 따라서.. 더보기
💜배열 복원하기 1. 문제 설명 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다. www.acmicpc.net 원래 배열 A를 수직으로 X, 수평으로 Y만큼 이동시킨 다음 원래 배열 A와 겹쳐서 새로운 배열B를 만든다. 만드는 원리는 다음과 같다. 겹치는 부분은 겹치는 값의 합이다. 안 겹치는 부분은 원래 값 그대로 이다. 원래 존재하지 않았던 새로운 평야의 값으 0이다. 겹쳐진 배열 B가 주어질 때, 원래 배열 A의 값을 구해라. 2. 푸는 방법 새로운 배열 A를 B를 통해서 구할 때, 겹치지 않는 부분은 B값.. 더보기
💔LCS 1. 문제 설명 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. www.acmicpc.net 문자열이 두 개 주어졌을 때, 두 문자열의 최장 공통 부분 수열을 구하여라 2. 문제 푸는 원리 설명 부분 수열은 본 수열에서의 숫자의 순서를 지키는 하나의 열이어야 한다. 예를 들어 0이 아닌 양의 정수라는 수열이 있다고 하자. (1, 2, 3, 4, 5, 6, 7, …) 짝수 정수로 이루어진 수열은 해당 정수의 순서를 지키므로 0이 아닌 양의 정수의 부분 수열이다. (2, 4, 6, 8. 10, …) 따라서 최장 공통 부분 수열이라면, 두 문자열에서 공통으로 순서가.. 더보기
💔벽 부수고 이동하기 4 1. 문제 설명 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. www.acmicpc.net 벽이 부분을 부수고 거기서 이동할 수 있는 공간의 크기를 구하라. 원래 부터 0이었던 공간은 그냥 0으로 출력, 원래 1(벽)이었던 공간은 그 벽을 부수고 좌우로 최대한 이동할 수 있는 공간의 개수를 해당 자리에 출력 2.문제 푸는 원리 처음엔 벽 하나하나 마다, 그 자리를 부수고, bfs를 돌렸다. 이렇게 풀었더니 시간초과가 났다. 다른 방법이 생각나지 않아서 다른 사람이 푼 원리를 읽었다.. 더보기
🖤LIS 알고리즘의 이론과 구현 1. LIS란? LIS란 Longest Increasing Subsequence의 약자로 가장 긴 증가하는 부분 수열을 뜻한다. LIS 알고리즘 문제는 전체 수열을 주어지고, 그 안에서 가장 길고, 증가하는 부분 수열을 구해야 하는 문제들을 총칭이다. 난 부분 수열이 무엇인지부터 헷갈렸다. 따라서 먼저 수학적 배경지식을 공부하고, 마저 설명하겠다. 1-1. 부분 수열이란 무엇인가? 수열은 수가 하나의 열로 나열된 형태를 뜻한다. (행군하는 군인을 떠올려보라!) 여기서 부분수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열 을 뜻한다. 만약 전체 수열 S 가 {1,2,3,4,5,6,7,8,9,10}이라면 {1}, {2,4,6,8,10}, {2,4,6}, {8,9,10} 모두 S의 .. 더보기
백준 1193번 분수찾기 1193번: 분수찾기 (acmicpc.net) 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { // 입력 받기 Scanner sc =new Scanner(System.in); ArrayList list = new ArrayList(); int N = sc.nextInt(); // 입력 받은 값에서 계산해야할 분수들 추리기. int i = 0; while(N > 0){ if(N 더보기
백준 2720번 해답 2720번: 세탁소 사장 동혁 (acmicpc.net) 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 1. 내 코드 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); for (int test_case = 0; test_case < N; test_case++) { int change = sc.nextInt(); int[] cen.. 더보기
백준 11005번 진법 변환2 11005번: 진법 변환 2 (acmicpc.net) 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 1. 내 코드 import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ArrayList list = new ArrayList(); // 10진수 받기 int digit = sc.nextInt(.. 더보기

티스토리툴바