[ 오버로딩 overloading ]

한 클래스 내에서 같은 이름의 메소드가 여러 개 정의될 때, 오버로딩 또는 메소드 중복이라고 한다.

  • 중복되는 메소드들은 매개변수의 개수 또는 타입이 달라야 한다.
  • 오버로딩은 자동으로 타입을 변환할 수 있다.
max(double n1, double n2){ }
max(double n1, double n2, double n3){ }

위와 같은 함수가 오버로딩 되었을 때, max(5, 10)을 호출하면
max(int n1, int n2)가 없기 때문에 매개변수의 타입이 자동으로 변환되어
max(double n1, double n2)가 호출된다.


[ 오버라이딩 overriding ]

수퍼클래스의 메소드와 서브클래스의 메소드가 이름, 매개변수의 목록, 반환 타입까지 모두 같을 때,
이를 메소드 오버라이딩, 메소드 재정의라고 한다.

이런 경우, 수퍼클래스 대신 서브클래스에 정의된 메소드가 사용된다.

< super 키워드 >

super 키워드를 통해서, 메소드 오버라이딩으로 인한 문제를 해결할 수 있다.
super.메소드 사용 시, 수퍼클래스와 서브클래스의 메소드가 동일하더라도
수퍼클래스의 메소드를 호출한다.

class A{
	int a;
	check(){ }
}

class B extends A{
	int a;
    check(){ 
    	super.check(); //A의 check를 호출한다.
    }
}
 
B objB = new B();

objB.check(); //오버라이딩으로 B의 check가 호출된다.

 

< equals와 toString 메소드 >

모든 객체는 Object라는 수퍼클래스의 서브클래스이다.
Object 클래스에는 여러 메소드들이 있는데 그 중, equals와 toString은 그대로 쓰기에는 부적절하다.

우리가 원하는 equals : 두 객체의 내용이 같은지를 비교
Object의 equals : 두 객체의 주소가 같은지를 비교

우리가 원하는 toString : 객체 내부 정보를 조합하여 정보를 보기 쉽게 반환하는 문자열
Object의 toString : 객체를 String으로 표현 ex) 객체@....

따라서 equals와 toString은 새롭게 오버라이딩 해줄 필요가 있다.

< equals 오버라이딩 >

  • equals 메소드의 매개변수를 Object 타입으로 명시하며 업캐스팅한다.
  • 매개변수의 실제 타입이 원하는 객체가 맞는지를 확인한다.
  • 매개변수로 넘어온 객체를 다시 다운캐스팅한다.
class Book{
	public boolean equals(Object obj){ //업캐스팅
    	if(obj != null && obj instanceof Book){ //원하는 객체인지 확인하기
     		Book oBook = (Book)obj //다운캐스팅
            return title.equals(oBook.title);
        }
    }
}

< toString 오버라이딩 >

  • 출력 시, 굳이 toString을 호출하지 않아도 무방하다.
class A{
	public String toString(){
    	return "원하는 내용"
    }
}

A obj = new A();
System.out.println(obj.toString());
System.out.println(obj); //toString을 호출하지 않아도 무방함

 

'Java' 카테고리의 다른 글

Java - 배열과 리스트  (1) 2025.02.06
Java - 인터페이스  (0) 2025.02.05
Java - 상속  (1) 2025.02.03
Java - 예외 처리  (0) 2025.01.31
구글 Java 스타일 가이드  (1) 2025.01.21

[Dynamic Programming, 동적 계획법]

큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.


탐욕법 Greedy Algorithm은 작은 단계에서 최선의 방법만 고려하지만,
동적계획법은 작은 단계에서 모든 방법을 계산한다는 차이점이 있다.

  • 일부 단계에서는 최선이 아닌 방법들이 전체 문제에서 최적방법이 되는 경우를 고려한다.
  • 완전탐색과는 달리, Memoization을 사용한다.
  • 계산한 부분문제들의 데이터를 별도 메모리에 저장하여,
    추후 같은 계산이 필요한 경우 상수시간만에 해당 값을 호출한다.
  • 문제를 읽고 점화식을 어떻게 구성하는지에 따라 복잡도가 확연히 달라진다.

ex) 거스름돈을 얼마나 지급할 것이냐.

[탐욕법]
1000원짜리부터 최대한 많이 사용해서 동전의 개수를 줄인다.

[동적 계획법 ]
모든 경우의 수를 생각해서 가작 적은 개수의 동전을 줄 수 있는 경우를 찾는다.


< 사용 조건 >

2가지 조건을 만족하는 문제에는 동적 계획법을 적용할 수 있다.

  1. Overlapping Subproblems
    동일한 작은 문제들이 반복하여 나타나는 경우
  2. Optimal Substructure
    부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

'알고리즘' 카테고리의 다른 글

이분탐색 (Binary Search)  (0) 2025.02.04
기초(6) DFS, BFS  (0) 2025.01.24
기초(5) 그래프 이론  (0) 2025.01.24
기초(4) 난수 생성  (0) 2025.01.24
기초(3) 리스트, 스택, 큐  (0) 2025.01.24

https://www.acmicpc.net/problem/11053

> 제한조건

더보기

시간제한 : 1초

메모리 제한 : 256MB

> 문제

더보기
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 
A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

> 입력

더보기

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

> 출력

더보기

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

> 풀이

1. 이분 탐색 법의 lower_bound를 사용한다.

2. 리스트의 끝 값보다 데이터가 큰 경우, 리스트에 삽입
    리스트의 끝 값보다 데이터가 작은 경우, 적절한 삽입 위치 파악 후 기존 값 대체

   가장 긴 수열의 정확한 구성값을 구하는 것이 아니고, 
   길이를 구하는 문제이기 때문에 기존 값을 대체하는 것이 가능하다.

> 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> data(n);
    for (int i = 0; i < n; i++) cin >> data[i];

    vector<int> list;
    list.push_back(data[0]);

    for (int i = 1; i < n; i++) {
        if (data[i] > list.back()) { //데이터가 리스트 끝 값 보다 큰 경우
            list.push_back(data[i]); //리스트에 추가
        }
        else {	//데이터가 리스트 끝 값 보다 작은 경우
        	//데이터의 적절한 삽입 위치를 파악
            auto it = lower_bound(list.begin(), list.end(), data[i]);
            //기존 값을 새로운 데이터로 바꿈
            *it = data[i];
        }
    }
    cout << list.size();
}

 

https://www.acmicpc.net/problem/2805

> 제한조건

더보기

시간제한 : 1초

메모리 제한 : 256MB

> 문제

더보기
상근이는 나무 M미터가 필요하다.
근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다.
정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고,
상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다.
먼저, 상근이는 절단기에 높이 H를 지정해야 한다.
높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.
그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다.
따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.

예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자.
상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고,
상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다.
(총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다.
이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는
높이의 최댓값을 구하는 프로그램을 작성하시오.

> 입력

더보기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.

(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에,
상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

> 출력

더보기

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

> 풀이

1. 주어진 나무의 개수와 길이가 매우 컸기 때문에 long long을 사용했다.

2. 이분탐색 사용했다.
0 ~ 최대 높이에 대해서 탐색한다.
중앙값의 높이보다 큰 나무에 대해서 벌목을 했을 때, 얻을 수 있는 나무의 길이를 구한다.

3. 높이의 최댓값
최대한 목표 나무 길이와의 차이가 크지 않아야 했다.
얻을 수 있는 나무의 길이가 목표하는 나무의 길이보다 큰 경우를 구하더라도
이 이후의 탐색에서 더 차이가 작은 나무를 얻을 수 있기 때문에,
탐색을 멈추지 않는다. 

> 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> trees;

    int t;
    int max_height = 0;
    for (int i = 0; i < N; i++) {
        scanf("%d", &t);
        trees.push_back(t);
        max_height = max(max_height, trees.back());
    }

    long long left = 0;
    long long right = max_height;
    long long mid;
    long long count;
    long long result = 0;

    while (left <= right) {
        mid = (left + right) / 2;
        count = 0;
        for (auto h : trees) {
            if (h > mid) {
                count += h - mid;
            }
        }

        //더 잘라야 함
        //좌측 탐색
        if (count < M) {
            right = mid - 1;
        }
        //덜 자를 수 있음
        //우측 탐색
        else {
            result = mid;
            left = mid + 1;
        }
    }

    printf("%d", result);
    return 0;
}

[ 이분탐색 (Binary Search) ]

정렬된 데이터에서 특정 값을 찾는 알고리즘이다.

  • 탐색 범위를 반씩 줄여나간다.
  • O(log n) 
  • 대규모 데이터에 대해서 효율적이다.

출처 : https://charles098.tistory.com/133

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int target;
    
    vector<int> list;

    int left = 0;
    int right = list.size() - 1;
    int mid;
    int result = -1;

    while (left <= right) {
        mid = (left + right) / 2;
        int num = list[mid];
		if(target == num) { //원하는 원소를 찾은 경우
			result = mid;   
			break;			//반복 종료
		}
			
		if(num > target) {  //탐색값이 타겟보다 큰 경우
			right = mid-1;  //좌측 탐색
		}
		
        else {				//탐색값이 타겟보다 작은 경우
			left = mid+1;	//우측 탐색
		}
    }

    printf("%d", result);
    return 0;
}

< upper_bound, lower_bound >

중복 데이터 값의 범위를 파악할 수 있다.

lower_bound : 특정 값 이상인 첫 위치 

upper_bound : 특정 값을 초과하는 첫 위치

https://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 


< C++ >

C++에서 algorithm 헤더를 통해 이진탐색과 lower_bound, upper_bound를 사용할 수 있다.
그러나 binary_search는 값의 존재 여부만을 확인하기 때문에
위치를 알고자 한다면 lower_bound를 사용해야 한다.

#include <algorithm>
// 이진탐색
bool binary_search(first, last, value);

// 첫 번째로 value 이상인 요소 위치 반환
lower_bound(first, last, value);

// 첫 번째로 value 초과인 요소 위치 반환 
upper_bound(first, last, value);

lower_bound, upper_bound는 반복자를 반환한다.
(*반복자 : 포인터와 유사한 동작)
따라서, 반환값을 auto로 받는 것이 편하다.


< Java >

Java는 데이터를 배열로 다루는가 리스트로 다루는가에 따라 이분탐색 기능을 제공하는 클래스가 다르다.
배열은 Array, 리스트는 Collections에서 지원한다. 

- 반환값
  검색 성공 시, 해당 위치의 인덱스를 반환한다.
  검색 실패 시, 해당 값이 삽입될 수 있는 위치(삽입 지점)를 기반으로 - (삽입 지점) -1 값을 반환한다.

ex) [10, 20, 30, 40, 50] 
30 탐색 시, 반환값 2
25 탬색 시, 삽입지점 -(2) -1 = -3, 반환값 -3

- 문제점
  중복된 값이 있는 경우, 반환되는 위치가 중복되는 값들 중 첫번째 위치라는 점을 보장하지 않는다.
  ex) [ 1, 3, 3, 3, 5, 7 ]에서 3을 찾고자 할 때, 무조건 1이 반환되는 것이 아니라 1,2,3 중에서 반환이 된다.

int index = Arrays.binarySearch(arr, target);
int index = Collections.binarySearch(list, target); 

public static int lowerBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low)/2;
        if (target <= arr[mid]) high = mid;
        else low = mid + 1;
    }
    return low;  // 타겟 이상의 첫 위치
}

public static int upperBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low)/2;
        if (target >= arr[mid]) low = mid + 1;
        else high = mid;
    }
    return low;  // 타겟 초과의 첫 위치
}

lower_bound와 upper_bound는 기능을 따로 제공하지 않기 때문에 직접 구현해야 한다.

'알고리즘' 카테고리의 다른 글

기초 (7) 동적 계획법  (0) 2025.02.04
기초(6) DFS, BFS  (0) 2025.01.24
기초(5) 그래프 이론  (0) 2025.01.24
기초(4) 난수 생성  (0) 2025.01.24
기초(3) 리스트, 스택, 큐  (0) 2025.01.24
  1. Java 전공책 복습을 이어갔다.
    상속 부분을 중심으로 공부했다.

  2. 하노이의 탑 문제를 복습하며 원리를 이해하고자 했다.
    하노이 탑에 비해 색종이 만들기 문제는 너무 쉬웠다.
  3. 나만의 가계부를 웹으로 개발하는 프로젝트를 시작했다.
    원래 엑셀로 정리했는데, 엑셀에는 어느 정도 코딩에 한계가 있다고 느끼던 차에
    웹 개발 강의를 통해 firebase와 bootstrap 사용법을 알게 되었고
    이를 이용하면 좀 더 쉽게 개발할 수 있을 것 같아서 프로젝트를 시작했다.

[오늘의 학습 키워드]

#상속 #하노이탑 #프로젝트 입력 구성


[학습 내용 정리]

  • 상속

https://devhippo.tistory.com/31

 

Java - 상속

[ Superclass와 Subclass ]수퍼클래스 : 먼저 정의하는 일반 클래스를 말한다. (부모)서브클래스 : 나중에 정의하는 특수 클래스를 말한다. (자식) extends를 사용한 상속으로 수퍼클래스의 속성을 서브

devhippo.tistory.com

 

  • 재귀함수 문제 풀이

https://devhippo.tistory.com/32

 

백준 11729번 - 재귀 - 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729> 제한 조건더보기시간제한 : 1초메모리 제한 : 256 MB> 문제더보기세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이

devhippo.tistory.com

https://devhippo.tistory.com/33

 

백준 2630번 - 재귀 - 색종이 만들기

분할 정복 기초 문제> 제한조건더보기시간제한 : 1초메모리 제한 : 128 MB> 문제더보기아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하

devhippo.tistory.com

 

  • 프로젝트 진행 과정 
    가계부를 위해 필요한 데이터를 입력 받는 입력창을 구성하였다.

지출, 수입 탭의 구성
내 계좌 간 이체, 계좌 추가 탭의 구성

< 개선해야 할 부분 >

  1. 입력 받는 부분을 플로팅 라벨로 바꾸고 싶다.
  2. 수입의 내역 부분을 셀렉션으로 변경해야 한다. (용돈, 월급, 이자, 캐시백, 기타)
  3. 일부 Select에서 선택지를 데이터 베이스에 저장되어있는 계좌를 기반으로 설정하는 방법을 구상할 필요가 있다.
  4. 탭이 보여지는 위치를 왼쪽 위로 크기 조정하기

[학습하며 겪었던 문제점]

  • bootstrap의 코드를 그대로 가져왔는데 디자인이 다른 현상

원하던 디자인

 

실제 적용 시 디자인

원하던 디자인의 부트스트랩 코드를 가져왔는데 실제 적용 시, 기본 리스트 형태의 결과가 출력되었다. 

<!-- CSS -->
<link href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0/dist/css/bootstrap.min.css" rel="stylesheet">

<!-- JavaScript -->
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0/dist/js/bootstrap.bundle.min.js"></script>

부트스트랩의 디자인을 활용하기 위해서는 부트스트랩의 CSS와 JavaScript를 추가해주어야 했다.

  • 하노이 탑 문제
    한 번더 복습하며 원리가 이해가 되긴 했지만 어느 정도 감으로 이해한 부분도 남아있는 상태이다.
    다시 풀라고 하면 풀 수 있을 것 같다.

[ 내일 학습 할 것 ]

1. Java 전공책 복습 이어서하기

2. 동적 프로그래밍 문제 풀이하기

3. 프로젝트 입력창 개선할 점 개선하기

분할 정복 기초 문제

> 제한조건

더보기

시간제한 : 1초

메모리 제한 : 128 MB

> 문제

더보기
아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

> 입력

더보기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

> 출력

더보기

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

9
7

> 풀이

1. 자른 영역이 모두 같은 색인지 아닌지 판별하는 함수

2. 자른 영역이 모두 같은 색인 경우를 종료 조건으로 설정

3. 자른 영역이 모두 같은 색이 아닌 경우, 해당 영역을 사분할하면서 탐색을 계속한다.

> 코드

#include <iostream>
int n = 2;
int Data[128][128];

int blue = 0;
int white = 0;

bool check(int startX, int startY, int size){
    int k = Data[startX][startY];
    for(int i = startX; i < startX + size; i++){
        for(int j = startY; j < startY + size; j++){
            if(k != Data[i][j]){
                //다른 값이 있음
                return 0;        
            }
        }
    }
    //모두 같은 값
    return 1;
}

void cut(int startX, int startY, int size){
    if(check(startX, startY, size)){
        if(Data[startX][startY]){
            blue++;
        }
        else{
            white++;
        }
        return;
    }
    int divSize = size/2;
    cut(startX, startY, divSize);
    cut(startX, startY+divSize, divSize);
    cut(startX + divSize, startY, divSize);
    cut(startX + divSize, startY + divSize, divSize);    
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &Data[i][j]);
        }
    }
    cut(0, 0, n);
    printf("%d\n%d\n", white, blue);
    return 0;
}

https://www.acmicpc.net/problem/11729

> 제한 조건

더보기

시간제한 : 1초
메모리 제한 : 256 MB

> 문제

더보기
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다.
각 원판은 반경이 큰 순서대로 쌓여있다.
이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라.
단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.

> 입력

더보기

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다

> 출력

더보기

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다.
두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데,
이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

> 풀이

  1. 상위 n-1개 원반을 보조 기둥으로 이동
    시작 기둥에서 보조 기둥으로 n-1개 원반을 옮긴다.
    이때 목적지 기둥을 보조로 사용한다.
    1이 시작점이 된다.
    2, 3이 보조기둥이 된다.

  2. 가장 큰 원반을 목적지로 이동
    남아있는 가장 큰 원반을 시작 기둥에서 목적지 기둥으로 옮긴다.

  3. 보조 기둥의 n-1개 원반을 목적지로 이동
    보조 기둥에 있는 원반들을 시작 기둥을 보조로 사용하여 목적지로 이동시킨다.
    2가 시작점이 된다.
    1, 3이 보조기둥이 된다.

> 코드

#include <iostream>
#include <vector>

using namespace std;

int n = 0;
vector<pair<int, int>> moves;

void hanoi(int p, int from, int to, int middle) {
    if (p == 1) {
        moves.push_back(make_pair(from, to));
        return;
    }

    hanoi(p-1, from, middle, to); 
    moves.push_back(make_pair(from, to)); 
    hanoi(p - 1, middle, to, from);
}

int main() {
    scanf("%d", &n);
    hanoi(n, 1, 3, 2);
    printf("%d\n", moves.size());
    for (auto m : moves) {
        printf("%d %d\n", m.first, m.second);
    }
    return 0;
}

[ Superclass와 Subclass ]

수퍼클래스 : 먼저 정의하는 일반 클래스를 말한다. (부모)
서브클래스 : 나중에 정의하는 특수 클래스를 말한다. (자식)

https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS8459970852

 

< extends 상속 >

extends를 사용한 상속으로 수퍼클래스의 속성을 서브클래스에서 사용하는 것이 가능해진다.
"서브클래스 extends 수퍼클래스"

class A {
    private int a;
    private int x;
    private int y;
    public A() {
    	this.a = 0;
    }
    
    public A(int x, int y){
    	this.x = x;
        this.y = y;
    }
}

class B extends A { //A를 상속받은 B
    private int b;
    public B() {
    	this.b = 1;
    }
    
    public B(int b, int x, int y){
    	super(x, y); //두 개의 매개변수를 사용하는 생성자 A(int x, int y)를 호출한다.
        this.b = b;
    }
}

B obj = new B();
B obj2 = new B(1, 2, 3);

- 인자가 없는 생성자의 경우

  • 서브클래스에서 수퍼클래스의 생성자를 호출하지 않아도 묵시적으로 수퍼클래스의 생성자가 먼저 호출된다.
  • 예시의 경우, B 생성자만 호출되었으나 A 생성자가 묵시적으로 호출되므로 A 생성 후, B가 생성된다.

- 인자가 있는 생성자의 경우

  • 명시적으로 수퍼클래스의 생성자를 호출해야 한다.
    super(인자)
    반드시 super 키워드를 써야 한다.
  • 수퍼클래스 생성자의 호출은 반드시 생성자의 첫 번째 문장이어야 한다.

 

< 접근 제어자 private & protected >

- private

class A {
    private int a;
    public A() {
    	this.a = 0;
    }
    public void setA(int a){
        this.a = a;
    }
    public int getA(){
    	return this.a;
    }
}

class B extends A { //A를 상속받은 B
    private int b;
    public B() {
    	this.b = 1;
    }
   public void save(int newA, int newB){
        a = newA; //에러
        super.setA(newA); //올바른 호출방법, super는 상황에 따라 생략 가능
        this.b = newB;
    }
    public void check(){
        System.out.println("A : " + getA());
        System.out.println("B : " + this.b);
    }
}

B obj = new B();
obj.save(17, 526);
obj.check()

서브클래스와 수퍼클래스는 엄연히 별개의 클래스이기 때문에
수퍼클래스의 변수가 private로 선언되어있다면 서브클래스가 마음대로 접근할 수 없다.
따라서 서브클래스에서 변수의 값을 변경 또는 불러오고자 한다면
setA(), getA()와 같은 별도의 함수를 만들어주어야 한다.

- protected

protected로 선언된 수퍼클래스 변수는 상속받은 서브클래스에서 제한 없이 사용할 수 있다.
상속받지 않은 클래스에 대해서는 사용이 불가능하다.

 

< 업캐스팅, 다운캐스팅 >

명찰 바꿔달기
수퍼와 서브클래스 둘 다 가능한데, 때에 따라 명찰만 바꿔 다는 것과 유사하다.

업캐스팅
: 수퍼클래스 타입의 참조 변수에 서브클래스의 객체를 대입하는 것

  • 객체가 변경되는 것은 아니다. 수퍼클래스로 취급되며 서브클래스 멤버가 숨겨진다.
  • 따라서, 서브클래스의 멤버는 사용할 수 없다.
  • 서브클래스 멤버 사용을 위해서는 다운캐스팅이 필요하다.

다운캐스팅
: 서브클래스 타입으로 되돌려서 숨겨진 멤버를 사용한다.

  • 명시적으로 클래스 타입을 지정한다.
  • 실제 객체에는 아무런 변경이 일어나지 않는다.
  • 객체를 가리키는 참조 변수의 타입이 달라질 뿐이다.
class A {
    public void foo(){}
}

class B extends A {
    public void boo(){}
}

A objA = new B(); //업스케일링 
B objB = new B();

objA.foo();
objA.boo(); //에러

B objA2 = (B)objA //objA를 다운캐스팅
objA2.boo();

 

상속 받은 클래스가 여러 개인 경우 instanceof 연산자를 사용할 수 있다.

class A { }
class B extends A{}
class C extends A{}

A objA = new C();

if(objA instanceof C){ //어떤 서브클래스인지 확인
	C objAC = (C)objA; //해당 서브클래스로 다운캐스팅
}

'Java' 카테고리의 다른 글

Java - 배열과 리스트  (1) 2025.02.06
Java - 인터페이스  (0) 2025.02.05
Java - 오버로딩, 오버라이딩  (1) 2025.02.04
Java - 예외 처리  (0) 2025.01.31
구글 Java 스타일 가이드  (1) 2025.01.21

Java 전공책을 전체적으로 복습했다.
클래스 등 이미 잘 알고 있는 내용은 가볍게 훑고 넘어갔고
자세하게 기억이 나지 않는 부분부터 블로그에 정리하고자 했다.
Java 그래픽 부분도 공부했는데 책에 전체적으로 내용이 퍼져있어서 아직 정리를 완료하지 못했다.

[오늘의 학습 키워드]

#예외처리 #하노이탑

[학습 내용 정리]

https://devhippo.tistory.com/29

 

Java - 예외 처리

자바에서 예외 처리는 if와 else로도 처리가 가능하지만, 자바가 보유한 예외 처리 기능을 사용하는 편이 보다 명확하고 바람직한 프로그램 구조를 이룰 수 있다.[ try-catch ]Java의 기본적인 예외 처

devhippo.tistory.com

 

[학습하며 겪었던 문제점]

하노이탑 알고리즘을 구상하는데서 어려움을 겪었다.

내가 DFS, BFS와 같은 탐색 알고리즘 형태로 문제 풀이를 하려고 했기 때문이다.

나는 스택을 3개를 써서 원반을 각각 이동시키려고 했다.
이에 맞춰서 코드를 짜다보니 코드가 굉장히 복잡해졌고 이것이 잘못된 방법인것 같다고 느꼈다.
다른 방법이 도저히 떠오르지 않아 다른 사람의 코드들을 참고했다.

원리는 다음과 같다.

 

  • N-1개의 원반을 시작 기둥에서 보조 기둥으로 이동
  • 가장 큰 원반을 목표 기둥으로 이동
  • N-1개의 원반을 보조 기둥에서 목표 기둥으로 이동

이를 N부터 입력해서 1번까지 재귀함수를 호출한 후, 호출이 쌓인 재귀함수를 하나씩 풀어가는 느낌이었다.

 

코드를 어느 정도 이해한 후 문제를 다시 풀었더니
원리를 이해해서 풀었다기 보다는 암기해서 풀었다는 느낌을 받았다.

그래서 내일 다시 문제를 풀어보려고 한다.
재귀적 사고력이 아직 부족하다고 느꼈기 때문에 다른 재귀함수 문제들도 풀어보려고 한다.

[ 내일 학습 할 것 ]

하노이탑 문제 다시 풀어보기

+ Recent posts