def solution(n, lost, reserve):
    answer = 0
    lost.sort()
    reserve.sort()

    # 1. 여벌 가져온 학생 중 도난당한 학생 체크
    reserve_list = []
    for i in reserve: # for문 안에 remove 함수 있으면 시간복잡도 N^2....
        if i in lost:
            lost.remove(i)
            continue
        else:
            reserve_list.append(i)

    # 2. 체육복 유무 알 수 있는 having 
    having = [True for _ in range(n+1)]

    for i in lost:
        having[i] = False

    for i in reserve_list:
        if i == 1:
            if having[i+1] == False:
                having[i+1] = True
        elif i == n:
            if having[i-1] == False:
                having[i-1] = True
        else:
            if having[i-1] == False:
                having[i-1] = True
            elif having[i+1] == False:
                having[i+1] = True

    having[0] = False
    answer = having.count(True)

    return answer

통과는 했지만 코드가 매우 길고, for문 안에 remove 함수가 있어 시간복잡도가 O(N^2)이 나온다.

💡 강사님 풀이

우선 이 문제는 그리디 알고리즘을 이용해서 푸는 문제이다. 그리디 : 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용

def solution(n, lost, reserve):
    u = [1] * (n + 2) # 체육복 정보 (편의성을 위해 앞, 뒤 체육복을 가진 학생 추가)
    for i in reserve:
        u[i] += 1 # 여벌 가져온 학생 체육복 하나씩 더 추가
    for i in lost:
        u[i] -= 1
    for i in range(1, n+1):
        if u[i-1] == 0 and u[i] == 2: # 앞의 사람 빌려야 하는 입장이고 내가 빌려줄 수 있으면
            u[i-1:i+1] = [1, 1] # 체육복을 빌려준다.
        elif u[i] == 2 and u[i+1] == 0: # 아니면 뒷사람 체크
            u[i:i+2] = [1, 1] # 뒷사람에게 체육복을 빌려준다.
    return len([x for x in u[1:-1] if x > 0])

초기 값을 모두 1로 둔 후에, 여벌체육복이 있으면 +1, 잃어버렸으면 -1을 해준다. 그리고 앞, 뒤 순서로 체크하면서 현재 위치의 학생이 여벌이 있고, 앞, 뒤의 학생이 체육복이 없는 경우 체육복을 빌려주는 방식으로 for문을 돌린다. (각 상황에서의 선택이 마지막 해답의 최적성을 해치지 않음) 이렇게 하면 시간복잡도는 O(N)이 된다.

def solution(bell):
    answer = 0
    accumulate_bell = [0]
    for i in range(len(bell)):
        if bell[i] == 1:
            accumulate_bell.append(accumulate_bell[i+1-1]+1)
        else:
            accumulate_bell.append(accumulate_bell[i+1-1]-1)
    s, e = 0, 2
    while s < len(accumulate_bell) and e < len(accumulate_bell):
        if accumulate_bell[s] == accumulate_bell[e]:
            answer = max(answer, e-s)
            e += 1
        else:
            e += 1
        if e >= len(accumulate_bell) and s < e-2:
                s += 1
                e = (s + 2)
    return answer

사실 처음엔 아이디어도 떠올리기 어려웠다. 강의에서 제시한 아이디어 (초록방울일 경우 1, 빨간방울일 경우 -1을 해서 누적값이 같아질 떄의 최대 길이 구하기) 를 참고하고 짜봤지만, bell의 최대 길이가 1,000,000이라 테스트케이스 말곤 모두 시간초과가 났다. while문 안에서 e, s의 값을 변경해서 시간초과가 난 것 같다.

💡 강사님 풀이

from itertools import accumulate

def solution(bell):
    coors_start = {}
    coors_end = {}
    for i, x in enumerate(accumulate([0] + [-1 if b == 1 else 1 for b in bell])):
        if x not in coors_start:
            coors_start[x] = i
        coors_end[x] = i
    return max(coors_end[x] - coors_start[x] for x in coors_end)

• 먼저 itertools의 accumulate 사용법을 알아야 할 것 같다.

  from itertools import accumulate
  

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] b = list(accumulate(a)) print(a) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] print(b) # [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

```

• accumulate는 누적합을 뽑아준다.

같은 수의 길이를 구해주는 부분에서 시간초과를 해결하지 못했는데 강사님 풀이에선 이를 딕셔너리를 활용해서 풀었다. start와 end 딕셔너리를 각각 만들어주고, start 딕셔너리는 초기 key값 한 번만, end 딕셔너리는 같은 key값이 나오면 업데이트 해준다. key는 실제 누적 값이고, value는 인덱스 이다. (최대 길이를 구하는 것이기 때문에 start는 가장 앞의 수, end는 가장 뒤의 수를 찾아야 하기 때문)

• 처음엔 for문 안에서 if x not in coors_start: 부분이 for문 안에 있어 O(N)보다 큰 시간복잡도를 가질 것이라 생각했지만, 아니었다. 딕셔너리의 key값을 찾는 연산(in)은 평균적으로 상수 시간에 수행된다.

✔️ 배운점

1️⃣ itertools의 accumulate로 누적합을 구할 수 있다.

2️⃣ 딕셔너리 내부에서 키의 존재 여부를 확인하는 연산(in 연산자)은 해시 테이블을 이용하여 평균적으로 상수 시간에 수행된다. (앞으로 리스트에서 같은 숫자의 인덱스를 찾을 땐 해시 테이블, 즉 딕셔너리 자료구조를 사용해보자!⭐️)

def solution(participant, completion):
    answer = ''

    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            break
    if answer == '':
        answer = participant[-1]

    return answer

통과는 했지만, 문제의 의도인 해쉬를 사용하지 않았다. sort() 함수를 사용했기 때문에 시간복잡도는 O(NlogN)

💡 강의 참고 후 코드

def solution(participant, completion):
    answer = ''

    participant_dict = {}
    completion_dict = {}
    for x in participant:
        participant_dict[x] = participant_dict.get(x, 0) + 1
    for x in completion:
        completion_dict[x] = completion_dict.get(x, 0) + 1

    for key, value in completion_dict.items():
        participant_dict[key] -= value

    answer = [key for key, value in participant_dict.items() if value > 0]

    return ''.join(answer)

시간 복잡도 O(N)이 된다.

✔️ 새로 알게된 함수

1️⃣ get(x, 0) -> x라는 key가 없을 때 0 반환, 있으면 해당 value 반환 2️⃣ answer = [key for key, value in participant_dict.items() if value > 0] 형태로 작성 가능

# 자신의 상의 크기와 같거나 큰 티셔츠를 받는다.

# people 하나씩 탐색하면서 같거나 큰 티셔츠 찾음
# 이중 for문 N^2 -> 5,000*5,000 = 25,000,000 
from collections import deque

def solution(people, tshirts):
    answer = 0
    # people과 tshirts 모두 오름차순 정렬
    people_dq = deque(sorted(people))
    tshirts_dq = deque(sorted(tshirts))

    while (people_dq):
        person = people_dq.popleft()
        while (tshirts_dq):
            tshirt = tshirts_dq.popleft()
            if person <= tshirt: # 같거나 큰 티셔츠 찾을 때까지 반복
                answer += 1
                break

    return answer

💡 문제 설명 및 강사님 풀이

def solution(people, tshirts):
    people.sort()
    tshirts.sort()
    p, t, ans = 0, 0, 0
    while p < len(people) and t < len(tshirts):
        if tshirts[t] >= people[p]:
            ans += 1
            p += 1
        t += 1
    return ans

후기

나는 deque 자료형을 이용해서 풀었는데, 이렇게 투포인터를 사용하면 코드가 훨씬 간결해진다. 두 리스트를 탐색하며 비교할 땐 투 포인터 알고리즘을 사용해보자.

# 업무 처리시간 10분

# (1) 현재 시각보다 앞선 시각의 고객 중 업무 시작하는데, 예약고객 우선 시작
# (2) 10분 더했을 때 (1)번 반복

# 시간 : 기준으로 자르기, 분 기준으로 변환, 시간 기준으로 sort
# booked 먼저 탐색, unbooked 그 다음에 탐색
from collections import deque
def solution(booked, unbooked):
    answer = []
    for idx, value in enumerate(booked):
        time, name = value
        h, m = time.split(":")
        mins = 60*int(h) + int(m)
        booked[idx] = [mins, name]
    for idx, value in enumerate(unbooked):
        time, name = value
        h, m = time.split(":")
        mins = 60*int(h) + int(m)
        unbooked[idx] = [mins, name]

    booked_dq = deque(sorted(booked, key = lambda x:x[0]))
    unbooked_dq = deque(sorted(unbooked, key = lambda x:x[0]))

    now = 1440
    while (True):
        if len(booked_dq) > 0:
            booked = booked_dq.popleft()
        else:
            booked = False
        while (unbooked_dq):
            unbooked = unbooked_dq.popleft()
            if (now == 1440 and unbooked[0] < booked[0]) or (now != 1440 and unbooked[0] <= now and unbooked[0] >= now) or not booked:
                # unbooked 먼저
                answer.append(unbooked[1])
                if now == 1440:
                    now = (unbooked[0]+10)
                else:
                    now += 10
                booked_dq.appendleft(booked)
            else:
                # booked 먼저
                answer.append(booked[1])
                if now == 1440:
                    now = (booked[0]+10)
                else:
                    now += 10
                unbooked_dq.appendleft(unbooked)
            break
        if len(booked_dq) == 0 and len(unbooked_dq) == 0:
            break


    return answer

💡 강사님 풀이

def parse_time(t):
    h, m = map(int, t.split(':'))
    return 60*h + m

def solution(booked, unbooked):

    booked = [(parse_time(t), name) for t, name in booked] + [(1000000, None)]
    unbooked = [(parse_time(t), name) for t, name in unbooked] + [(1000000, None)]
    booked.sort()
    unbooked.sort()
    b, u, t, answer = 0, 0, 0, []

    while b < len(booked) and u < len(unbooked):

        t1, t2 = booked[b][0], unbooked[u][0]
        if t1 <= t:
            answer.append(booked[b][1])
            b += 1
            t += 10
        elif t2 <= t:
            answer.append(unbooked[u][1])
            u += 1
            t += 10
        else:
            t = min(t1, t2)

    answer.pop()
    return answer

후기

풀이가 굉장히 단순하다. 시간을 적절한 숫자로 바꿔주는 부분은 동일하다. 다만 초기 규칙을 단순하게 생각하지 못했다.

✔️ 실수한 점

1️⃣ 반복문에 사용할 자료형

• 나는 deque를 사용했는데 deque를 사용하게 되면 booked unbooked 두가지 중 answer에 추가하지 않은 것을 다시 appendleft 해줘야 하는 문제가 생긴다.
• 여기선 자료형의 길이로 반복문을 돌리는 방식으로 사용했다.

2️⃣ 초기 시간 설정

• 나는 초기 시간을 1440으로 설정했는데, 그럴 필요가 없었다.

✔️ 배운 점

• 특정 자료형을 사용할 때는 그 자료형을 쓰는게 좋을지 다른 자료형을 쓰는게 좋을지 먼저 고민해야 한다.
• 코드를 짜기 전에 풀이 로직을 정리하는데 더 시간을 쓰자.
• 코드가 길어지고 복잡해질 것 같으면 함수로 뺴자
• 강사님 코드의 while문 구조 기억하고 나중에 써먹자 !
• 예외처리 해주기 전에 더미데이터를 추가해서 해결할 수 있는지 확인
• 문법 booked = [[parse_time(time), value] for time, value in booked] + [[10000, 'dummy']] 리스트끼리 더할 떄는 각각 동등한 자료형끼리 더해야 한다 (ex. 이중 리스트 + 이중 리스트)

💡 강의 참고 후 코드

def parse_time(time):
    h, m = time.split(":")
    return (60*int(h) + int(m))

def solution(booked, unbooked):
    b, u, t, answer = 0, 0, 0, []
    booked = [[parse_time(time), value] for time, value in booked] + [[10000, 'dummy']]
    unbooked = [[parse_time(time), value] for time, value in unbooked] + [[10000, 'dummy']]
    booked.sort()
    unbooked.sort()

    while b<len(booked) and u<len(unbooked):
        bt, ut = booked[b][0], unbooked[u][0]
        if bt <= t: # 대기중인 손님 중 예약한 손님 우선으로 처리
            answer.append(booked[b][1])
            b += 1
            t += 10
        elif ut <= t:
            answer.append(unbooked[u][1])
            u += 1
            t += 10
        else: # 현재 시점에서 대기중인 손님이 없는 경우
            t = min(bt, ut) # 현재 시간 이후로 올 손님 중 가장 빨리 올 손님 시간으로 설정

    answer.pop()
    return answer

더미데이터를 추가해주는 부분은 나중에도 스스로 떠올릴 수 있을지 모르겠다. 잘 쓴 코드들 많이 참고하면서 공부하기 ✔️

• 자바 진영의 ORM 기술 표준으로, 인터페이스의 모음
• JPA 인터페이스를 구현한 대표적인 오픈소스가 Hibernate

💡 ORM (Object-relational mapping)

객체 관계 매핑 ->객체는 객체대로 설계하고, 관계형 데이터베이스는 관계형 데이터베이스대로 설계한다 ORM프레임워크가 중간에서 매핑해준다.

📍 JPA의 동작 과정

• JPA는 애플리케이션과 JDBC 사이에서 동작한다.
  • 개발자가 JPA를 사용하면, JPA 내부에서 JDBC API를 사용해 SQL을 호출하여 DB와 통신한다.
  • 개발자가 직업 JDBC API를 쓰는 것이 아니다.

저장 과정

EX) MemerDAO에서 객체를 저장하고 싶을 때

• 개발자는 JPA에 Member 객체를 넘긴다.
• JPA는
  • 1) Member엔티티를 분석
  • 2) INSERT SQL 생성
  • 3) JDBC API를 사용해 SQL을 DB에 날린다.

조회 과정

• EX) MemerDAO 객체를 조회하고 싶을 때

  • 개발자는 member의 pk값을 JPA에 넘긴다.
  • JPA는
  • 1) 엔티티의 매핑 정보를 바탕으로 적절한 SELECT SQL을 생성
  • 2) JDBC API를 사용해 SQL을 DB에 날린다.
  • 3) DB로부터 결과를 받아온다.
  • 4) 결과(ResultSet)를 객체에 모두 매핑한다.

• 쿼리를 JPA가 만들어 주기 때문에 Object와 RDB간의 패러다임 불일치를 해결할 수 있다.

*패러다임 불일치란 ? *💡
db는 철저히 데이터 중심으로 설계되어 있으며 객체와 db는 목적이 다르다. 패러다임의 불일치는 이렇게 객체(OOP)와 관계형 DB의 데이터 표현방식과 다루는 방법이 달라 일어나는 현상이다. 객체와 db 양쪽의 불일치를 해결해줘야 한다. 그렇지 않다면, db에 의존적이게 코딩을 하게 될 수 밖에 없다.

🤔 JPA를 왜 사용해야 할까?

1. SQL 중심적인 개발에서 객체 중심으로 개발

• SQL중심적인 개발의 문제점

2. 생산성

• 간단한 CRUD
  • 저장 : jpa.persist(member)
  • 조회 : Member member = jpa.find(memberId)
  • 수정 : member.setName("변경할 이름")
  • 삭제 : jpa.ermove(member)
    
• 수정시엔 객체를 변경하면 자동으로 DB에 UPDATE Query가 나간다.

3. 유지보수

• 기존 : 필드 변경 시 모든 SQL 수정 필요
• JPA : 필드만 추가하면 JPA가 SQL을 처리해줌

참고 자료

https://gmlwjd9405.github.io/2019/08/04/what-is-jpa.html

Error (오류)

• 프로그램에서 복구할 수 없는 시스템 수준의 심각한 문제를 의미 (주로 자바 가상머신에서 발생시키는 것)
• 개발자가 미리 예측하여 방지할 수 없음 (로직 수정으로 처리할 수 없음)

ex) OutOfMemoryError, ThreadDeath, StackOverflowError 등

Exception (예외)

• 개발자가 구현한 로직에서 실수가 발생하거나, 사용자 영향에 의해 발생
• 개발자가 미리 예측하여 방지할 수 있음 (상황에 맞는 예외처리 필요)

Java 예외의 종류

상속 관계가 이렇게 되어 있는 이유는 Exception이나 Error의 성격은 다르지만, 모두 동일한 이름의 메소드를 사용하여 처리할 수 있도록 하기 위함

1. checked exception (일반 예외)

컴파일러가 해당 예외를 확인하고 처리 여부를 강제하는 예외

• 처리를 해주지 않으면 런타임 전에 에러가 발생한다. (실행 불가) ⬇️

2. unchecked exception (실행 예외)

컴파일러가 해당 예외를 확인하지 않고 예외 처리를 강제하지 않는 예외 RuntimeException을 상속한 클래스

• 처리 안해줘도 실행 되지만, 런타임에서 에러 발생

Throwable 클래스에 선언, Exception 클래스에서 오버로딩한 메소드

1. getMessage()

예외 메시지를 String 형태로 제공받는다. 예외가 출력되었을 때 어떤 예외가 발생되었는지를 확인할 때 매우 유용하다. 즉, 그 메시지를 활용하여 별도의 예외 메시지를 사용자에게 보여주려고 할 때 좋다.

2. toString()

예외 메시지를 String 형태로 제공받는다. 그런데, getMessage() 메소드보다는 약간 더 자세하게, 예외 클래스 이름도 같이 제공한다.

3. printStackTrace()

가장 첫 줄에는 예외 메시지를 출력하고, 두 번째 줄부터는 예외가 발생하게 된 메소드들의 호출 관계(스택 트레이스)를 출력해준다.

Exception 처리 방법

try : 예외 발생 가능성이 있는 로직이 포함된 블럭 catch : 예외가 발생했을 때 처리되는 로직이 포함된 블럭 finally : 예외가 발생하던 안하던 최종적으로 처리되는 로직이 포함된 블럭

[예외에 대한 책임 전가]

📍 *throw *

• 예외를 강제로 발생시킨 후, 상위 블럭이나 catch문으로 예외를 던진다.
• 즉, 예외를 발생시키는데 사용

public void divide(int num1, int num2) { if (num2 == 0) { throw new ArithmeticException("Divide by zero error"); } int result = num1 / num2; System.out.println("Result: " + result); }

📍 **throws **
- 예외가 발생할 수 있는 메서드에서 해당 예외를 호출자에게 전달하는 데 사용
- 예외를 직접 처리하지 않고, 호출자에게 예외 처리 책임을 넘기는 방식
- Throws를 던지면 해당 코드를 사용하는 쪽에서 try catch 요구를 받게 된다.

```java

import java.io.IOException;

public class FileReader {

    public void readFile() throws IOException {
        // 파일을 읽는 작업
        // IOException이 발생할 수 있음
    }

    public static void main(String[] args) {
        FileReader reader = new FileReader();
        try {
            reader.readFile();
        } catch (IOException e) {
            System.out.println("파일 읽기 오류: " + e.getMessage());
        }
    }
}

1. 예외 복구

• 예외 상황을 파악하고 문제를 해결해 정상 상태로 돌려놓는 방법
• 예외를 잡아서 일정 시간, 조건만큼 대기하고 다시 재시도를 반복
• 최대 재시도 횟수를 넘기게 되는 경우 예외 발생시킴

final int MAX_RETRY = 100;
public Object someMethod() {
    int maxRetry = MAX_RETRY;
    while(maxRetry > 0) {
        try {
            ...
        } catch(SomeException e) {
            // 로그 출력. 정해진 시간만큼 대기한다.
        } finally {
            // 리소스 반납 및 정리 작업
        }
    }
    // 최대 재시도 횟수를 넘기면 직접 예외를 발생시킨다.
    throw new RetryFailedException();
}

2. 예외처리 회피

• 예외 처리를 직접 담당하지 않고 호출한 쪽으로 던져 회피하는 방법
• 긴밀하게 역할을 분담하고 있는 관계가 아니라면 예외를 그냥 던지는 것은 무책임하다.

public void method1(){
 try {
   method2(); // throws가 붙은 method2는 반드시 이렇게 try문 안에서 호출되어야 함. 
   // method2가 떠넘긴 예외를 아래 catch문을 통해 처리
}
 catch (ClassNotFoundException e1) {
  System.out.println("클래스가 존재하지 않습니다.");
}

public void method2() throws ClassNotFoundException {
 Class class = Class.forName("java.lang.String22");
}

3. 예외 전환

• 회피와 비슷하게 메서드 밖으로 예외 던지지만, 그냥 던지지 않고 적절한 예외로 전환해서 넘기는 방법
• 더 명확한 의미로 전달하기 위해 적합한 의미를 가진 예외로 변경
• 예외 처리를 단순하게 만들기 위해 포장(wrap)할 수도 있음

// 조금 더 명확한 예외로 던진다.
public void add(User user) throws DuplicateUserIdException, SQLException {
    try {
        // ...생략
    } catch(SQLException e) {
        if(e.getErrorCode() == MysqlErrorNumbers.ER_DUP_ENTRY) {
            throw DuplicateUserIdException();
        }
        else throw e;
    }
}

// 예외를 단순하게 포장한다.
public void someMethod() {
    try {
        // ...생략
    }
    catch(NamingException ne) {
        throw new EJBException(ne);
        }
    catch(SQLException se) {
        throw new EJBException(se);
        }
    catch(RemoteException re) {
        throw new EJBException(re);
        }
}

서버쪽 시스템 오류를 메세지로 사용자에게 보여주게 되면, 심각한 보안적인 사고를 초래할 수 있다. 따라서 에러메세지를 사용자에게 보내주면 안될 때 오류를 파일 형식으로 저장할 수 있는 로깅 시스템을 사용한다.

문제

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
graph = []

for i in range(n):
    tmp = list(map(int, input().split()))
    graph.append(tmp)

s, x, y = map(int, input().split())

dx = [-1 ,1 , 0, 0]
dy = [0, 0, -1, 1]
def bfs(i, j):
    x, y = i, j
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<= nx < n and 0<= ny < len(graph[0]):
            # 한 번 전파될 때 숫자가 더 낮은 바이러스를 우선적으로 전파시켜주기 위한 조건문
            # 이미 한 번 전파되었고 현재 전파되는 바이러스가 더 작을 경우 현재 바이러스 숫자로 변경
            if graph[nx][ny] != 0 and visited[nx][ny] and (graph[nx][ny] > graph[x][y]):
                graph[nx][ny] = graph[x][y]
                visited[nx][ny] = True
            elif graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y]
                visited[nx][ny] = True

for _ in range(s):
    visited = [[False] * (len(graph[0])) for _ in range(n)]
    for i in range(n):
        for j in range(len(graph[0])):
            if graph[i][j] != 0 and not visited[i][j]:
                bfs(i, j)
    cnt = 0
    for row in graph:
        cnt += row.count(0)
    if cnt == 0:
        break
print(graph[x-1][y-1])

후기🤔

처음 시간초과 오류가 났다. 조건 중 '바이러스가 모두 전파된 경우 전파를 멈춘다'라는 조건을 처리해주지 않아서였다. 그래프에 0이 하나도 없을 경우 for문을 빠져나오는 부분을 추가해준 후 해결 ! 조건을 주는건 이유가 있기 때문에 모든 조건을 빠짐없이 처리해주자.

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

예제 입력 1

4 2 2 1 2 4 3 2 1 4 3 1 2 3 2

예제 출력 1

2 7

풀이

import sys
input = sys.stdin.readline
from collections import deque

nodes, n = map(int, input().split())
# graph에 저장되는 값 (연결된 노드, 거리)
graph = [[] for _ in range(nodes+1)]

# graph에 노드간 연결, 거리 정보 저장
for _ in range(nodes-1):
    a, b, dist = map(int, input().split())
    graph[a].append((b, dist))
    graph[b].append((a, dist))

for _ in range(n):
    # visited로 거리 계산
    visited = [-1 for _ in range(nodes+1)]
    a, b = map(int, input().split())
    queue = deque()
    queue.append(a)
    visited[a] = 0
    while queue:
        now = queue.popleft()
        if now == b:
            print(visited[b])
            break

        for node, dist in graph[now]:
            if visited[node] == -1:
                # 거리 누적 (이전노드까지 걸린 거리 + 이전 노드에서 현재 노드까지 걸린 거리)
                visited[node] += (visited[now]+(dist+1))
                queue.append(node)

후기 🤔

처음 dfs로 시도했다가 계속 실패해서 bfs로 풀었다. 거리를 누적해주는 부분에서 조금 고민했는데, '최단거리'를 구하는 문제와 유사하다. 이렇게 '거리'를 구할 때는 visited 자료형을 활용하면 된다는걸 기억하자 !

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

풀이 (BFS)

import sys
input = sys.stdin.readline
from collections import deque

row, col, n = map(int, input().split(' '))
graph = [[0]*(col) for _ in range(row)]

for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split(' '))
    for i in range(row-y2, row-y1):
        for j in range(x1, x2):
            graph[i][j] = 1

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

queue = deque()
def bfs(i, j, cnt):
    queue.append((i, j))
    count = cnt
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < row and 0 <= ny < col:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    queue.append((nx, ny))
                    count += 1
    return count
answer = []
for i in range(row):
    for j in range(col):
        if graph[i][j] == 0:
            graph[i][j] = 1
            cnt = 1
            tmp = bfs(i, j, cnt)
            answer.append(tmp)

answer.sort()
print(len(answer))
print(*answer)

후기 🤔

사각형이 있는 부분은 1, 그렇지 않은 부분은 0으로 채워두고 BFS로 하나씩 탐색하면 된다. 초반 그래프를 그릴 때 (1을 칠할 때) for문의 범위를 잡아주는 부분에서 헷갈려서 조금 오래걸렸다.

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

4
6
1
3
1
4

풀이 (BFS)

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
visited = [False for _ in range(n+1)]

# 노드 연결 정보
linked = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    linked[a].append(b)
    linked[b].append(a)

queue = deque()
queue.append(1)
answer = [[] for _ in range(n+1)]
while queue:
    parent = queue.popleft()
    for i in linked[parent]:
        if not visited[i]:
            visited[i] = True
            queue.append(i)
            answer[i] = parent

for i in range(2, n+1):
    print(answer[i])

graph에 노드들의 연결 정보를 저장한다. 최상단 노드인 1부터 큐에 넣는다. (큐에 들어간 노드는 이제 더이상 누군가의 자식 노드가 될 수 없다.) 이제 큐에서 하나씩 pop 하며 연결된 노드를 자식 노드로 저장하면 된다.

처음에 BFS방식이 아닌 for문을 사용해서 풀었다가 다시 풀었다.

자료구조, 알고리즘을 먼저 생각하고 문제에 적용하자

1번째 줄 : 커밋 내의 변경 내용을 요약
2번째 줄 : 빈 칸
3번째 줄 : 변경한 이유

작업트리와 인덱스

Git의 '커밋' 작업은 '작업 트리'에 있는 변경 내용을 저장소에 바로 기록하는 것이 아니라 '인덱스'에 파일 상태를 기록(stage - 스테이징) 해야 한다.

원격 저장소 복제 (Clone)

• 누군가의 변경 이력이 적용된 원격 저장소가 있으면, 그걸 통째로 복제해와 내 PC에서 작업할 수 있다. 이때 사용하는 것이 Clone !

• 변경 이력도 함께 로컬 저장소에 복제되어 오기 때문에, 원격 저장소와 똑같이 이력을 참조, 커밋 진행이 가능하다.

원격 저장소에서 Pull 해오기

• 원격 저장소를 공유해 여러 사람이 함께 작업하면, 모두가 같은 원격 저장소에 push를 하게 됨.
• 그렇다면, 다른 사람이 원격 저장소에 push한 내용을 내 로컬 저장소에도 pull 할 필요가 있다. (원격 저장소 변경 내역 로컬 저장소에 업데이트)

변경 이력 병합(Merge)

내가 pull을 한 후 다른 사람이 push를 해 원격 저장소를 업데이트 한 경우 내 push 요청이 거부된다.

이 경우 병합(merge) 작업을 통해 다른 사람의 업데이트 이력을 내 저장소에도 갱신해야 한다.

1. 수동으로 해결하는 방법

• 원격 저장소와 로컬 저장소 양쪽에서 파일의 동일한 부분을 변경한 경우 두 변경 내용 중 어느 쪽을 저장할 것인지 판단 할 수 없기 때문에 충돌 발생

Git은 충돌이 발생한 파일 내용을 위 그림처럼 표시해준다. (이 부분을 직접 수정해 주어야 함) 즉, 파일을 일일이 비교하며 바뀐 점을 찾아서 적용한 후 병합

당연히 "<<<<<<<< HEAD , >>>>>>>>>footer" 같은 충돌기호는 다 지워야 한다.

2. 깃으로 자동 병합

• 파일의 다른 위치를 수정했다면 깃에서 서로 다른 위치의 소스를 자동으로 병합하기 때문에 문제가 없다.

• 하지만 실제 개발 환경에서는 여러 사람이 같은 위치의 코드를 수정하기 때문에 자동병합으론 해결 못하는 충돌이 자주 일어남.

이 경우,

git checkout master : 기준이 되는 브랜치로 먼저 이동 git merge feature : 병합당하는_브랜치

명령어를 입력하면 브랜치의 코드가 아래처럼 수정된다.

동일한 곳을 수정했을 경우

아래처럼 수정됨

HEAD가 현재 브랜치이고, 둘 다 수락하거나 둘 중 하나를 수학하면 자동으로 충돌이 해결된다. 선택하고 add, commit 하면 병합이 완료된다.

충돌 예방 방법

• 내부적으로 팀원 간 규칙을 정하고 상의하면서 개발을 진행하면 항후 발생할 충돌을 줄인다.
• 자주 커밋하고 자주 병합할 수록 충돌이 발생할 기회는 적다.
• 자신의 브랜치 상태가 최신일수록 병합할 때 발생하는 충돌을 최소화 할수 있다.
• 기준이 되는 브랜치(예를 들어 master)를 자주 모니터링하고, 변화된 부분을 즉시 자신의 브랜치에 반영하면서 작업하면 충돌을 줄일 수 있다.

브랜치 병합 여부 확인

병합한 브랜치는 (*)로 표시된다!
git branch --no-merged :병합하지 않은 브랜치 조회

참고

1. https://backlog.com/git-tutorial/kr/intro/intro1_1.html
2. https://konkukcodekat.tistory.com/entry/%EA%B9%83git-%EB%B3%91%ED%95%A9-merge-Fast-Forward-3-way

• for문과 while문 while문은 반복 횟수가 상황에 따라 다른 경우에 사용하는 반면, for문은 반복횟수가 명확할 때 좋다.

• while문 예시

int n = 1;
while (n <= 10) {
  System.out.println(n);
  n++;
}

• for문 예시

  for (int i = 1; i <= 9; i++) {
  System.out.printf("3 x %d = %d\n", i, 3 * i);
  }

Python과 같이 break, continue 사용이 가능하다.

배열

자바의 배열은 Python의 List와 다르게 같은 형의 데이터만 저장할 수 있다.

배열이란?

여러 값을 하나의 변수로 묶은 것.

int[] scores = { 65, 74, 23, 75, 68, 96, 88, 98, 54 };


// 1) 배열 값 읽기(read)
int[] scores = {99, 88, 77};
System.out.println(scores[0]); // 99
System.out.println(scores[1]); // 88
System.out.println(scores[2]); // 77
// 2) 배열 값 변경(write)
System.out.println(scores[0]); // 99
scores[0] = 0; // 0번 인덱스 값 변경
System.out.println(scores[0]); // 0

length 키워드로 배열의 길이 알 수 있음

String[] names = {"Kim", "Lee", "Park", "Choi", "Oh", "Jo"};
int[] mathScores = {82, 76, 100, 92, 68, 96};
for (int i = 0; i < names.length; i++) {
  System.out.printf("%s : %d\n", names[i], mathScores[i]);
}

출처: https://cloudstudying.kr/courses/10

• 나눗셈 연산 주의 숫자간 연산은 더 큰 타입을 따른다.

  1. double a = 5.0 / 2.0; // 2.5
  2. int b = 4 / 2;        // 2
  3. int c = 5 / 2;        // 2.5 (X) => 2 (O)
  

• 타입 불일치 주의 변수에 값 대입 시, 그 값이 변수의 타입과 일치해야 한다.

  1. // 타입 불일치 에러
  2. int score = "100";
  3. 
  4. // 해결 방법
  5. int score = 100;      // int로 일치
  6. String score = "100"; // String으로 일치
  7. int score = Integer.parseInt("100"); // "100" => 100

• 타입 변환 주의 타입 불일치의 문제는 타입 변환을 통해 해결 가능하다.

  • 자동변환 (더 큰 타입으로 대입시 발생) ```

  1. // 자동 변환 (더 큰 타입으로 대입될 때)

  2. double p = 2; // 2 => 2.0

  3. int n = 5 / 2; // 2

  4. double q = n; // 2 => 2.0

  • 직접변환 (타입 casting) ```
  1. // 에러 발생
  2. int r = 10.4; // ERROR
  4. // 실수를 정수로 강제 캐스팅
  5. int r = (int) 10.4; // 10.4 => 10

메소드 호출과 정의

메소드란?

일련의 동작을 하나로 묶는 것 입력값에 따른 반환값이 있다.

메소드 정의

메소드를 사용하려면, 먼저 정의돼 있어야한다.

메소드 예시

public static int square(int n) {
  int result;
  result = n * n;
  return result;
}

다음과 같이 호출 가능

int z = square(4); // 입력: 4 => 반환: 16
System.out.println(z); // 16

조건문

조건문이란?

상황에 따라 실행 흐름을 달리하는 문법

• if문, else if문, else문

  if (90점이상?) {
  A 학점
  } else if (80점 이상?){
  B 학점
  } else {
  C 학점
  }

  비교 연산자

  System.out.println(7 > 4); // 7은 4보다 큰가? => true
  System.out.println(10 % 3 == 0); // 10을 3으로 나눈 나머지가 0인가? => false
  

```

논리 연산자

1. and -> &&
2. or -> ||
3. not -> !

출처: https://cloudstudying.kr/courses/10

• 자바 언어로 컴퓨터에게 일을 시키는 것.
• 개발자가 컴퓨터에게 시킬 일을 자바 언어(소스코드)로 작성하면, 소스코드는 컴파일러라는 번역기를 통해 기계어로 바뀐다.
• 컴파일링(compiling) : 자바 코드가 기계어로 번역되는 과정

자바의 특징과 객체지향

• 자바는 멀티플랫폼 언어이다.
  • 멀티플랫폼 언어 : 다양한 운영체제(UNIX, Window, MacOS, Android, etc..)에서 변경없이 동작. (이식성이 좋음)
• 자바는 객체지향 언어이다.
  • 객체 지향 언어 : 객체를 조립해 전체 프로그램을 만든느 언어

변수와 타입 그리고 연산자

• 변수 : 변하는 수로서, 이름 붙여진 메모리 공간
• 변수 생성의 예

  int mathScore = 88;            // 수학 점수를 저장할 공간
  String bookTitle = "오만과 편견"; // 책 이름을 저장할 공간
  double weight = 72.4;          // 무게를 저장할 공간
  boolean finished = true;       // 종료 여부를 저장할 공간

출처: https://cloudstudying.kr/courses/10