- 자바 내용 보충
- nextInt() => 정수형 입력 받음
- next() => 스페이스로 구분하여 문자열 입력 받음
- nextLine() => 문자열 1줄
여러 번 반복은 메서드를 만들어 처리한다.
- 알고리즘: 문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합
- 결정트리: 왼쪽에서 오른쪽으로 이동하고 조건이 성립하면 위로, 성립하지 않으면 아래로
- 중앙값을 구하는 방법:
import java.util.Scanner;
public class WeekOne{
static int med(int a, int b, int c){
if(a>=b){
if(b>=c){
return b;
}
else if(c>=a){
return a;
}
else{
return c;
}
}
else if(a > c){ // a<b 일 때
return a;
}
else if(b > c){ // a<b와 a<=c 일 때
return c;
}
else{ // a<b , a<=c, b<=c 일 때
return b;
}
}
}
&& 이나 || 을 쓰면 효율이 떨어지는 이유:
&&와 ||를 쓰면 코드는 읽기 편해질(Readable) 수 있지만, 컴퓨터 입장에서는 했던 비교를 또 해야 하는 비효율이 생긴다.
그래서 성능이 중요한 알고리즘(예: 대량의 데이터를 처리할 때)에서는 조건문을 분리하여 비교 횟수를 최소화하는 방식을 선호한다
if ((b <= a && a <= c) || (c <= a && a <= b))
- 여기서 컴퓨터는 b <= a를 확인하고, a <= c를 확인한다.
- 만약 이게 거짓이라면 || 뒤로 넘어가서 c <= a를 다시 확인합니다.
- 이미 앞에서 a와 b, a와 c의 관계를 어느 정도 파악했음에도 불구하고, 다음 조건절에서 똑같은 비교를 반복하게 된다.
가우스 덧셈으로 정수들의 합 처리하기
for(int i = 0; i < n / 2; i++){
sum += (n - i) + (k); // (n-i)는 뒤에서 오는 수, k는 앞에서 가는 수
k++;
}
// 홀수일 때 처리
if (n % 2 != 0) {
sum += (n / 2) + 1; // 딱 중간에 있는 값을 더해줌
}
공식화: int sum = n * (n + 1) / 2;
for문 종료한 다음에도 변수를 사용하려면 for문 밖에서 i를 선언하고 사용
int i;
for(i = 1; i<=n; i++){
sum+=i;
}
사전 판단 반복문과 사후 판단 반복문의 차이점: 사후 판단은 루프 본문 반드시 한 번 실행 (ex, do-while문)
구조적 프로그래밍: 하나의 입구와 하나의 출구를 가진 구성요소만을 계층적으로 배치하여 프로그램 구성
=> 순차, 선택, 반복
오른쪽 위가 직각인 이등변 삼각형: 안에서 처리!
static void triangleLB(int n){
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
System.out.print(" ");
}
for(int k=0;k<n-i;k++){
System.out.print("*");
}
System.out.println();
}
}
자료구조: 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
데이터 단위: 데이터를 구성하는 한 덩어리
자료구조: 자료를 효율적으로 이용하기 위해 컴퓨터에 저장하는 방법
- 배열
- 배열은 같은 자료형으로 이루어진 구성 요소가 모인 것이다.
- int[] a = new int[5];
- 변수 a가 참조한다고 설정 / 배열 본체와 함께 length라는 변수가 만들어진다. (메소드 아님)
배열의 구성 요소는 설정하지 않으면 자동으로 0으로 초기화된다!
- clone() 메소드는 배열 본체의 복제본을 참조한다.
- 배열의 최댓값을 비교 -> a[0] 요소부터 a[n-1]요소까지 살펴보면서 갱신하는데
- 배열의 요소를 하나씩 차례대로 살펴보는 과정을 주사 (순회, traverse)라고 한다. => 스캔
int[] a = height; (height가 다른 배열을 참조하고 있을 때)
참조처를 복사하는 행위
=>배열 본체를 참조하는 것이다.
- 난수 생성 => java util 패키지의 random 클래스 사용
Random rand = new Random();
int num = rand.nextInt(n); 0부터 n-1사이의 난수 생성
- 컴퓨터에서 생성하는 난수는 진짜 난수가 아니다.
- 컴퓨터가 계산해 둔 의사난수이며, 이 결과만 가지고 난수를 생성한다.
- 컴퓨터를 켜면 계산된 결과만 가지고 난수를 생성한다.
=> 그래서 seed값을 항상 다르게 전달해야 하는데 보통 현재 시간을 이용한다.
rand.nextInt(현재시간);
- 배열 요소를 역순으로 정렬하는 방법:
- 맨 앞과 맨 뒤를 교환 -> 두 번째와 마지막 전 요소와 교환 -> ...
- i=0과 n-i-1 요소와 교환, 이게 공식이다.
요소를 교환할 때 swap메서드를 만들어서 사용하고
그 원리는 같은 자료형을 가진 변수 t를 설정 -> t = x; x = y; y = t; 이런 식으로 진행
static void swap(int[] a, int idx1, int idx2){
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void reverse(int[] a){
for(int i = 0; i<a.length/2;i++){
swap(a, i, a.length-i-1);
}
}
- 기수 변환: 10진수를 n진수로 바꾸려면 정수를 n으로 나눈 나머지를 구하는 동시에 그 몫에 대해 나눗셈을 반복해야 한다.
10진수: 0 1 2 3 4 5 6 7 8 9
8진수: 0 1 2 3 4 5 6 7 => 8의 거듭제곱 값을 가진다. 이 숫자를 다 사용하면 2자리가 된다
16진수: 0 1 2 3 4 5 6 7 8 9 A B C D E F 이 숫자를 다 사용하면 2 자리가 된다.
1. 익숙한 '10진수'로 먼저 이해하기
10진수는 한 자리에 쓸 수 있는 숫자가 0부터 9까지(총 10개)입니다.
- 0, 1, 2, ..., 8, 9 (끝!)
- 9 다음에는 더 이상 한 자리에 표현할 숫자가 없죠?
- 그래서 자릿수를 늘려서 10이 됩니다.
즉, "쓸 수 있는 가장 큰 숫자(9)를 넘어가면 두 자리(10)가 된다"는 것이죠.
2. 8진수 (Octal)
8진수는 한 자리에 쓸 수 있는 숫자가 **0부터 7까지(총 8개)**입니다. 8이라는 숫자는 쓰지 못합니다.
- 진행: 0, 1, 2, 3, 4, 5, 6, 7 (끝!)
- 다음: 7 다음에 8을 써야 하는데, 8진수에는 8이라는 기호가 없습니다.
- 결과: 그래서 자릿수를 올려서 10이 됩니다.
- (여기서 10은 십이 아니라, 10진수의 8을 의미합니다.)
3. 16진수 (Hexadecimal)
16진수는 한 자리에 쓸 수 있는 문자가 **0부터 F까지(총 16개)**입니다.
- 0~9까지 쓰고, 10부터는 알파벳을 빌려옵니다. (A=10, B=11, ..., F=15)
- 진행: 0, 1, ..., 9, A, B, C, D, E, F (끝!)
- 다음: F(15) 다음은 16이어야 하는데, 한 자리에 16을 표현할 문자가 더 이상 없습니다.
- 결과: 그래서 자릿수를 올려서 10이 됩니다.
- (여기서 10은 십이 아니라, 10진수의 16을 의미합니다.)
static int cardConvR(int x, int r, char[] d){
int digits = 0;
String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
do{
d[digits++]=dchar.charAt(x%r); //역순으로 배치
x=x/r;
}while(x!=0);
return digits;
}
String 클래스 : 기억해야 할 주요 메소드 =>
char charAt(int i)
int length()
boolean equals(String s)
- 소수: 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않습니다.
public static void main(String[] args){
int counter = 0;
for(int n = 2; n <= 1000; n++){
int i;
for(i = 2; i < n; i++){ //만약 n이 13일 때
counter++;
if(n % i == 0){
break;
}
}
if(n == i){ //나누어떨어지지 않고 나오는 i값이 13이다.
System.out.println(n);
}
}
System.out.println("나눗셈을 수행한 횟수: " + counter);
}
n이 소수라면 변수 i가 n과 같은 값이고
n이 소수가 아니라면 변수 i가 n보다 작은 값이다.
만약 2 또는 3으로 나누어 떨어지지 않는다면 4나 6으로도 나누어 떨어지지 않는다.
-> 이 코드는 불필요한 나눗셈을 하고 있다.
<알고리즘 개선>
전에 구해두었던 소수들로 나눗셈을 진행한다.
4이상의 짝수는 2로 나누어떨어지므로 소수가 아니기 때문에
홀수를 계산한다. 3, 5, 7, 9....
for문은 i값을 1부터 하는데 prime[0]은 2이기 때문에 나눌 필요가 없다.
public class PrimeNum1 {
public static void main(String[] args){
int counter = 0;
int ptr = 0;
int[] prime = new int[500];
prime[ptr++] = 2;
for(int n = 3; n <= 1000; n += 2){ //홀수만
int i;
for(i = 1; i < ptr; i++){
counter++;
if(n % prime[i] == 0){ //만약 9이면 prime[1]인 3으로 나누어떨어진다.
break;
}
}
if(ptr == i){
prime[ptr++] = n;
}
}
for(int i = 0; i < ptr; i++){
System.out.println(prime[i]);
}
System.out.println("나눗셈을 수행한 함수 : "+counter);
}
}
나눗셈을 수행하는 횟수가 반 이상 감소한다.
=> 같은 답을 얻는 알고리즘은 하나가 아니다.
=> 빠른 알고리즘은 메모리를 많이 요구한다.
<알고리즘 개선>
100의 약수 대칭성
5x20 = 20x5
이런 식이기 때문에
정사각형 한 변의 길이까지만 소수로 나눗셈을 시도한다.
즉, 제곱근을 한 변으로 하는 이후의 직사각형에 대한 계산량을 줄이는 것이 핵심이다.
n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않습니다.
import java.util.Scanner;
public class WeekOne{
public static void main(String[] args) {
int counter = 0;
int ptr = 0;
int[] prime = new int[500];
prime[ptr++] = 2;
prime[ptr++] = 3;
for(int n = 5; n <= 1000; n += 2){
boolean flag = false;
for(int i = 1; prime[i] * prime[i] <= n; i++){
counter += 2;
if(n % prime[i] == 0){
flag = true;
break;
}
}
if(!flag){
prime[ptr++] = n;
counter++;
}
}
for(int i = 0; i < ptr; i++){
System.out.println(prime[i]);
}
System.out.println("곱셈과 나눗셈을 수행한 횟수 : " + counter);
}
}
- 자바에서의 다차원 배열: "구성 자료형으로 하는 배열"을 구성 자료형으로 하는 배열
int[][] x; //배열변수
x = new int[2][];
x[0] = new int[4];
x[1] = new int[4];
//다차원 배열 내부
참조하고 다시 참조하는 구조로 생각하자
행의 다른 요소가 연속으로 놓이지 않는다 = x[0][3] 바로 뒤에 x[1][0]이 저장되지 않는다.
다차원 배열의 복제는 최상위의 1레벨만 수행한다.
int[][] a = {{1, 2, 3, 4}, {5, 6, 7}};
int[][] b = a.clone();
//열 배열은 복제되지 않고 양쪽에서 참조된다.
배열 스캔은 보통 for-each문으로 수행한다.
- 클래스: 임의의 데이터형을 자유롭게 조합하여 만들 수 있는 자료구조이다.
class XYZ{
int x;
long y;
double z;
}
XYZ a = new XYZ();
//참조와 인스턴스 생성을 한 번에
- 중첩 클래스
- 멤버 클래스: 선언이 다른 클래스 또는 인터페이스 선언에 둘러싸인 클래스
- 내부 클래스: 정적으로 선언되지 않는 중첩 클래스
- 지역 클래스: 이름이 주어진 중첩 클래스, 어떤 클래스의 멤버도 될 수 없다.
- A. 멤버 내부 클래스 (Member Inner Class/Instance Inner Class)
- 특징:
- 가장 일반적인 형태의 내부 클래스입니다.
- 외부 클래스의 멤버 변수 위치에 선언됩니다.
- 외부 클래스의 private 멤버를 포함한 모든 필드와 메서드에 자유롭게 접근할 수 있습니다.
- 외부 클래스 인스턴스를 먼저 만든 후, outerInstance.new Inner() 형태로 생성합니다.
- 주의: 내부 클래스의 인스턴스는 외부 클래스의 인스턴스 참조를 몰래 가지고 있기 때문에 메모리 누수(Memory Leak)의 원인이 될 수 있습니다.
- 특징:
- 메서드(혹은 초기화 블록) 내부에 선언됩니다.
- 선언된 메서드 안에서만 사용할 수 있습니다 (지역 변수처럼).
- 메서드의 지역 변수 중 final 혹은 effectively final(값이 바뀌지 않는) 변수에만 접근 가능합니다.
- 특징:
- 클래스의 이름이 없습니다.
- 클래스 선언과 객체 생성을 동시에 합니다.
- 주로 인터페이스를 구현하거나 클래스를 상속받아 일회용으로 객체를 만들 때 사용합니다.
- 용도:
- 이벤트 리스너 처리나 쓰레드 객체 생성 등 단발성 로직에 많이 쓰입니다. (Java 8 이후로는 람다식으로 많이 대체됨)
- 특징:
다음부터 본격적인 알고리즘 공부와 자료구조에 도입한다.
기초부터 탄탄히!