1. 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2. 풀이에 대한 설명 2차원 배열을 순회하면서, (1) 1을 만난다면! 거기서 부터 해당 1의 상하좌우 중 붙어있는 1이 있는지 확인한다. (아파트 단지 내의 아파트 수 체크) (2) 내가 금방 방문해서 확인한 1은 -1로 값을 바꾸어서 방문 처리한다. (3) 1 search가 끝나면 해당 아파트 단지의 아파트 수를 다 센 것이다. (4) 이때 아파트 수를 aptList라는 아파트 단지..

1. 개요 아주 기본적인 BFS로 풀 수 있는 간단한 문제이다. 이 문제가 잘 안 풀리는 사람은 BaaaaaaaaarkingDog님의 그래프 강의를 보고 오길 바란다. 실버 3도 식은 땀 흘리며 풀었다... 재활운동 시작! 내가 한번 틀렸었는데, 이유는 양방향 그래프임을 생각해주지 않고 풀어서 이다. 이론 정리 다시 해야겠다. 2. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { pu..

문제 설명 https://www.acmicpc.net/problem/9663 N*N 체스판이 주어진다. 체스판에 Queen을 서로가 서로를 죽이지 못하게 모든 행에 놓아라 이떄 놓을 수 있는 경우의 수는 어떻게 되는가? 푸는 원리 백트래킹을 사용해야 한다. 백트래킹이란 깊이 우선 탐색을 하되, 가능성이 없는 루트를 탐색한다고 판단될 경우 과감하게 그 루트를 포기하고 다음 경우의 수를 체크하러 떠나는 것이다. 해당 길이 답을 도출할 수 있는 유망한 길인지 아닌지 체크하는 것은 문제마다 다르다. 따라서 유망성 체크 조건을 알아차리는 감각은 많은 백트래킹 문제를 풀어보며 익혀야 하겠다. 본론으로 돌아와서 N-Queen 문제를 풀어보자. 체스에서 퀸은 비숍과 록을 합친 움직임을 할 수 있는 가장 쎈 장기말이다...

1. 문제 설명 https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net IOI 형태의 문자열 Pn이 주어질 때, 전체 문자열 S에서 Pn이 몇 번 등장하는지 등장 횟수를 출력해라 2. 푸는 원리 이것도 안 풀려서 답지를 봤다. 문자열 알고리즘을 공부 해야겠다. 나는 문자열을 투포인터로 한번 쭉 훑으려고 했는데 해당 문제는 숫자로 이루어진 것이 아니다 보니, 반복문의 i를 계속 star..

1. 문제 설명 2565번: 전깃줄 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. www.acmicpc.net 두 개의 전봇대가 존재한다. 두 전봇대 사이엔 여러 전깃줄이 존재한다. 전봇대의 높이는 1~10으로 표현되는데, 전깃줄은 다음 그림과 같이 겹칠 수 있다. 최소한의 전깃줄을 제거해서 모든 전깃줄이 서로 교차하지 않도록 만들어라. 2. 푸는 원리 해당 문제를 LIS로 생각만 할 수 있다면 쉽게 풀리는 문제다. 하지만 그렇게 생각하기가 꽤나 어렵다. 따라서 필자는 먼저 전깃줄 문제를 어떻게 LIS 문제로 볼 수 있는지부터 설명하고자 한다. 위 사진의 ..

1. 문제 설명 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. www.acmicpc.net 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하고, 해당 조건을 만족하는 부분 수열 중 하나를 출력하라. → 원래 최장 증가 부분 수열의 길이만 구하던 문제에서 이제 그 구성요소를 구하는 문제로 바뀌었다. 2. 푸는 원리 처음에 문제 푸는 데 정말 헤맸는데, 그 이유는 해당 문제도 다른 LIS처럼 이분탐색을 써서 풀려고 했기 때문이다. 하지만 이분탐색의 경우 큰 문제가 있는데, 바로 LIS의 구성요소를 구하기 힘들다는 점이다. 왜 그런지 한번 보자. 먼저 값을 구하기 위해 조작하는 배열을 A, 수열 전체를 담는 배..

1. 문제 설명 11000번: 강의실 배정 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. www.acmicpc.net 강의의 시작 시간과 종료 시간이 주어졌을 때 해당 강의들을 전부 소화할 수 있는 최소 강의 수를 구하여라. 2. 푸는 원리 저번에 풀었는데 틀렸다. 틀리는 방법도 똑같았다 ㅜㅜ. 다시 푸는 방법을 정리해 보겠다. 배열 혹은 List에 강의 시작 시간이 빠른 순으로 강의를 정렬한다. 강의의 끝 시간을 기준으로 값들을 정리하는 Priority Queue를 만든다. 자 이제 List에 존재하는 값들을 차례로 순회할 것이다. 우리가 현재 조회하는 강의를 A라고 해보자. A의 강의 시작 시간이 오후 1시라고 할 때, 현재 시각을 오후 1시라고 가정하는 것이다. 이렇게 list에서 현..

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값..

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, …) 따라서 최장 공통 부분 수열이라면, 두 문자열에서 공통으로 순서가..

1. 문제 설명 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. www.acmicpc.net 벽이 부분을 부수고 거기서 이동할 수 있는 공간의 크기를 구하라. 원래 부터 0이었던 공간은 그냥 0으로 출력, 원래 1(벽)이었던 공간은 그 벽을 부수고 좌우로 최대한 이동할 수 있는 공간의 개수를 해당 자리에 출력 2.문제 푸는 원리 처음엔 벽 하나하나 마다, 그 자리를 부수고, bfs를 돌렸다. 이렇게 풀었더니 시간초과가 났다. 다른 방법이 생각나지 않아서 다른 사람이 푼 원리를 읽었다..

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번: 분수찾기 (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번: 세탁소 사장 동혁 (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 (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(..

2745번: 진법 변환 (acmicpc.net) 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 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(); // 입력값, 진법 받기 String s = sc.next(); int ..

2563번: 색종이 (acmicpc.net) 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 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(); // 도화지 만들기 String [][] arr= new String[100][100]; // 도화지 안..

10798번: 세로읽기 (acmicpc.net) 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 1. 내 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[][] word = new char[5][15]; for (int i = 0; i < 5; i++) { String s= sc.nextLine(); for (int j..

2566번: 최댓값 (acmicpc.net) 1. 내 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[][] eightyNine = new int[9][9]; int max = 0; int location = 0; int location2 = 0; for (int i = 0; i max) { max = eightyNine[i][j]; location ..

2738번: 행렬 덧셈 (acmicpc.net) 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 1. 내 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] former = new int[N][M]; int[][] latter = ..