CS/Data Structure & Algorithm
연속 배열
1. 문제유형 - 연속 배열 유형 2. 푸는 방식 - count, sum 매커니즘 3. 정리 4. 출처 문제 유형 주어진 배열에 1이 연속으로 있으면 1씩 추가되는 배열이며, 합계를 구해야 되는 문제입니다. 이런식의 문제유형을 연속 배열 유형이라고 제 마음대로 정했습니다.. 사실 배열 탐색 유형의 일종이라 봐도 됩니다. 푸는 방식 이것을 풀 때 보통 맨 왼쪽 index를 기준으로 한칸씩 비교하면서 차례로 옮기는데 배열이라서 점수 배열로 또다시 만들어서 풀 필요가 없습니다. 변수로만 해결할 수 있는 문제는 최대한 변수로 해결하는 것이 좋습니다! 이와같이 cnt, sum 단 두개의 변수로 해당 문제를 해결하였습니다. int cnt = 0; int answer = 0; for (int i = 0; i < ar..
숫자 뒤집는 방법
알고리즘을 풀다가 숫자를 뒤집어야 하는 상황이 나와서 한번 정리해서 올립니다. 기존에 생각했던 방식은 toString() -> toCharArray() -> 배열 순서 바꾸기 -> new String(arr) -> Integer.parseInt() ... 딱 봐도 효율성이 떨어지는 코드였습니다. 새로운 방식은 위와 같이 문자열로 바꿔서 작업 할 필요 없이 수 계산으로만 바꿀 수 있습니다. 자세한 방식은 밑 그림을 참고 바랍니다.
소수 판별, 에라토스테네스 체
소수란? 1과 자기 자신을 제외한 나머지 수로 나누어 떨어지지 않는 수입니다. 소수 판별 함수 1일 경우에는 무조껀 소수가 아니므로 먼저 조건문을 통해 걸러냅니다. 이후 2부터 n까지의 수를 한개씩 비교하며 정확히는 1과 자기자신 수를 제외한 나머지 수를 비교하며 나머지가 0이 1개라도 있을 경우 소수가 아니기 때문에 false를 반환하도록 구성하였습니다. public boolean prime(int n) { if (n == 1) return false; for(int i = 2; i < n; i++) if(n % i == 0) return false; return true; } n까지의 수 중에서 소수 고르기 직접 다 비교 직접 비교하는 방식입니다. int answer = 1; // 2는 고정으로 포함..
[Array] 4. 피보나치 수열
import java.util.*; /** */ public class Main { public int[] solution(int n) { int[] answer = new int[n]; for(int i = 0; i < n; i++) { if (i < 2) answer[i] = 1; else { answer[i] = answer[i-2] + answer[i-1]; } } return answer; } public static void main(String[] args) { Main m = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int a : m.solution(n)) { System.out.print(a + ..
[Array] 3. 가위바위보
import java.util.*; /** */ public class Main { public char[] solution(int n, int[] A, int[] B) { char[] answer = new char[n]; // 1 : 가위, 2 : 바위, 3 : 보 // 1 < 2, 2 < 3, 3 < 1 for(int i = 0; i < n; i++) { if(A[i] == B[i]) answer[i] = 'D'; else if(A[i] == 1 && B[i] == 2) answer[i] = 'B'; else if(A[i] == 2 && B[i] == 3) answer[i] = 'B'; else if(A[i] == 3 && B[i] == 1) answer[i] = 'B'; else answer[i]..
[Array] 2. 보이는 학생
/* [ 틀린 풀이 ] 1. 뒤에 더 큰 사람이 있다는 것을 인지하지 못했습니다. cm[i] < cm[i+1]으로 했기 때문에 바로 옆 사람만 비교하여 만족하지 못하면 바로 리턴하게 만들었습니다. 2. 반대로 볼 수 없는 사람만 제외하는 방법을 생각했습니다. 하나 하나 비교해서 count하는 것이 아닌 볼수 없는 사람들만 전체 학생 수에서 -1을 진행하였습니다. [ 풀이 ] 아예 taller와 for문으로 돌아가는 i를 위치를 바꿔서 진행하였습니다. */ import java.util.*; class Main { public int solution(int n, int[] cm) { int cnt = 1; int taller = cm[0]; for(int i = 1; i < n; i++) { if(cm[i..
[Array] 1. 큰 수 출력하기
import java.util.*; /** 1. i와 j를 두어 각각 인덱스 -1, 0을 가리키게 하였습니다. 이후 loop를 돌리면서 각각 비교하여 answer 배열에 추가할 수 있게 하였습니다. 하지만 answer의 배열 사이즈를 입력 배열과 똑같이 해야됬었고 그 순서에 따라 j 인덱스가 움직여져서 빈 공간은 0으로 채워져서 표시되었습니다. 2. 첫번째로 배열을 받아서 출력하는 법을 알게 되었습니다. main에서 for문을 사용하여 nextInt()로 한개씩 받으면 됩니다. 출력도 마천가지로 for each문을 사용해 한개씩 출력하면 됩니다. 두번째로 배열을 단순히 Array로 선언하지 않고 ArrayList로 선언하는 것이 좋습니다. 더 많은 메서드를 제공합니다. 그 중 add()를 이용하여 배열 ..
[String] 12. 암호
import java.util.*; /** 1. 못풀었습니다,, 2. 첫번째로 문자를 7자리로 나누어 숫자로 변환하는 단계입니다. substring으로 index 0 부터 index 7 전까지 나눈 다음 replace를 사용하여 #은 1로 *은 0으로 대체합니다. 두번째로 문자열로 나온 수를 parseInt를 사용하여 2진수로 int형으로 저장합니다. 그 후 (char)로 형변환하여 이를 문자로 인식하도록 하여 출력합니다. 마지막으로 이 과정을 반복하기 위해 str.substring을 이용하여 str 자체를 7 index부터 끝까지 잘라서 넣음으로써 위의 코드를 반복할 수 있게 합니다. */ public class Main { public String solution(int n, String str) {..
[String] 11. 문자열 압축
import java.util.*; /** 1. 내가 생각한 알고리즘 0 인덱스로 시작해서 차례차례 한 문자씩 비교하는 방법을 사용하였습니다. 0번째 인덱스를 char 변수에 저장하고 다음 인덱스로 넘어갑니다. 다음 인덱스가 이전에 저장했던 변수값과 같다면 count를 ++합니다. 만약 다르다면 answer에 count를 추가합니다. 2. 좀 더 효율적인 강의 알고리즘 문자 1개만 이용한다면 StringBuilder보다 String이 효율적일 수 있습니다. StringBuilder의 효율성은 객체를 여러개 생성해야 할 때 빛을 발하는데 지금은 문자 1개만 다루고 있으므로 String으로 해도 됩니다. String을 toCharArray()해서 배열 인덱스로 접근하는 것 보다 그냥 String의 메서드인 ..
[String] 10. 가장짧은 문자거리
문자 거리 구하고 싶을 때는 >> 방향으로 한번 탐색하고 한번 탐색하고 후에, p) answer[i] = p; } } return answer; } public static void main(String[] args) { Main m = new Main(); Scanner in = new Scanner(System.in); String str = in.next(); char c = in.next().charAt(0); for(int i : m.solution(str, c)) { System.out.print(i + " "); } } }