CS/자료구조
[자료구조] 기초수학 문제
meizzi
2024. 8. 16. 20:43
728x90
반응형
1. 파스칼 삼각형
- 이항계수를 삼각형 모양의 기하학적인 형태로 배열한 것
- 첫 번째 줄에는 숫자 1을 쓴다.
- 그 다음 줄부터는 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다.
- 삼각형의 행의 수가 주어지면 파스칼의 삼각형 출력
- 풀이
- 행의 수에 대해 이중 반복문을 돌아 만일 j가 0이거나 i와 j가 같은 경우에는 외각 지역인 숫자가 1인 곳을 의미한다.
- 아니면 위의 왼쪽 값과 오른쪽 값을 더하면 된다.
- 왼쪽 값은 위의 배열인 i - 1에서 j - 1의 값 / 오른쪽 값은 위의 배열인 i - 1에서 j의 값
public static ArrayList<ArrayList<Integer>> solution(int numRows) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
ArrayList<Integer> list = new ArrayList<>();
for (int j = 0; j < i + 1; j++) {
if(j == 0 || j == i) {
list.add(1);
} else {
int x = result.get(i-1).get(j-1); // 왼쪽
int y = result.get(i-1).get(j); // 오른쪽
list.add(x+y);
}
}
result.add(list);
}
return result;
}2. 순열 응용
- 양의 정수로 이루어진 arr 배열이 주어질 때 해당 데이터로 만들 수 있는 permutation 중 아래 조건 만족
- 현재 데이터보다 이전의 큰 수 출력
- 한 번의 swap으로 출력 가능한 큰 수 출력
- 예시
- 3, 2, 1 -> 3, 1, 2
- 1, 9, 4, 7, 6 -> 1, 9, 4, 6, 7
- 1, 1, 2, 3 -> 1, 1, 2, 3
- 풀이
- arr가 비어있거나 2보다 작은 경우에는 swap이 필요 없으니까 바로 반환
- 인덱스 값을 -1로 저장해놓고 반복문을 거꾸로 돌면서 앞의 값이 현재 값보다 작으면 인덱스 값을 현재 i 값에서 1 감소
- 만일 인덱스 값이 -1 그대로면 원래 arr 값 그대로 반환
- 아니면 반복문을 한번 더 거꾸로 돌면서 만일 현재 값이 인덱스에 해당하는 값보다 작거나 만일 현재 값과 그 전 값이 같으면 그 값을 바꿀 경우 더 큰 수가 되기 때문에 다른 경우에만 값 변환
- 현재 값과 인덱스에 해당하는 값 변경
public static void solution (int[] arr) {
if (arr.lengrh == 0 || arr.length < 2) return;
int idx = -1;
for (int i = arr.length-1; i >= 1; i--) {
if (arr[i] < arr[i-1]) {
idx = i - 1;
break;
}
}
if (idx == -1) {
System.our.println(Arrays.toString(arr));
return;
}
for (int i = arr.length-1; i > idx; i--) {
if (arr[i] < arr[idx] && arr[i] != arr[i-1]) {
int tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
break;
}
}
}3. 문자열 순열
- 주어진 문자열 s1, s2에서 s1을 permutation을 한 문자열이 s2의 부분 문자열에 해당하면 true, 아니면 false 반환
- 예시
- s1: "ab" / s2: "adbak" -> true 반환
- 풀이
- 기본 permutation 활용
- permutation을 한 문자열 배열을 구하고 contains로 문자열이 포함되어 있는지 확인
public static boolean solution (String s1, String s2) {
boolean[] visited = new boolean[s1.length()];
char[] out = new char[s1.length()];
ArrayList<String> list = new ArrayList<>();
permutation(s1.toCharArray(), 0, s1.length(), s1.length(), visited, out, list);
for(String s : list) {
if(s2.contains(s)) return true;
}
return false;
}
4. 행복한 수 판별
- 행복한 수
- 각 자리수를 제곱한 것을 더하는 과정을 반복했을 때 1로 끝나는 수
- 행복한 수가 아니라면 1에 도달하지 못하고 같은 수열 반복
- 행복한 수라면 true, 아니면 false 반환
public static boolean solution (int n) {
HashSet<Integer> set = new HashSet<>();
while(set.add(n)) {
int sqaureSum = 0;
while(n > 0) {
int remain = n % 10;
sqaureSum += remain * remain;
n /= 10;
}
if(sqaureSum == 1) {
return true;
} else {
n = sqaureSum;
}
}
return false;
}5. 땅의 둘레
- grid[i][j]가 1은 땅, 0은 물
- grid한 cell의 변의 길이는 1
- 지도에는 하나의 독립된 영토만 있고 분리된 땅은 없음
- 땅 내부에 물은 존재하지 않음
- 이때, 땅의 둘레 출력
- 풀이
- 방향 표시를 위한 이차원 배열 선언
- 현재 땅이 1인 경우 방향 배열을 돌려 주변에 물이나 벽이 있는지 체크하여 맞으면 둘레 길이 1 증가
public static int solution (int[][] grid) {
int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int cnt = 0;
int row = grid.length;
int col = grid[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(grid[i][j] == 1) {
for (int[] d : directions) {
int x = i + d[0];
int y = j + d[1];
if(x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == 0) {
cnt++;
}
}
}
}
}
return cnt;
}6. 카탈랑 수
- 카탈랑 수
- 1, 1, 2, 5, 14, 42, 132, 429, ...
- 1, 1, 2, 5, 14, 42, 132, 429, ...
- 카탈랑 수의 n번째 값
public static int solution (int n) {
int result = 0;
if (n <= 1) return 1;
for(int i = 0; i < n; i++) {
result += solution(i) * solution(n-i-1);
}
return result;
}7. 팰린드롬
- 회문 또는 팰린드롬은 앞 뒤 방향으로 같은 순서의 문자로 구성된 문자열
- ex) "abba", "kayak", "madam"
- 유사회문은 문자열 그 자체는 회문이 아니지만 한 문자를 삭제하면 회문이 되는 문자열
- 주어진 문자열을 확인 후 문자열 종류에 따라 다음과 같이 출력
- 회문: 0 / 유사회문: 1 / 기타: 2
public static int solution (String str) {
return isPalindrome(0, str.length-1, str.toCharArray(), 0);
}
public static int isPalindrome(int left, int right, char[] arr, int delCnt) {
while(left < right) {
if(arr[left] != arr[right]) {
if(delCnt == 0) {
if(isPalindrome(left+1, right, arr, 1) == 0 || isPalindrome(left, right-1, arr, 1) == 0) {
return 1;
} else {
return 2;
}
} else {
return 2;
}
} else {
left++;
right++;
}
}
return 0;
}8. 1차 방정식
- 주어진 1차 방정식 풀이
- 해당 방정식은 "+", "-", "x", 상수로만 구성
- 해가 없으면 "No solution" 출력
- 해가 무한대인 경우 "Infinite solutions" 출력
- 해가 있는 경우 x의 값을 "x=" 형태로 출력
public static String solution (Stirng equation) {
String[] parts = equation.split("=");
int[] leftSide = evaluate(parts[0]);
int[] rightSide = evaluate(parts[1]);
if(leftSide[0] == rightSide[0] && leftSide[1] == rightSide[1]) {
return "Infinite solutions";
} else if(leftSide[0] == rightSide[0]) {
return "No solution";
} else {
return "x=" + (rightSide[1] - leftSide[1]) / (leftSide[0] - rightSide[0]);
}
}
public static int[] evaluate (Stirng str) {
int[] result = new int[2];
boolean isMinus = false;
int idx = 0;
while (idx != str.length()) {
char c = str.charAt(idx++);
if (c == "+") {
continue;
}
if (c == "-") {
isMinus = true;
continue;
}
if (c == "x") {
retult[0] += isMinus ? -1 : 1;
} else {
if (idx < str.length() && str.charAt(idx) == "x") {
result[0] += isMinus ? -(c-'0') : (c-'0');
} else {
result[1] += isMinus ? -(c-'0') : (c-'0');
}
}
isMinus = false;
}
return result;
}9. 좋은 수
- 짝수 인덱스 위치에는 짝수
- 홀수 인덱스 위치에는 소수 (2, 3, 5, 7)
- 인덱스는 0부터 시작
- 1 이상의 정수 n이 주어졌을 때, n 자리로 구성될 수 있는 좋은 수의 개수 출력
- 단, n의 값에 따라 값이 클 수 있으니 결과는 10^9+7로 나머지 연산을 한 결과 출력
final static int mod = (int) 1e9 + 7;
public static int solution(long n) {
return (int)(recursion(5, (n+1)/2) * recursion(4, n/2) % mod);
}
public static long recursion(long x, long y) {
if(y == 0) return 1;
long p = recursion(x, y/2);
return p*p*(y%2>0 ? x:1);
}10. 하노이의 탑
- 한 번에 하나의 원판 이동 가능
- 큰 원판이 작은 원판 위에 있으면 안됨
- 원판의 개수가 n일 때, 가장 왼쪽 기중으로부터 끝 기둥으로 이동하는 과정에 대해 출력
static StringBuffer sb;
public static void solution(int n) {
sb = new StringBuffer();
hanoi(n, 1, 2, 3);
System.out.println(sb);
}
public static void hanoi(int n, int start, int mid, int to) {
if(n == 1) {
sb.append(start + " " + to + "\n");
return;
}
hanoi(n-1, start, to, mid);
sb.append(start + " " + to + "\n");
hanoi(n-1, mid, start, to);
}728x90
반응형