개발놀이터

package 배열응용3장.연속부분수열3다시4.my; import java.util.Scanner; public class Main { /** * -내 풀이- * two pointers algorithm 을 이용해 풀었는데 내 코드가 더 깔끔한 것 같다. 선생님의 코드는 너무 복잡함 * 피드백할 것은 없다. */ public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int m = kb.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = kb.nextInt(); } System.out.println(so..

package 배열응용3장.최대매출3다시3.my; import java.util.Scanner; public class Main { /** * -피드백- * sliding window 알고리즘을 이용하여 풀면 된다. * sliding window 는 two pointers algorithm 을 이용한 문제지만 딱히 two pointers algorithm 을 이용하지 않아도 된다. * 선생님의 풀이처럼 for 문 하나를 가지고 풀어도 된다. * * -선생님 풀이- * ex) 10개의 값을 3개만큼 합해서 최댓값을 구해야 한다면 * 1 2 3 4 5 6 7 8 9 10 * | | * | | * | | * 이렇게 칸을 이동시키면 된다. 즉, 앞에건 빼주고 뒤에건 더해주면 된다. * for (int i = k..

package 배열응용3장.공통원소구하기3다시2.my; import java.util.ArrayList; import java.util.Scanner; public class Main { /** * -내 풀이- * 도저히 생각이 나지 않아서 포기했다. * * -선생님 풀이- * 이번에도 two pointers algorithm 을 사용한 문제였다. * 이번에 눈여겨 볼 점은 어떤 배열을 오름차순으로 정렬하기 위해서는 Arrays 클래스의 sort 메서드를 사용하면 된다는 것과 * 교집합을 찾는 문제이기 때문에 p1 과 p2 가 같은 경우 p1, p2 둘을 동시에 증가시켜야 했다는 점이다. * * 그리고 p1 과 p2 중 작은 쪽을 하나 증가시켜야 한다는 점도 인상깊었다. * * int p1 = 0, p2..

package 배열응용3장.두배열합치기3다시1.my; import java.util.Scanner; public class Main { /** * -내 풀이- * 이중 for 문을 돌면서 각각의 숫자를 비교한 후 최솟값을 넣는 방향으로 진행했다. * 거기에 배열 두개를 그냥 새로운 배열로 만들어서 풀었다. * * --피드백-- * 두개의 정렬된 배열을 하나의 배열로 만드는 것이 아니라 각각의 배열에서 포인터를 도입해 비교하면 된다. * 그리고 문제를 잘못 이해하여 입력받은 두 배열은 정렬된 상태라는 것을 눈치채지 못했다. * * -선생님의 풀이- * two pointers algorithm 을 이용해 풀면 간단하게 풀린다. * * pt1 = 0, pt2 = 0; * while (pt1 < n && pt2..

Two-Pointers-Algorithm two pointers algorithm (이하 투 포인터 알고리즘) 알고리즘은 말 그대로 포인터를 사용해 배열에 쉽게 접근할 수 있게 해줍니다. 자바에서도 배열에 쉽게 접근하기 위해 포인터를 사용하는 경우가 종종 있습니다. 보통 lt (left), rt (right) 혹은 s (start), e (end) 혹은 p1, p2 이런식으로 포인터를 정해서 값을 하나씩 증가시키면서 배열을 참조합니다. 투 포인터 알고리즘을 사용하는 문제는 비교적 자주 만나볼 수 있으며 한번 익혀두면 나중에 써먹기 정말 편하다고 합니다. 물론 저는 세번밖에 안써봤습니다. 먼저 문제를 확인해보시죠 문제를 해석하자면 N개로 된 수열에서 N개의 부분집합 중에서 M이 되는 개수가 몇개냐라고 물어..

이번 시간에는 코딩테스트 준비를 하면서 문제를 풀다가 흥미로운 알고리즘을 발견해서 해당 내용을 포스팅하려고 합니다. 바로바로 '에라토스테네스의 체' 라는건데요. 이번에도 흥미로운 내용이 있으니 한번 둘러보고 가세요! 에라토스테네스의 체란? 에라토스테네스의 체는 말 그대로 어떤 물질을 걸러주는 '체'를 의미합니다. 여기서는 소수를 걸러주는 체가 되겠네요. 소수에 대해서 아주아주 간단하게 설명하고 넘어가도록 하겠습니다. 소수는 1과 자기자신으로밖에 나눠지지 않는 수를 말합니다. 2 3 5 7 ... 이런 숫자들을 말하죠 1과 자기자신으로밖에 나눠지지 않는 수라는 것은 소수를 공부했던 사람이라면 누구나 떠올릴 수 있는 개념입니다. 이것을 코딩으로 구현하려면 어떻게 해야할까요? 정말 우리가 흔히 알고있는 개념으..

시간복잡도 시간복잡도란 내가 만든 코드가 얼마나 효율적인지를 나타내는 척도입니다. 시간복잡도를 계산하면 코드의 어느 부분에서 시간을 많이 잡아먹고 있는지 대략적으로 알 수 있으며 코드를 리팩토링 할 때도 좋은 영향을 미칠 수 있습니다. 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은 무슨 의미일까요? 바로 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가?'를 고려한다는 의미입니다. 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 의미입니다. 그리고 이 시간복잡도는 빅-오 표기법을 사용해 나타냅니다. 빅-오 표기법 빅-오 표기법 말고도 빅-오메가 표기법, 빅..

이번 2장 배열에서는 기본적으로 배열과 for 문을 어떻게 설계하고 컴퓨팅적 사고를 하는지에 대해 물어보는 문제가 많았다. 그래서 딱히 중요한 문법이나 알고리즘이 많이 나오지 않았기 때문에 가장 중요했다고 생각되는 내용만 몇개 추려서 포스팅 할 예정이다. 2-5. 소수의 개수 input 값으로 숫자를 하나 부여받고 0부터 해당 값까지 소수의 개수를 구하는 문제 풀이는 두가지로 나뉜다. 1. 소수를 수학적으로 접근하는 방법 2. 알고리즘을 사용하는 방법 하지만 여기서 첫번째 방법으로 문제를 풀게되면 TimeLimitBreak 에 걸리기 때문에 옳지 못한 풀이이다. 하지만 정리해보자면 1. 소수를 수학적으로 접근하는 방법 나눠지는수 / 나누는수 이렇게 연산을 하는데 2중 for문을 돌면서 모든 값을 다 비교..

package 배열1차원2차원.멘토링2다시12.my; import java.util.Scanner; public class Main { /** * 내 머리가 빠가인가 이해가 안된다... */ public static void main(String[] args) { Scanner kb = new Scanner(System.in); int grade = kb.nextInt(); int count = kb.nextInt(); int[][] arr = new int[grade][count]; for (int i = 0; i < grade; i++) { for (int j = 0; j < count; j++) { arr[i][j] = kb.nextInt(); } } System.out.println(solutio..

package 배열1차원2차원.임시반장2다시11.my; import java.util.Scanner; public class Main { /** * 문제가 너무 이상해서 이런식으로는 절대 코딩테스트 안나올듯 * 오해의 소지가 너무 분명함 */ public static void main(String[] args) { Scanner kb = new Scanner(System.in); int input = kb.nextInt(); int[][] arr = new int[input][5]; for (int i = 0; i < input; i++) { for (int j = 0; j < 5; j++) { arr[i][j] = kb.nextInt(); } } System.out.println(solution(inp..