기역니은

boolean solution(String inputString) {
    for (int i = 0; i < inputString.length() / 2; i++) {
        if (inputString.charAt(i) != inputString.charAt(inputString.length() - i - 1)) {
            return false;
        } 
    }
    return true;
}

먼저 두 노드를 회전시킨다는 건 두 노드의 높이를 서로 바꾸는 것을 의미한다. 그냥 잡아 피는 게 아니라 노드의 부모자식관계를 역전시켜야 한다.

일직선 불균형, 꺽쇠 불균형은 단지 내가 분류하려고 붙인 것일 뿐 정식 명칭은 아니다. 본래 왼쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 LL 유형 오른쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 RL유형과 같이 말한다.

오른쪽 회전, 왼쪽 회전이 헷갈린다면 그냥 시계방향(오른쪽 회전) 반시계방향(왼쪽 회전)으로 이해하면 좀 낫다.

1. 일직선 불균형(RR,  LL유형)

불균형이 생긴 서브트리의 반대 방향으로 회전한다.

왼쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 오른쪽(시계방향)으로 회전(LL유형)

오른쪽 자식의 오른쪽 서브트리에서 불균형이 발생하면 왼쪽(반시계방향)으로 회전(RR유형)

왼쪽 자식의 서브트리에서 불균형이 발생했으므로 오른쪽(시계방향) 회전한다.

2. 꺽쇠 불균형(RL, LR유형)

a. 자식 노드를 불균형이 발생한 방향으로 회전시켜 일직선 노드를 만든다.

왼쪽에서 불균형이 발생했으므로 자식노드를 왼쪽(반시계방향) 회전한다.

b. 일직선 불균형이 됐으므로 부모노드를 반대 방향으로 회전시킨다.

부모 노드를 오른쪽(시계방향) 회전한다.

1. 접근

ArrayList :  요소의 위치를 알면 인덱스로 바로 접근해서 시간복잡도가 O(1)이다.

LinkedList : 첫 노드부터 순차적으로 접근해야 되므로 시간 복잡도가 O(n)이다.

2. 삽입 및 삭제

ArrayList : 리스트 끝에 삽입하거나 삭제할 때의 시간복잡도는 O(1)이지만 그 외에는 다른 요소들을 복사해 이동시켜줘야 하므로 O(n)이다. (이와 같은 특징 때문에 Stack을 구현하기에 적합하다)

LinkedList : 첫 노드를 삽입하거나 제거할 때의 시간복잡도는 O(1)이지만 맨 끝에 삽입하거나 제거할 때는 맨 마지막 노드까지 접근해야 하므로 O(n)의 시간복잡도를 갖는다. (이와 같은 특징 때문에 Queue를 구현하기에 적합하다)

리스트 중간에 요소를 제거하거나 삽입할 때는 대체로 LinkedList의 처리속도가 더 빠르다.

4. 메모리 사용

ArrayList : 배열의 크기는 고정되어있으므로 요소가 배열의 크기를 벗어나면 더 큰 배열을 새로 생성해 기존 배열의 내용을 복사해 줘야 된다. 그렇다고 배열의 크기를 너무 크게 잡으면 메모리가 낭비된다.

LinkedList : 크기가 가변적이므로 요소들을 계속 추가해도 상관없다. 다만 배열리스트와는 다르게 next 포인터를 가지고 있어 배열리스트보다 더 많은 용량을 차지한다.

1. equals()

Object 클래스의 equals()는 매개변수로 받은 참조변수의 값(객체의 주소)을 비교하여 같은 객체인지 아닌지를 boolean 값으로 반환하는 메서드이다. 

비교하고 싶은 인스턴스 변수(iv)끼리 비교하도록 equals() 메서드를 오버라이딩해서 사용하면 된다.

class Value {
    int value;
    Value () {};
    Value (int value) {
        this.value = value;
    }

    public boolean equals(Object obj) { // 오버라이딩 안하면 객체의 주소를 비교
        // 참조변수의 형변환 전에는 반드시 instanceof로 확인해야한다.
        if(!(obj instanceof Value)) return false;
        Value v = (Value) obj;
        return this.value == v.value;
    }
}

instanceof 연산자는 형변환이 가능한지 확인하는 연산자이다. 참조변수의 형변환은 상속관계에서만 가능하다. 상속관계가 아닌 다른 참조변수가 매개변수로 들어온다면 비교할 필요 없이 false를 반환하면 된다.

메서드 오버라이딩은 선언부가 같아야되므로 아래와 같이 정의하면 Object 클래스의 equals()를 오버라이딩한 게 아니라 그냥 별개의 메서드를 정의한 게 되므로 주의하자.

  public boolean equals(Value v) { 
        return this.value == v.value;
    }

2. hashCode()

Object 클래스의 hashCode() 메서드는 객체의 주소를 int로 변환한 해시코드를 만들어 반환하는 함수이다.

equals() 메서드를 오버라이딩하면 hashCode() 메서드 또한 오버라이딩해야 한다.

class Card {
    String kind;
    int number;
    static int width = 100;
    static int height = 250;

    Card () {
        this("SPADE", 1);
    }

    public Card(String kind, int number) {
        this.kind = kind;
        this.number = number;
    }

    @Override
    public boolean equals(Object obj) {
        if(!(obj instanceof Card)) return false;
        Card c = (Card) obj;
        return this.kind.equals(c.kind) && this.number == c.number;
    }

    @Override
    public int hashCode() {
        return Objects.hash(kind, number);
    }
}

* String 클래스에는 이미 equals()가 문자열의 내용끼리 비교하도록 오버라이딩되어있기 때문에 String 타입의 변수 kind는 equals()로 비교한다.

* Objects.hash() : 여러 객체의 해시 코드를 결합하여 새로운 해시 코드를 생성하는 메서드이다. 가변 인자를 받으므로 여러 개의 필드를 넣어도 된다. Object가 아닌 Objects임에 유의하자

- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다. 

- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.

- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

※ 시간 복잡도를 다룰 때 등호(=)는 같다는 뜻이 아니라 속한다(∈)에 가깝다. 

예를 들어 아래 식이 참인지 판별하려면 2n이 n과 같거나 더 빠른 범위에 포함되는지를 확인하면 된다. 시간복잡도를 다룰 때 상수는 무시하므로 2n은 n과 같다. 고로 아래 식은 참이다.

n^3/4이 nlogn보다 같거나 빠르다는 뜻이다. 입력값이 작은 경우는 고려하지 않고 계산하기 쉬운 큰 값을 넣어 맞는지 확인해 보자

n = 1000, 로그의 밑을 10으로 놓고 계산하면

좌항은 10000, 우항은 3000이므로 좌항이 더 크다. 즉 n^3/4가 nlogn보다 더 시간복잡도가 큰 느린 알고리즘이므로 위 식은 거짓이다.

상수는 무시하고, 최고차항만을 고려하므로 좌항과 우항은 같다. 곧 위 식은 참이다.

1. 입력값(n)은 항상 0보다 크다.

2. 입력값이 증가하면 처리시간도 늘어난다.

3. 모든 상수를 무시한다. 

3n, 10n, 4n+13 모두 시간 복잡도가 n인 알고리즘이다.

4. 다항식에서 가장 높은 차수의 항만을 고려한다.

- 4n^7+22n^5+10n 의 시간 복잡도는 n^7이다.

5. 로그의 밑은 무시한다.

- 로그의 밑을 계산하기 가장 편한 값으로 두고 계산하면 된다.

- 시간 복잡도가 로그인 알고리즘은 보통 2로 나누거나 곱하는 경우에 자주 쓰인다.

matrix_a = [[3, 6], 
            [4, 9]]
matrix_b = [[7, 2], 
            [8, 3]]

1. 행렬 a를 행으로 자른다.

for row in matrix_a :
    print('row of a :',row)

row of a : [3, 6]
row of a : [4, 9]

2. 행렬 b를 열로 자른다.

for col in  zip(*matrix_b) :
    print('colum of b :',col)

※ 리스트로 묶여있는 행렬을 *로 풀어서 zip을 해야 열로 묶인다.

colum of b :  (7, 8)
colum of b :  (2, 3)

3. 행렬 a의 행과 행렬 b의 열에서 곱할 요소끼리 zip으로 묶어준다.

zip_result = [zip(row, col) 
              for col in zip(*matrix_b)
              for row in matrix_a]
for a,b in zip_result:
    print(a,b)

(3, 7) (6, 8)
(4, 7) (9, 8)
(3, 2) (6, 3)
(4, 2) (9, 3)

4. 묶여있는 요소끼리 곱하고 합을 구한다. 

result = [ [sum(a*b for a,b in zip(row, col)) 
          for col in zip(*matrix_b) ]
          for row in matrix_a]
print(result)

※  [sum(a*b for a,b in zip(row, col)) for col in zip(*matrix_b) ]  : 각 행을 리스트로 묶으려고 대괄호를 씌웠다.

[[69, 24], [100, 35]]

개선 전 코드

BidProductResponseDto가 생성될 때 경매 상품의 제시자가 아무도 없어 topBid가 null인 경우 NPE가 발생했다.

    public BidProductResponseDto(BidProduct bidProduct) {
        id = bidProduct.getId();
        name = bidProduct.getName();
        description = bidProduct.getDescription();
        startPrice = bidProduct.getStartPrice();
        expirationPeriod = bidProduct.getExpirationPeriod();
        feetSize = bidProduct.getFeetsize();
        footSize = bidProduct.getFootsize();
        footPicture = bidProduct.getFootpicture();
        brand = new BrandResponseDto(bidProduct.getBrand());

        topBid = new BidResponseDto(bidProduct.getTopBid());

        status = bidProduct.getStatus();

        createdAt = bidProduct.getCreatedAt();
        updatedAt = bidProduct.getUpdatedAt();
        for (int i = 0; i < bidProduct.getBids().size(); i++) {
            bidResponseDtoList.add(new BidResponseDto(bidProduct.getBids().get(i)));
        }
    }

해결방안

입찰이 하나도 없을 때 빈 객체를 생성한 뒤, topBid의 제시자는 경매상품 출품자로, topBid의 가격은 경매 시작가로 설정한다.

    public BidProductResponseDto(BidProduct bidProduct) {
        this.id = bidProduct.getId();
        this.name = bidProduct.getName();
        this.author = bidProduct.getUser().getName();
        this.description = bidProduct.getDescription();
        this.startPrice = bidProduct.getStartPrice();
        this.expirationPeriod = bidProduct.getExpirationPeriod();
        this.feetSize = bidProduct.getFeetsize();
        this.footSize = bidProduct.getFootsize();
        this.footPicture = bidProduct.getFootpicture();
        this.brand = new BrandResponseDto(bidProduct.getBrand());

        // topBid 설정 (경매 제시가가 아직 없을 경우 처리)
        if (bidProduct.getTopBid() != null) {
            this.topBid = bidProduct.getTopBid();
        } else {
            // topBid가 없을 때 topBid 제시자는 경매상품 등록자로, 가격은 startPrice로 설정
            this.topBid = new Bid();
            this.topBid.setUser(bidProduct.getUser());
            this.topBid.setBidPrice(bidProduct.getStartPrice());
        }


        this.status = bidProduct.getStatus();

        this.createdAt = bidProduct.getCreatedAt();
        this.updatedAt = bidProduct.getUpdatedAt();

        this.bidResponseDtoList = bidProduct.getBids().stream()
                .map(BidResponseDto::new)
                .sorted(Comparator.comparing(BidResponseDto::getBidPrice))
                .toList();

    }

고찰할 점 

@Table(name = "bidproduct")
public class BidProduct extends Timestamped{

	...
 
    /**
     * 연관관계 - Foreign Key 값을 따로 컬럼으로 정의하지 않고 연관 관계로 정의합니다.
     */
     
    @OneToMany(mappedBy = "bidProduct", cascade = CascadeType.REMOVE)
    private List<Bid> bids = new ArrayList<>();

    @OneToOne
    @JoinColumn(name = "topBid")
    private Bid topBid;
    
    ...
   
}

BidProduct와 topBid는 일대일 단방향 연관관계인데 topBid가 null인 경우를 (topBid의 price가 null인 경우, topBid의 user가 null인 경우 등등..) 메서드마다 매번 핸들링해줘야 했다. 아예 topBid의 초기값을 설정하는 게 더 나은 방법이었을까?