순간을 기록으로

안녕하세요 luminous13입니다. 이번에는 백준 수정렬하기1 2750번 문제를 풀어보도록 하겠습니다. 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 데이터를 오름차순으로 정렬하는 문제입니다. 사실 정렬을 Arrays.sort()를 이용하여 쉽게 정렬할 수 있지만 이번에는 직접 정렬을 구현하면서 문제를 풀어보도록 하겠습니다. 여러 정렬 알고리즘 중 하나를 선택해야 합니다. 데이터 크기를 보니 최대 1,000이 올 수 있습니다. 데이터 크기가 크..

분석 * 이번 문제는 수 나열에서 부분 합을 여러번 구하는 문제다. * 배열의 구간 합을 구해야 될때에는 합 배열을 이용하면 시간복잡도를 O(n)에서 On(1)로 줄일 수 있다. * 합 배열 공식:S[i] = S[i-1] + arr[i] * [i,j] 구간 합 공식: S[j] - S[i-1] * 배열의 사이즈를 1 추가하여 인덱스가 1이 첫 번째 원소로 설정해야 합배열 첫 번째 원소도 규칙있게 구할 수 있다. * * 이번 문제에서 만약 합 배열을 이용하지 않고 이중 for문을 사용하면 수의 갯수*횟수이 연산횟수가 된다. * 100,000*100,000 = 10,000,000,000 이다. 즉 100억번 연산을 하게되고 시간은 100초가 소요될것이다. * 따라서 합배열을 사용해야하는 문제다. 수도코드 * ..

문제 N을 입력하면 1~N을 원소로하는 공집합을 제외한 부분집합을 출력하기 풀이 DFS를 이용해서 풀 수 있다. 예를들어 {1, 2, 3}이라는 집합이 있다고 하자. 이 집합의 공집합을 제외한 부분 집합의 갯수는 2^3-1이므로 7이다. 즉 원소마다 있느냐, 없느냐에따라 경우의 수가 2가지이고 원소의 갯수만큼 그만큼 곱해주면 모든 경우의 수가 나온다. 마지막에 공집합은 제외하니 -1을 하면된다. 그럼 DFS원리를 이용해서 이진트리로 풀어보자 코드 package 인프런.재귀와트리와그래프.부분집합구하기; /* * 어떤 집합의 모든 부분집합을 출력하는 문제 * */ public class Main { static int n; // 원소의 갯수 static boolean[] ch; // 부분 집합의 원소로 사용..

안녕하세요. 오늘은 싱클톤 패턴에 대해 알아보겠습니다. 싱글톤 패턴 싱글톤 패턴이란 인스턴스를 오직 한 개만 제공하는 클래스를 만드는 패턴입니다. 인스턴스가 무조건 한개여만 됩니다. 예를들어 오버워치를 하고 있는데 마우스 속도가 너무 느린거에요. 셋팅창을 열어 마우스 감도를 90으로 올렸어요. 그런데 이번에는 너무 마우스가 빨라서 속도를 다시 줄이려 마우스 감도를 60으로 줄이려고해요. 이때 만약 셋팅창 인스턴스가 여러개면 어떤 셋팅창에는 마우스 감도가 90이고 어떤 채팅창에는 마우스 감도가 60이라서 문제가 발생하게되죠. 이럴 때 싱글톤 패턴을 이용해서 문제를 해결하게 됩니다. 코드로 살펴보기 우선 App.java와 Settings.java파일을 만듭니다. public class Settings { }..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 후기 2차원 배열까지 접근하는 건 알겠는데 도저히 정렬을 어떤 식으로 해야 되는지 감이 안 왔다. Arrays.sort() 메소드의 경우 기본적으로 인자로 1차원 배열만 인자로 받기 때문이다. 다행히 Compartor를 이용해서 해결할 수 있었다. import java.io.*; import java.util.Arrays; import java..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 목표 평균 값을 구할 수 있다. 중앙값을 구할 수 있다. 최빈값을 구할 수 있다. 최댓값과 최솟값을 구할 수 있다. 푸는 순서: 1.문제 읽기 --> 2.수도코드 작성하기 --> 3.코드 작성하기 --> 4.테스트케이스 만들기. 맨 처음에 각 구하는 값을 함수 별로 담에서 구하려 했다. 하지만 생각보다 코드가 중복되는 걸 확인하고 함수로 분리하는 게 오히려 좋지 않을 수 있다는 생각이 들어 리팩토링 했다. 수도..