Java/Algorithms

문제 -1, 0, 1로만 이루어진 가로, 세로의 길이가 3^n인 종이가 주어졌을 때 같은 숫자로만 이루어진 종이가 종류별로 몇 개인지 출력하라 접근 방식 현재 종이가 같은 숫자로만 이루어지지 않은 경우에는 종이를 9등분 하고 같은 숫자로만 이루어져 있을 때만 해당하는 종이의 카운트를 1씩 올려줘야 한다. 종이의 가로, 세로 길이는 3의 n제곱으로만 주어지기 때문에 같은 숫자로 이루어지지 않은 경우에는 3으로 범위를 나눠주면서 재귀를 계속해서 돌려주면 된다. 예를 들어 가로, 세로의 길이가 27이고, 해당 종이가 같은 숫자로만 이루어지지 않았으면 가로, 세로 길이가 9인 종이 9개로 나눌 수 있고 이 종이를 다시 3인 종이와 1인 종이로 나눌 수 있다. 나눌 때마다 현재 종이가 같은 숫자로 이루어진지 확인..

문제 정해진 출력 양식에 맞게 주어진 반복 횟수만큼 반복해서 출력하라 접근 방식 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." ____"재귀함수가 뭔가요?" ____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. ____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. ____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 ..

문제 수포자 3명이 일정한 규칙으로 정답을 찍었을 때 가장 많은 문제를 맞힌 사람의 번호를 리턴하라 (동률인 경우에는 번호가 빠른 순으로 리턴한다.) 접근 방식 int[][] stupids = new int[][]{ new int[]{1, 2, 3, 4, 5}, new int[]{2, 1, 2, 3, 2, 4, 2, 5}, new int[]{3, 3, 1, 1, 2, 2, 4, 4, 5, 5} }; 우선 각각의 수포자는 위와 같은 순서대로 문제를 찍으니 주어진 정답 배열을 순회하며 각 수포자의 찍기 규칙과 비교하며 맞힌 문제가 몇 개인지 카운트하고 가장 많이 맞힌 사람을 찾으면 된다. 주의해야 할 점은 정답 배열과 찍기 규칙의 길이가 다르기 때문에 찍는 순서가 마지막이 된 경우에는 배열의 인덱스를 다시 ..

문제 명함의 가로, 세로 길이가 주어졌을 때 모든 명함을 담을 수 있는 가장 작은 명함 지갑의 넓이를 구하라 접근 방식 가로세로 16050 23070 36030 48040 만약 명함의 길이가 위와 같이 주어졌다면 가로의 가장 긴 길이와 세로의 가장 긴 길이를 찾아 지갑을 만들면 모든 명함을 넣을 수 있다. 하지만 문제에서 구해야 하는 것은 지갑의 최소 넓이이기 때문에 생각을 좀 달리해야 한다. 가장 긴 가로와 세로 길이의 지갑이면 명함을 모두 넣을 수 있으니 명함을 90도 회전하는 경우에는 좀 더 작은 면적의 지갑으로도 명함을 모두 보관할 수 있다. 가로세로 16050 27030 36030 48040 바로 위와 같이 가로보다 세로가 긴 경우 둘의 길이를 바꿔준 후에 (90도 회전) 가로와 세로의 가장 큰..

문제 유명한 하노이 탑 문제로 1번 탑에서 3번 탑까지 원판의 순서를 유지하면서 옮기기 위한 과정과 이동 횟수를 출력하는 문제다. 접근 방식 재귀를 사용해서 풀 수 있는 교과서 같은 문제로 하노이 탑에 대해서는 잘 알고 있지만 코드로 짜는건 많이 어려웠다. (재귀가 참 이론은 쉬운데 귀납적으로 생각하고 구현하는 것이 어려운거 같다...) 위에서부터 1번 원판, 2번 원판, ... , n번 원판이라고 했을 때 맨 밑에 있는 n번째 원판을 제외한 모든 원판을 2번 탑으로 옮길 수 있다면 n번 원판을 3번 탑으로 옮길 수 있다는 것이 성립된다. 그 후에 2번째 탑에 있는 원판들을 모두 3번 탑으로 그대로 옮길 수 있다면 하노이 탑의 원리대로 1번 탑의 원판들을 그대로 3번 탑으로 옮길 수 있는 것이다. 그러면..

문제 정수 A, B, C가 주어졌을 때 A를 B번 곱한 값을 C로 나누었을 때 몫을 구하라 접근 방식 문제 자체는 엄청 간단한 문제지만 시간제한과 메모리 제한이 걸려있기 때문에 반복문이나 재귀로 하나하나 다 곱하고 나누면 통과할 수 없는 문제다. (값의 표현 범위를 벗어나기도 한다) 반복문으로도 풀 수 있고 재귀로도 풀 수 있는 문제지만 재귀를 공부할 겸 재귀로 풀어보았다. 우선 반복문으로 풀면 메모리 초과가 발생할 일은 없지만 재귀로 풀 때는 조심해야 할 부분이 있는데 재귀 호출을 B만큼 반복하면 호출 스택에 그만큼 쌓여 B의 값이 큰 경우에는 메모리가 초과되기 때문에 재귀 호출을 최대한 줄이는 방식으로 풀어야 한다. (x ^ n) * (x ^ n) = x^2n 위와 같은 법칙을 생각해서 풀면 되는데 ..

문제 정렬된 배열 두 개가 주어졌을 때 두 배열을 정렬된 상태로 합치는 문제 접근 방식 {2, 3, 5, 9} {1, 4, 7} 위와 같은 배열이 두 개 주어졌을 때 1, 2, 3, 4, 5, 7, 9 순서대로 정렬해야 한다. 두 개의 배열은 이미 정렬된 상태이니 각 배열의 첫 번째 인덱스들부터 서로 비교하며 작은 순서대로 다른 배열에 추가하거나 출력해주면 된다. 병합 정렬의 개념에 대해서 공부하기 좋은 문제로 이미 정렬된 두 개의 배열이 주어지기 때문에 풀기가 쉬웠다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS..

문제 R, G, B 세 가지 색상으로 이루어진 그림이 주어졌을 때 적록색약인 사람과 아닌 사람이 볼 수 있는 구역의 수를 구하라 접근 방식 적녹색약인 사람은 R과 G를 같은 색깔로 볼 것이기 때문에 둘을 하나의 색으로 취급해서 BFS를 돌면서 출발지가 몇 개인지 카운트하면 되고 색약이 아닌 사람은 세 가지 색상 모두 출발지를 카운트하면 된다. 풀고 나니 반복문의 사용이 쓸데없이 많은거 같아 반복문을 좀 더 효율적으로 돌 수 있는 방법을 생각해봐야겠다. 풀이 public class Main { private static final int[] dx = {1, 0, -1, 0}; private static final int[] dy = {0, 1, 0, -1}; private static final char[..