그리고 비동기로 불러온 데이터가 여러개면 조합을 할때 모든 데이터가 isLoading 인지를 체크해서 조건 통과할 때 넘겨줘야 하나? 근데 그러면 하나를 조회하다가 실패했을때 계속 유저는 화면을 기다리게 될 수도 있음… 흠

useSWR 생각할 것

유저가 클릭한 날짜로 쿼리를 생성한 다음, 여러 api로부터 데이터를 각각 불러와야 함 불러온 데이터를 기반으로 유저에게 보여줘야 할 데이터를 가공한 다음 화면에 뿌려줘야 함

• Fetch 호출
• 데이터가 준비되면 가공 시작
• 가공이 끝나면 화면에 넘겨주기

데이터가 준비되면 -> 어떻게 체크할건지 가공이 끝난 데이터 -> state로 관리? 가공이 끝나면 해당 state에 의존되는 useEffect로 리렌더링 유발 여러 api로부터 데이터를 불러올 때의 렌더링 기다리는 건 어떻게 처리할 수 있는지

그럴 때 revert를 사용하면 된다. 잘못 변경한 파일의 커밋을 revert를 역순으로 한 다음 다시 merge 하면 OK!

[참고한 블로그] (https://velog.io/@chosj1526/git-revert%EC%8B%9C-Conflict%EA%B0%80-%EB%B0%9C%EC%83%9D%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8A%94-%EC%83%81%ED%99%A9%EA%B3%BC-%EC%9D%B4%EC%9C%A0)

그래서 border-collapse를 separate로 분리하고 border-spacing: 0으로 주어 테이블 구성하는 셀 간 간격을 없앰

table className="border-separate border-spacing-0"

React, Next, Zustand, TS 사용해서 프로젝트를 하나 만들고 있는게 있는데, 실시간으로 데이터를 잘 받아와서 띄워주는게 굉장히 중요한 웹페이지다. 계속 데이터도 fetch해와야 하고, 버벅거리지도 않아야 해서 완전 SSR로 가기에는 부담스럽고... 어떻게 해야할지 Next.js 공식문서를 보다가 정확히 내 상황을 찾았다.

The data is frequently updated, which requires request-time data fetching. SWR The team behind Next.js has created a React hook for data fetching called SWR. We highly recommend it if you’re fetching data on the client side. It handles caching, revalidation, focus tracking, refetching on interval, and more. We won’t cover the details here, but here’s an example usage: .... 출처 : https://nextjs.org/learn-pages-router/basics/data-fetching/request-time

자주 데이터가 변경되어야 하고, 유저가 어떤 데이터를 불러올지 서버가 모르는 상황에서는 어쩔 수 없이 Client-side rendering을 해야한다. 그렇다고 싹 다 JS에서 useEffect써서 fetch해오자니 무식한것같고... 딱 SWR이 맞았다.

공식문서를 보면서 학습중이다. DB에서 불러온 데이터는 서버에 저장해두기에는 개인별로 어떤 데이터를 불러올지 모르기 때문에 전역상태(Zustand) 안 쓰고 SWR 쓰는게 더 좋을 것 같다.

다만.. 깡통서버에 올리다보니까 gcc도 없고 걍 깜깜해서 일단 정리만 해두고 안 함 ㅠ 넘 오래 걸릴듯해서..

root 계정 초기 비밀번호 설정 https://blog.naver.com/blacky512/10149326083

cp 시 omitting 에러가 날 경우 https://blog.naver.com/windil/63875933

• 자세한 cp 명령어 설명 https://backendcode.tistory.com/307

rm 명령어 설명 https://www.hostinger.com/tutorials/how-to-remove-files-and-folders-using-linux-command-line/#:~:text=To%20permanently%20remove%20a%20directory,directories%2C%20use%20the%20ls%20command.

오프라인 패키지 설치방법 (.deb 사용) https://rottk.tistory.com/entry/Ubuntu-Offline-package-%EC%84%A4%EC%B9%98

nodejs, yarn 오프라인 설치방법 (tar.xz 파일 들여와서 설치) https://songdev.tistory.com/80

ip 잡는법 https://velog.io/@3436rngus/Ubuntu-Server-20.04-LTS-netplan-interfaces-%EA%B3%A0%EC%A0%95-IP-%EC%84%A4%EC%A0%95 [서브넷마스크] (https://bumday.tistory.com/19)

폐쇄망 ubuntu가 18.04 버전이라 호환가능한 nodeJS 버전이 너무 낮음 -> NextJS나 React 들여오기엔 한계가 있어서 업글 필요

업그레이드는 한번에는 불가능하고 18 -> 20 -> 22 해줘야 하는데, usb로 iso 파일을 가져다가 해보기로 했다

다만 문제점은 미리 백업을 해두고 작업을 진행하는 것이 안전할 것 같은데 백업할 수 있는 패키지가 폐쇄망에 없다

따라서 VM에 폐쇄망과 동일한 환경을 설정하여 timeshift 패키지를 설치 후, 해당 파일을 반입하여 설치해보려 한다.

인터넷 되는 PC에서

VM을 다운받고, ubuntu 18.04 환경으로 실행해주었다. terminal도 안 켜져서 언어설정을 English(US) -> English(Canada)로 바꿔주고 하니까 된다.. 물론 sudo 권한도 없어서 구글링을 통해 권한 부여하고 sudoers 폴더에도 넣어주었다.

timeshift는 20부터 제대로 지원하는지, 18은 다음과 같이 설치해야 함

sudo add-apt-repository -y ppa:teejee2008/ppa
sudo apt-get update
sudo apt-get install timeshift

(참고 블로그 : https://joggle.tistory.com/3)

deb 파일 만들기

https://tw0226.tistory.com/13 참고하여 진행함

VM VirbutalBox <-> Window 간 파일 옮기기

https://yeni03-0w0.tistory.com/34 & https://pururing-log.tistory.com/60 두 블로그 참고하여 진행 공유폴더 만들어서 deb 파일 내보낸 뒤, usb에 저장하기

폐쇄망 PC

deb 파일 설치하기

sudo dpkg -i /path/to/deb/file.deb 로 파일을 설치해준다. (스택오버플로우 참고)

timeshift 실행하여 백업하기 (시스템 백업)

GUI 버전 링크 참고하여 진행 Command Line버전 링크 참고하여 진행 Command Line버전2 여기 링크를 봐도 괜찮았다.

tar 사용하여 백업하기 (데이터 백업)

참고블로그

timeshift는 데이터백업은 안된다고 하니... tar 사용해서 전체 서버 백업도 해두자

백업이 완료되면 다시 인터넷 되는 PC에서 ubuntu 20 iso 파일을 준비하자

인터넷 PC

iso 파일 다운받아 부팅디스크 만들기

1. iso 파일 다운받기 ubuntu desktop이랑 server 두개 있는데 GUI 유무 차이라고 한다. 기존 서버가 server여서 동일하게 다운받았다.
2. Rufus 프로그램을 사용하여 usb에 부팅디스크 만들기

폐쇄망 PC

upgrade Ubunutu

3. usb 꽂고 켜기 (bios에서 부팅을 usb를 먼저 인식하게 해줘야 한다) https://ubuntu.com/tutorials/install-ubuntu-server#1-overview 공식 페이지를 참고하자 아니면 여기도 참고했다

   To upgrade Ubuntu using a bootable USB drive:

   1) Create a bootable USB drive with the latest Ubuntu installer. You can download the ISO from the Ubuntu website and use a tool like Rufus or balenaEtcher to create the bootable USB. 2) Plug the bootable USB into the computer you want to upgrade. 3) Reboot the computer and enter the BIOS or boot menu. This is usually done by pressing a key like F2, F12, or Del during boot. 4) In the BIOS or boot menu, select the bootable USB drive as the boot device. 5) The Ubuntu installer will load from the USB drive. Choose the "Upgrade Ubuntu" option and follow the on-screen instructions to complete the upgrade process. The installer will guide you through the steps to upgrade your existing Ubuntu installation to the newer version, preserving your personal files and settings where possible. Make sure to back up any important data beforehand just in case.

일반적으로 1억번(100,000,000 = 10^8)의 연산 = 1초의 실행시간 (당연한건데 자꾸 헷갈려서.. 4개단위로 끊어서 보자고)

시간복잡도의 유형

• 빅오메가 : best case
• 빅세타 : average case
• 빅오(O(n)) : worwt case의 연산횟수. 항상 최악의 경우를 고려함

보통 n^2, nlogn 중 고민하게 된다

처리할 데이터가 많아질수록 차이가 급격하게 벌어짐

만약 시간제한이 2초인 경우

→ 2억번 이하의 연산을 해야되는구나! 도출하기

백만개의 데이터를 2초 안에 정렬해야하는 경우, 버블정렬(n^2) vs 병합정렬(nlogn)중에는 당연히 후자를 골라야함 why? nlogn 백만 -> 2천만번 < 2억번

알고리즘 잘 고른 것 같은데 시간초과가 나는 경우

가장 많이 중첩된 반복문의 시간복잡도를 살펴볼것!! (상수는 무시)

디버깅

• 디버깅 : 프로그램에서 발생하는 문법 오류, 논리 오류를 바로잡는 과정

음수가 나올 수 없는데 음수가 나왔다?

→ 자료형 체크!!! (overflow 발생했을 가능성 큼) ex. int -> long long으로 바꿔보자

배열, 리스트, 벡터

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근 가능
2. 새로운 값 삽입 / 특정 인덱스 삭제가 어려움 → 해당 인덱스 주변의 값을 이동시키는 과정 필요
3. 배열의 크기는 선언할때 지정, 한번 선언시 크기 변경 불가능
4. 구조가 간단하여 코테에서 많이 사용

리스트의 특징

(값, 포인터) 노드라는 것을 포인터로 연결한 자료구조

1. 인덱스가 없어서 Head 포인터부터 순서대로 접근. 접근 속도 느림
2. 포인터로 연결되어 있어 삽입/삭제 연산 빠름
3. 선언 시 크기 별도 지정할 필요 없음 (따로 크기가 정해져있지 X)
4. 포인터를 저장할 공간이 필요하여 배열보다 구조 복잡

벡터의 특징 (중요!)

C++ 표준 라이브러리에 있는 자료구조 컨테이너 중 하나 배열의 특징을 가지면서 배열의 단점을 보완한 동적 배열의 형태

1. 동적으로 원소를 추가할 수 있다. 크기가 자동으로 늘어남
2. 맨 마지막 데이터 삽입/삭제는 문제X. 중간 데이터의 삽입 삭제는 배열과 같은 매커니즘
3. 인덱스를 시용하여 접근 가능

#include <vector> 해줘야 사용 가능!

합배열

배열이 바뀌지 않을때, 구간합을 구하기 유용하다 배열 각 칸의 누적합을 저장해두고 특정 부분의 구간합을 구해야할 때 사용

배열 A 누적합 배열 S

S[i] = S[i-1] + A[i]

2~5 사이의 누적합 : S[5] - S[1]

만약 배열의 값이 자주 바뀐다면? -> 세그먼트 트리 (인덱스 트리) 사용

백준 1253 좋은 수 구하기

백준 1253. 버블소트

• 시간제한 2초
• 서로 다른 두 수의 합으로 특정 수를 만들어내야 하므로 좋은 수 판별 알고리즘이 N^2를 넘어가면 안된다. (하나하나 살펴보면서 처리해주면 안된단 뜻)

→ nlogn의 시간복잡도인 정렬 + 두 수를 체크해야 하므로 투 포인터 (O(N))

두 수를 살펴봐야 하는 경우 -> 투포인터를 의심하자

C++ 입출력 빠르게

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(NULL);
    cin.tie(NULL);
}

• ios::sync_with_stdio(false); : C에서의 입출력 라이브러리 stdio, C++에서의 입출력 라이브러리 iostream의 버퍼 동기화를 분리. C++만의 버퍼를 사용해서 검사할 버퍼의 크기가 줄어들어 속도 향상 (C언어 입출력함수 printf, scanf등 사용 불가)

• cin.tie(NULL); : cin, cout의 tie를 풀어준다. cin, cout은 기본적으로 tie되어있어 cin을 사용하기 전에 cout에서 출력할 값을 내보냄. 출력할 값을 버퍼에서 내보내는 flush 과정을 건너뛰므로 속도 향상 (cout에서 입력을 받기 전에 무언가를 표시할 때마다 cin을 수동으로 플러시해줘야 함)

• endl 대신 \n 쓰기 : endl은 개행 후 버퍼를 비워주는 역할까지 하므로 단순 개행문자를 사용하는 것이 속도가 조금 더 빠르다

cin, getline 차이

• cin : 띄어쓰기(공백) 기준으로 입력받음. \n 만나면 저장하지 않고 버퍼에 넣어준뒤 그 전까지의 입력만 받음
• getline : 3번째 파라미터로 주어지는 것을 기준으로 입력을 분할하여 받음. 디폴트값은 \n. cin과 달리, \n 자체를 저장 가능

백준 1377 - 버블정렬

백준 1377. 버블소트 문제에서 시키는대로 버블정렬하면 시간초과난다. N은 50(510^5)만이므로 N^2를 하면 기준시간 2초(2억번 210^8)에 절대 못 들어온다.

따라서 버블정렬 내에서 최적화를 시켜주는 것이 아니라 문제에서 출력하는 값이 정확히 무엇인지를 판단하는 것이 중요하다

문제에서 출력하는 값 i는 몇 번의 swap이 일어났는지 그 횟수+1를 출력해주는 것이다. 즉, 반복문이 몇 번 돌았는지를 체크해주는 것!

핵심 아이디어는 정렬 후 인덱스 값 - 초기 인덱스값의 max값이 최대 반복 횟수와 같다는 것이다.

따라서 nlogn의 시간복잡도를 가지는 algorithm 라이브러리의 sort함수를 실행해준 뒤 인덱스값의 차이를 구해주면 된다.

(어렵다)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N = 0;
    cin >> N;

    // (값, 인덱스) 쌍으로 넣어주기
    vector<pair<int, int>> A(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i].first;
        A[i].second = i;
    }

    sort(A.begin(), A.end());

    int Max = 0;
    for (int i = 0; i < N; i++) {
        if (Max < A[i].second - i) {
            Max = A[i].second - i;
        }
    }

    cout << Max + 1;
    return 0;
}

정렬 여부를 처리해줄때 인덱스를 가지고 몇번의 swap이 일어났는지 체크해줄 수 있음을 알고가자!

입력되는 문자열을 Tree 형식으로 만들어 진행되어 보다 빠르게 문자열 검색이 가능한 자료구조 문자열을 검색하는 문제에서 입력되는 문자열이 많을 경우 자주 사용

해설참고 [Lv 3. 금과 은 운반하기] (https://school.programmers.co.kr/learn/courses/30/lessons/86053)

풀이

가능한 범위가 넓기 때문에 이분탐색으로 훑어야한다. 여기까진 캐치했지... 근데 주어진 시간이 이분탐색의 기준이 되고, 금/은을 나눠서 가져오는 과정에서 구현이 안되서 다른 풀이를 참고했다. 프로그래머스 AI 추천 잘하네... 어쩜 이리 잘 못 푸는 문제만 쏙쏙^^...

참고한 블로그

Lv 3는 언제쯤 잘 풀릴까...

코드

def solution(a, b, g, s, w, t):

    start = 0
    end = 10**9*4*10**5 # 최대 필요량(10**9) * 금,은 2번 왕복(4) * 최소무게(1) * 최대시간(10**5)

    # 최솟값을 찾아야하므로 최댓값에서 시작
    answer = end
    while start <= end:
        mid = (start+end)//2
        gold = 0
        silver = 0
        total = 0

        for i in range(len(g)):
            now_gold = g[i]
            now_silver = s[i]
            now_weight = w[i]
            now_time = t[i]

            # 현재 마을에서 옮길 수 있는 총 횟수 (왕복으로 계산)
            move_cnt = mid // (now_time * 2)
            # 만약 나머지가 now_time보다 크면 1번 편도 가능하므로 1번 더 계산
            if mid % (now_time*2) >= now_time:
                move_cnt += 1

            # move_cnt(운반횟수) * now_weight(한번에 옮길수있는 무게) = 총 운반할수있는 양
            # gold, silver, total에 각각 더하는 값은, 보유량(now_g, now_s)과 왕복으로 옮기는 총량(move_cnt * now_w) 중 최소값
            gold += now_gold if (now_gold < move_cnt * now_weight) else move_cnt * now_weight 
            silver += now_silver if (now_silver < move_cnt * now_weight) else move_cnt * now_weight
            total += now_gold + now_silver if (now_gold + now_silver < move_cnt * now_weight) else move_cnt * now_weight 

        # 모두 옮길 수 있는 충분한 시간이었음
        if gold >= a and silver >= b and total >= a + b:
            end = mid - 1
            answer = min(answer, mid)
        else:
            start = mid + 1


    return answer

해설참고 [Lv 4. 자동완성] (https://school.programmers.co.kr/learn/courses/30/lessons/17685)

풀이1 (정렬로 처리)

예전에 비슷한 문제를 풀어본 적이 있었다. 접두사가 같은 단어를 체크해주는 그런 문제였던 것 같은데 거기서 정렬로 문제를 처리해줬던 게 생각났음...! 근데 구현은 직접 못했다 다른 사람 코드 보면서 연습하다보면 늘겠거니 한다...

참고한 블로그는 여기

등장하는 단어를 모두 정렬하면 인접한 2개의 단어가 비슷한 글자가 등장할 수 있는 단어다. 따라서 앞, 뒤 단어를 살펴보면서 일치한 글자수+1의 최댓값을 가져오면 된다.

코드1

def solution(words):
    N = len(words)
    words.sort() # 단어를 사전순으로 정렬
    result = [0] * N # 단어마다 입력해야 하는 문자 수

    for i in range(N - 1):
        # 인접하는 두 단어 비교
        now_word = words[i]
        next_word = words[i + 1]
        for j in range(min(len(now_word), len(next_word))):
            if now_word[j] != next_word[j]:
                j -= 1 # 일치하지 않으면 일치하는 최대 인덱스로 저장 후 break
                break

        # 일치하는 인덱스 + 1만큼 문자를 입력해야 찾을 수 있다 
        # (j는 0부터 시작하니 +1)
        # 단, 입력하는 문자 수가 단어 길이를 넘으면 안됨
        result[i] = max(result[i], min(len(now_word), j + 2))
        result[i + 1] = max(result[i + 1], min(len(next_word), j + 2))

    # 합계가 검색결과 총 횟수
    return sum(result)

풀이2 (트라이)

트라이 자료구조를 사용하면 훨씬 깔끔하게 풀 수 있다

글자별로 (letter, [0, {}]) 의 자료를 만들어서 몇개의 글자가 등장하는지 세어주고 이어붙여준다

위와 같이 등장하는 글자로 트리를 만들어주면서 해당되는 데이터가 뭔지 체크해준다!

{'g': [3, {'o': [2, {'n': [1, {'e': [1, {}]}]}], 'u': [1, {'i': [1, {'l': [1, {'d': [1, {}]}]}]}]}]}

이 분 블로그도 나중에 참고해서 공부해야지

코드2

def make_trie(words):
    dic = {}
    for word in words:
        current_dict = dic
        for letter in word:
            current_dict.setdefault(letter, [0, {}])
            current_dict[letter][0] +=1              
            current_dict = current_dict[letter][1]

    return dic

def solution(words):
    answer = 0
    trie = make_trie(words) 
    for word in words:
        temp = trie
        for letter in word:
            answer += 1
            temp = temp[letter]
            if temp[0] == 1:
                break
            else:
                temp = temp[1]

    return answer

오늘 푼건 거의 다 해설을 보고 했군... 어렵다

풀이

그래프 내에서 최단 거리를 구해야한단거는 캐치했는데 최종 로직이 안 나와서 해설을 참고했다. 이 문제는 특정 지점까지 합승을 하고, 그 뒤는 따로 이동하는 경우다.

따라서 최단거리는 k번 노드까지 합승을 하고, k번 노드에서 각자 따로 가는 경우를 1~n번까지 돌면서 최솟값을 구해줘야한다.

코드

# 최종 로직이 안떠올라 해설 참고
def floyd(graph, n):
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n+1):
                if graph[a][b] > graph[a][k] + graph[k][b]:
                    graph[a][b] = graph[a][k] + graph[k][b]
    return graph

def solution(n, s, a, b, fares):
    graph = [[int(1e9) for _ in range(n+1)] for _ in range(n+1)]

    for c, d, f in fares:
        graph[c][d] = f
        graph[d][c] = f

    for i in range(1, n+1):
        graph[i][i] = 0

    graph = floyd(graph, n)

    answer = int(1e9)
    # k까지 합승한다고 고려, s->k + k->a + k->b (이걸 떠올려야함)
    for k in range(1, n+1):
        answer = min(answer, graph[s][k] + graph[k][a] + graph[k][b])

    return answer

__pycache__

만약 위의 폴더가 생성된다면, 파이썬이라는 인터프리터가 메모리 로딩을 좀 더 빨리하기 위해 컴파일을 시켜줬다~ 라고 이해해주기

module

파이썬에서 module이란 하나의 py(파이썬 파일)을 의미 모듈 안에는 함수, 클래스가 존재할 수 있어 모두 가져오거나 필요한 내용만 골라서 호출할 수도 있음 같은 디렉토리 안에 있어야 호출 가능하다

if name == "main" 사용 이유

파이썬 파일을 모듈로 불러와 호출할 때 해당 파일에 함수, 코드 다 섞여있으면 import를 하자마자 실행될 수 있다. (그냥 print문이 존재하는 등) 따라서 파이썬 파일을 직접 실행할 때만 호출되도록 하고 싶은 구문은 위의 코드로 감싸주면 된다.

만약 모듈로 호출이 된다면 __name__에는 모듈 이름이 설정된다. 해당 파일을 커맨드라인 등 직접 실행한다면 __name__에는 __main__이라는 값(네임스페이스)가 들어간다.

import 방법의 종류

모듈 import시 모든 코드가 메모리에 로딩되는 것을 방지하기 위해 Alias as 를 설정하거나 from을 사용하여 특정 함수나 클래스만 호출할 수도 있다.

여러 방법 중 가독성을 높여주는 방식은 해당 함수가 어디서 왔는지 명시적으로 밝혀주는 Alias 방식이다.

import fah_converter as fah
print(fah.convert_c_to_f(41.6))

위와 같이 fah라는 모듈에서 함수를 불러왔다는 것을 코드만 봐도 알 수 있게 된다.

패키지

모듈이 모여 폴더로 연결, 패키지가 됨 (하나의 대형 프로젝트를 만드는 코드의 묶음)

폴더 별로 __init__.py 구성하기

• 현재 폴더가 패키지임을 알리는 초기화 스크립트
• 원래는 없을 경우 패키지로 간주하지 않았으나, python 3.3+ 부터는 X
• 하위 폴더와 py 파일(모듈)을 모두 구성
• 앞으로 무엇을 쓸건지 알려주는 역할

__all__ = ["image", "sound"]
from . import image
from . import sound

위와 같은 형식으로 작성

파이썬 가상 환경

virutalenv

virutalenv + pip 가장 대표적인 가상환경 관리 도구 레퍼런스, 패키지의 개수면에서 pip로 설치할 수 있어서 유용

conda

상용 가상 환경 도구 아나콘다에서 사용되는 가상환경 도구 Windows에서 매우 편리~! (컴파일된 도구까지 한꺼번에 다운) (pip는 python이 C로 되어있는데 pip는 컴파일된 코드가 안 들어가있을때가 있음)

conda create -n 프로젝트이름 python=3.11

위와 같은 형식으로 가상환경을 만들어준 뒤 실행하면 된다.

6. File / Exception / Log Handling

파일의 종류

• Binary 파일 : 이진법 형식 (컴퓨터만 이해할 수 있다) -> 메모장으로 열면 깨져보임. ex) excel 파일 등 어플리케이션에 종속된 경우
• Text 파일 : 문자열 형식 (인간이 이해할 수 있다) -> 메모장으로 열면 내용 확인 가능

7. Numpy

Numpy

import numpy as np 보통 np로 alias 처리를 해서 넣는 경우가 대부분

array creation

• 생성 : test_array = np.array([1,2,3], float)

• numpy.ndarray 객체로 생성

• 하나의 데이터 타입만 배열에 넣을 수 있음

• dynamic typing이 지원되지 않음

• C의 Array를 사용하여 배열을 생성

• shape : numpy array의 dimension 구성을 반환 ex. [[1,2,3,3],[4,5,6,6],[7,8,9,9]] -> (3,4) ex. [1,2,3,4] -> (4,) (튜플이라서 값 1개 반환시 뒤에 콤마 존재)

• dtype : numpy array의 데이터 타입을 반환

• ndim : number of dimensions 몇차원이냐

• size : data의 전체 개수

• nbytes : ndarray object의 메모리 크기 반환

일반적인 리스트와 달리, 원하는 행과 열만 뽑아내는 slicing이 가능함

서비스 배포는 vercel을 사용해서 했고 서비스의 주소는 https://willing.vercel.app/ 이다.

현재는 데이터 저장을 브라우저 local storage에 하고 있는데 웹<->앱 등 유저 기반으로 할 수 있도록 조금 여유 생기면 얼른 서버까지 하고 싶다!!

DFS처럼 쭉 진행하다가 더이상 진행할 필요가 없을 때는 되돌아가는 기법

백트래킹으로 순열 구현하기

진짜!!! 이해가 안되서 하나하나 자세히 적어둔다. 백준 N과 M(1) 문제의 소스코드다.

N개 중 M개를 뽑으면 되는데, 이때 M이 N이 되면 순열을 구하는거고 아니면 부분순열 구하는 것.

재귀함수로 들어가야하기때문에 반드시 종료조건을 적어주고 시작해야한다. 종료조건은 지금까지 뽑은 숫자의 개수가 M개가 될 때다. 그러면 원하는 작업을 해준 뒤(문제의 경우 출력) return해주면 된다.

N개의 숫자 배열을 전부 돌면서 M개를 뽑아야 되기 때문에 반복문으로 처음부터 끝까지 순회한다. i번째 요소를 사용했음을 저장해야 올바른 인덱스 숫자를 가져올 수 있으므로 visited 배열을 사용하여 현재까지 어떤 인덱스가 사용되었는지 저장한다. 따라서 반복문을 시작하자마자 visited[i]가 사용되었는지 체크하고 사용되었다면 그 경우를 살펴보지 않고 넘어간다. visited[i]를 방문 처리해준 뒤, 해당 인덱스 숫자를 배열에 넣어준다. 그런 뒤 다음 단계로 넘어갈 수 있도록 함수를 호출(재귀)한다.

여기에서 반복문을 마무리하면 1가지 경우밖에 살펴볼 수 없다. 따라서 return을 만나 호출이 끝난 뒤 되돌아오면 사용했던 요소 visited[i]를 사용 해제해주고 배열에서도 제거해줘야 모든 경우를 살펴볼 수 있다.

3개월 전에 분명 이 시리즈를 다 풀었음에도 왜 이리 새로운지. 알고리즘을 까먹지 않게 계속 유형별로 꾸준히 풀어야함을 다시 느낀다... 참고하기 좋은 유튜브를 함께 기록한다.

from sys import stdin

input = stdin.readline

N, M = map(int, input().split()) # N개 중 M개를 뽑아야 함
arr = []
visited = [False] * (N + 1)


def dfs():
    if len(arr) == M:
        print(" ".join(map(str, arr)))
        return

    for i in range(1, N + 1):
        if visited[i]:
            continue
        visited[i] = True
        arr.append(i)
        dfs()
        arr.pop()
        visited[i] = False


dfs()

[실버2. 백준 10819 차이를 최대로] (https://www.acmicpc.net/problem/10819)

풀이

순열을 구하면 되는 문제다. 백트래킹 연습으로 계속 풀어보고 있다.

코드

N = int(input())
data = list(map(int, input().split()))


max_data = -int(1e9)
arr = []

visit = [False] * (N)


def dfs():
    global max_data
    if len(arr) == N:
        sum_ = 0
        for i in range(N - 1):
            sum_ += abs(arr[i] - arr[i + 1])
        max_data = max(max_data, sum_)
        return

    for i in range(N):
        if not visit[i]:
            visit[i] = True
            arr.append(data[i])
            dfs()
            visit[i] = False
            arr.pop()


dfs()
print(max_data)

풀이

그렇게까지 복잡한 구현이 아니라고 생각했는데 시간이 너무 오래 걸려서 해설을 봤다ㅠ 참고한 블로그는 여기

포인트

1. 공은 동시에 굴러감
2. 같은 방향으로 다 굴린 다음 같은 좌표에 존재한다면 더 많이 움직인 구슬을 한칸 뒤로
3. 공은 벽을 만날 때까지 계속 데굴데굴 굴러감
4. 움직인 좌표값의 저장은 최종적으로 도착한 좌표만 해도 OK (빨간 공, 파란 공 좌표를 동시에 저장)

큐에 값을 넣을 때 (빨간공 좌표, 파란공 좌표) 를 같이 넣어서 동시에 계산해줘야 한다. 그리고 벽을 만날 때까지 계속 굴리다가 벽을 만나면 한칸 뒤로 후진해줘야 한다. 만약 구멍을 만난다면 끝! 10번 넘게 움직이거나 BFS를 다 돌았음에도 도달하지 못했다면 -1를 출력한다.

코드를 보면 대충 이제 알겠는데 시간 안에 차근차근 구현하는건 아직도 왜 이리 부족한지 모르겠다. 정진하자!!!!!

코드

from sys import stdin
from collections import deque

input = stdin.readline

# 목표는 빨간 구슬 구멍으로 빼내기 / 파란 구슬이 들어가면 안됨!
# 공은 동시에 움직인다.
# n = 세로 크기 Row, m = 가로 크기 Col
n, m = map(int, input().split(" "))

# . = 빈칸 / # = 장애물, 벽 / o = 구멍
# 그래프 입력받기
graph = []
R = [0, 0]
B = [0, 0]
target = [0, 0]
for a in range(n):
    sub = list(input())
    graph.append(sub)
    for b in range(m):
        if sub[b] == "R":
            R = [a, b]
        elif sub[b] == "B":
            B = [a, b]
        elif sub[b] == "O":
            target = [a, b]

answer_mark = False

# 상, 하, 좌, 우
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

q = deque()

# R 좌표, B 좌표
q.append((R[0], R[1], B[0], B[1], 0))

visited = set()
visited.add((R[0], R[1], B[0], B[1]))

while q:
    rx, ry, bx, by, cnt = q.popleft()

    if graph[rx][ry] == "O":
        print(cnt)
        answer_mark = True
        break

    if cnt >= 10:
        continue

    # r, b 움직이기
    for k in range(4):
        r_move = 0
        b_move = 0

        # r 움직이기
        nrx = rx + dx[k]
        nry = ry + dy[k]

        while True:
            # 벽이면 한칸 뒤로 이동
            if graph[nrx][nry] == "#":
                nrx -= dx[k]
                nry -= dy[k]
                break
            elif graph[nrx][nry] == "O":
                break

            nrx += dx[k]
            nry += dy[k]

            r_move += 1

        # b 움직이기
        nbx = bx + dx[k]
        nby = by + dy[k]
        while True:
            # 벽이면 한칸 뒤로 이동
            if graph[nbx][nby] == "#":
                nbx -= dx[k]
                nby -= dy[k]
                break
            elif graph[nbx][nby] == "O":
                break

            nbx += dx[k]
            nby += dy[k]
            b_move += 1

        # B 빠지면 안됨
        if graph[nbx][nby] == "O":
            continue

        # r, b가 같은 경우 / O일때 아닐때
        if nrx == nbx and nry == nby:
            # 더 움직임이 많은걸 한칸 뒤로
            if r_move > b_move:
                nrx -= dx[k]
                nry -= dy[k]
            else:
                nbx -= dx[k]
                nby -= dy[k]

        if not (nrx, nry, nbx, nby) in visited:
            visited.add((nrx, nry, nbx, nby))
            q.append((nrx, nry, nbx, nby, cnt + 1))


if answer_mark == False:
    print(-1)

최소의 비용으로 모든 노드가 연결된 최소 스패닝 트리를 만들 수 있는 알고리즘이다.

union-find 방법(서로소 집합)을 통해 사이클을 판별하는 방법은 무방향 그래프에서만 가능하다.

1. 그래프에 대한 간선 정보만 따로 빼내서 오름차순으로 정렬한다. 간선을 하나씩 확인하며 간선이 사이클을 발생시키는지 확인 (사이클 발생 확인 방법 : 연결된 루트 노드가 같은지) 2-1. 사이클X, 최소 스패닝 트리에 포함 (노드와 노드의 루트 노드를 연결) 2-2. 사이클O, 최소 스패닝 트리에 포함X
2. 모든 간선에 대해서 2번 과정 반복

방향 그래프에서 사이클 찾기

방향 그래프에서 사이클이란 특정 정점에서 시작하여 어떤 경로를 지나 다시 그 정점으로 돌아오는 경로를 의미한다. 따라서 DFS를 이용해 그래프를 탐색하며, 시작점과 방문점이 같은 경우 사이클이 존재한다고 판단할 수 있다. 참고한 블로그

코드 : 시간복잡도 O(V(V+E)

from collections import defaultdict

def solution1():
    N = 7
    # 4,6,7 노드간 사이클 존재
    edges = [(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (6, 4), (4, 7), (7, 6)]

    graph = defaultdict(list)
    for edge in edges:
        s, e = edge
        # 그래프 연결
        graph[s].append(e)

    visit = [0] * (N + 1)

    # 시간복잡도 DFS O(V+E),
    # 모든 정점에 하므로 O(v(V+E))
    def dfs(start, here):
        # 재귀 함수 종료 조건
        # 이미 방문했고
        if visit[here]:
            # 시작 정점과 현재 방문 정점이 같다면 싸이클
            if start == here:
                return False
            # 같지 않다면 싸이클X 노드에서 온 것임
            return True

        # 방문 처리
        visit[here] = True
        for node in graph[here]:
            # 시작 정점을 그대로 둔 채로 DFS로 노드 계속 탐색
            if dfs(start, node):
                # DFS가 true를 반환하는 경우 사이클 존재
                return True
            return False

    # 시간복잡도 O(V+E)로 해결하기
    # DFS를 수행하다가 재귀 탐색이 종료되지 않았는데 다시 방문하게 되면 사이클 O
    # 사이클이 존재하는 노드와 연결된 노드로부터 사이클 존재여부 바로 확인O

    def dfs2(here):
        if visit[here]:
            # DFS가 아직 안 끝났는데 사이클
            if visit[here] == -1:
                return True
            return False

        # DFS 아직 안 끝남
        visit[here] = -1

        for node in graph[here]:
            if dfs(node):
                return True
        # DFS가 끝났으므로 1로 설정
        visit[here] = 1
        return True

    for i in range(1, N + 1):
        # 사이클이 하나라도 존재한다면 사이클이 있는 그래프
        if dfs(i, i):
            return True
        return False


print(solution1())

코드 : 시간복잡도 O(V+E)

from collections import defaultdict


def solution2():
    N = 7
    # 4,6,7 노드간 사이클 존재
    edges = [(1, 2), (1, 5), (2, 3), (2, 6), (3, 4), (6, 4), (4, 7), (7, 6)]

    graph = defaultdict(list)
    for edge in edges:
        s, e = edge
        # 그래프 연결
        graph[s].append(e)

    visit = [0] * (N + 1)

    # 시간복잡도 O(V+E)로 해결하기
    # DFS를 수행하다가 재귀 탐색이 종료되지 않았는데 다시 방문하게 되면 사이클 O
    # 사이클이 존재하는 노드와 연결된 노드로부터 사이클 존재여부 바로 확인O

    def dfs2(here):
        if visit[here]:
            # DFS가 아직 안 끝났는데 사이클
            if visit[here] == -1:
                return True
            return False

        # DFS 아직 안 끝남
        visit[here] = -1

        for node in graph[here]:
            if dfs2(node):
                return True
        # DFS가 끝났으므로 1로 설정
        visit[here] = 1
        return True

    return dfs2(1)


print(solution2())

그리디 (크루스칼 알고리즘)

[골드4. 백준 1197 최소 스패닝 트리] (https://www.acmicpc.net/problem/1197)

풀이

크루스칼 알고리즘 (그리디)

1. 간선을 오름차순으로 정렬
2. 간선을 하나씩 확인하며 간선이 사이클을 발생시키는지 확인 (사이클 발생 확인 방법 : 연결된 루트 노드가 같은지) 2-1. 사이클X, 최소 스패닝 트리에 포함 (노드와 노드의 루트 노드를 연결) 2-2. 사이클O, 최소 스패닝 트리에 포함X
3. 모든 간선에 대해서 2번 과정 반복

크루스칼 알고리즘을 연습하기 좋은 문제.

코드

from sys import stdin

input = stdin.readline

V, E = map(int, input().split(" "))

dist = []
for _ in range(E):
    a, b, c = map(int, input().split(" "))
    dist.append([a, b, c])

# 간선을 오름차순으로 정렬
dist.sort(key=lambda x: (x[2]))

# 부모 테이블
parent = [i for i in range(V + 1)]


def find_parent(parent, n):
    if parent[n] != n:
        parent[n] = find_parent(parent, parent[n])
    return parent[n]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


answer = 0
for a, b, edge in dist:
    # 사이클 존재 X
    if find_parent(parent, a) != find_parent(parent, b):
        # 연결하고 최소 스패닝 트리에 포함 (가중치만 출력하면 되므로 합계)
        union_parent(parent, a, b)
        answer += edge

print(answer)

[골드4. 백준 1922 네트워크 연결] (https://www.acmicpc.net/problem/1922)

풀이

크루스칼 알고리즘 연습하기 좋은 다른 문제! 응용 없이 완전 기본 문제다. 크루스칼 알고리즘을 써야해서 골드에 난이도가 책정된듯?

코드

from sys import stdin

input = stdin.readline

N = int(input())  # 정점
M = int(input())  # 간선

dist = []
for _ in range(M):
    a, b, c = map(int, input().split(" "))
    dist.append((a, b, c))  # a-b : 비용 c

# 간선비용 기준 정렬
dist.sort(key=lambda x: (x[2]))

parent = [i for i in range(N + 1)]


# union-find
def find_parent(parent, n):
    if parent[n] != n:
        parent[n] = find_parent(parent, parent[n])
    return parent[n]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


answer = 0
for a, b, cost in dist:
    if find_parent(parent, a) != find_parent(parent, b):
        # 사이클 X => 연결 후 최소 스패닝 트리에 포함
        union_parent(parent, a, b)
        answer += cost

print(answer)

✨[골드1. 백준 17472 다리 만들기 2] (https://www.acmicpc.net/problem/17472)

풀이

✨ 달아놓은 이유는... 잘풀어서 뿌듯해서....^^ 구현문제처럼 차근차근 문제를 따라가면 되는 문제다.

그래프에 땅(1), 바다(0) 좌표가 주어진다. 상하좌우로 인접한 땅을 하나의 섬으로 친다. 각 섬에서 상하좌우 중 한 방향으로만 직진하여 바다 위에 다른 섬으로 가는 다리를 만들 수 있는데 다리의 최소 길이는 2이다.

무방향 그래프니 크루스칼 알고리즘을 사용하여 다리의 모든 경우의 수를 구하여 짧은 것만 연결해주면 된다!

섬의 좌표를 각 섬 별로 저장했으며 (섬에 따라 인덱스가 다르다) 상하좌우로 쭉 직진하며 만약 다른 섬이 등장하는 경우(섬인데 인덱스가 본인과 다른 경우) 다리의 길이가 1보다 크면 저장해주었다.

(시작 정점, 끝나는 정점이 바뀐 경우를 또 저장할 필요가 없어서 빼줬는데 어차피 서로소 알고리즘을 사용할 것이니 이 부분은 뺴줘도 될 것 같다)

주의할 점은 마지막에 모든 섬이 연결되었는지 체크해줘야 한다는 것이다. 따라서 생성된 다리 개수가 섬의 개수-1 인지 체크해줘야 한다.

골드1문제를 1시간 언저리로 안정적으로 풀어서 기쁘다.

코드

from sys import stdin
from collections import deque

input = stdin.readline

# N : Row, M : Col
N, M = map(int, input().split(" "))

graph = [list(map(int, input().split(" "))) for _ in range(N)]
islands = []

dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def find_island(sr, sc):
    temp = [(sr, sc)]
    q = deque([(sr, sc)])
    graph[sr][sc] = 2  # 방문처리
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if graph[nr][nc] == 1:
                    # 방문처리, 큐에 넣기, 섬 좌표값 저장
                    graph[nr][nc] = 2
                    q.append((nr, nc))
                    temp.append((nr, nc))

    islands.append(temp)


for r in range(N):
    for c in range(M):
        if graph[r][c] == 1:
            find_island(r, c)


def find_island_idx(r, c):
    for i in range(len(islands)):
        if (r, c) in islands[i]:
            return i


dist = []
# idx : 섬 번호
for idx in range(len(islands)):
    for r, c in islands[idx]:
        # 섬 좌표 별로 4방향으로 쭉 직진하면서 다른 섬이 있는지 체크
        for i in range(4):
            count = 0
            nr = r + dr[i]
            nc = c + dc[i]
            while 0 <= nr < N and 0 <= nc < M:
                # 바다
                if graph[nr][nc] == 0:
                    nr += dr[i]
                    nc += dc[i]
                    count += 1
                # 섬
                else:
                    other_island = find_island_idx(nr, nc)
                    if idx != other_island and count != 1:
                        if (other_island, idx, count) not in dist:
                            dist.append((idx, other_island, count))
                    break

parent = [i for i in range(len(islands))]


def find_parent(parent, n):
    if parent[n] != n:
        parent[n] = find_parent(parent, parent[n])
    return parent[n]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


bridge = 0
answer = 0
dist.sort(key=lambda x: (x[2]))
for a, b, cost in dist:
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        bridge += 1
        answer += cost

# 모든 섬이 연결되었는지 체크
if bridge != len(islands) - 1:
    print(-1)
else:
    print(answer)

최단거리

다익스트라

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화 (무한의 값 int(1e9사용)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 (그리디) : 가장 짧은 노드를 빠르게 찾을 수 있도록 힙 (heapq) 자료구조 사용
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3,4번 과정 반복

[골드4. 백준 1504 특정한 최단 경로] (https://www.acmicpc.net/problem/1504)

풀이

40분정도 걸려서 풀었다. 아이디어를 고민하는데 20분 구현하는데 20분정도 걸린 것 같다.

문제를 살펴보면 일반적인 최단 경로 문제와 비슷하나, 특이점이 하나 있다. 특정한 두 정점(v1, v2)을 반드시 지나가야 한다는 것이다.

따라서 고려해야 하는 경우는 2가지다.

1. 1 -> v1 -> v2 -> N
2. 1 -> v2 -> v1 -> N

따라서 각각 1, v1, v2에서 시작하는 최단 거리 테이블이 총 3개 필요하다.

더해서 최솟값을 출력해주면 된다. 만약 불가능한 경우 -1을 출력

코드

from sys import stdin
import heapq

input = stdin.readline

N, E = map(int, input().split(" "))

# 노드
graph = [[] for _ in range(N + 1)]
for _ in range(E):
    a, b, c = map(int, input().split(" "))
    graph[a].append((b, c))
    graph[b].append((a, c))

v1, v2 = map(int, input().split(" "))


def dijkstr(start, distance):
    q = []
    distance[start] = 0
    heapq.heappush(q, (0, start))  # 비용, 노드

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            next_node, next_node_cost = i
            cost = dist + next_node_cost
            if distance[next_node] > cost:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))


# 1번 정점에서 시작하는 거리 그래프
distance1 = [int(1e9) for _ in range(N + 1)]
dijkstr(1, distance1)

# v1번 정점에서 시작하는 거리 그래프
distanceV1 = [int(1e9) for _ in range(N + 1)]
dijkstr(v1, distanceV1)

# v2번 정점에서 시작하는 거리 그래프
distanceV2 = [int(1e9) for _ in range(N + 1)]
dijkstr(v2, distanceV2)

answer = 0
# 1->v1->v2->N
if (
    distance1[v1] != int(1e9)
    and distanceV1[v2] != int(1e9)
    and distanceV2[N] != int(1e9)
):
    answer = distance1[v1] + distanceV1[v2] + distanceV2[N]

# 1->v2->v1->N
if (
    distance1[v2] != int(1e9)
    and distanceV2[v1] != int(1e9)
    and distanceV1[N] != int(1e9)
):
    answer = min(answer, distance1[v2] + distanceV2[v1] + distanceV1[N])

if answer == 0:
    print(-1)
else:
    print(answer)

[골드1. 백준 16118 달빛 여우] (https://www.acmicpc.net/problem/16118)

풀이

경우를 나눠서 최단경로를 체크해야한단 점에서 어제 푼 [골드3. 백준 2206 벽 부수고 이동하기] (https://www.acmicpc.net/problem/2206) 문제와 비슷하다. 비슷한데 왜 캐치를 못하고... 예제를 이해 못했는지 조금 슬프다!!

여우는 일반적인 다익스트라 방식으로 풀면 된다.

늑대가 문제인데, 늑대는 빠르게 / 느리게를 번갈아가며 이동한다. 따라서 소숫점이 나오지 않도록 간선의 가중치를 다 x2해주고 시작했다.

핵심 포인트는 늑대가 특정 좌표까지 빠르게 도착했는지 / 느리게 도착했는지를 나눠서 봐야 한다.

따라서 빠르게 도착했는지의 여부를 arrive_fast 변수로 힙에 같이 넣어주었고, 빠르게 도착했을 때의 거리값은 distance[node][0]에 느리게 도착했을 때의 거리값은 distance[node][1]에 넣어주었다.

엄청나게 헷갈린다!!!! 비교해야되는 데이터가 헷갈려서 예시를 자세히 적어둔다.

이전 데이터와 비교해서 업데이트해줄 때, 빠르게 도착한 경우 이제 느리게 출발해야된다. 따라서 거리값은 x2해준다. 그리고 비교해야 될 데이터는 현재 선택한 경로cost와 다음 도착할 거리값(느리게 출발했으니 -> 다음 노드 기준 느리게 도착했을 때)을 갱신해줘야 하므로 distance[next_node][1] 를 비교한다.

코드

from sys import stdin
import heapq

input = stdin.readline

# N : 정점, M : 간선
N, M = map(int, input().split(" "))

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b, d = map(int, input().split(" "))
    graph[a].append((b, d * 2))
    graph[b].append((a, d * 2))

distance_fox = [int(1e9) for _ in range(N + 1)]
distance_wolf = [[int(1e9)] * 2 for _ in range(N + 1)]


def dijkstra_fox(start):
    q = []
    heapq.heappush(q, (0, start))
    distance_fox[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance_fox[now] < dist:
            continue

        for i in graph[now]:
            next_node, next_node_cost = i
            cost = dist + next_node_cost
            if distance_fox[next_node] > cost:
                distance_fox[next_node] = cost
                heapq.heappush(q, (cost, next_node))


def dijkstra_wolf(start):
    q = []
    # 빨리 도착했는지(True): distance[0], 느리게 도착했는지(False) : distance[1]
    heapq.heappush(q, (0, start, False))
    distance_wolf[start][1] = 0
    while q:
        dist, now, arrive_fast = heapq.heappop(q)

        if arrive_fast and distance_wolf[now][0] < dist:
            continue
        elif not arrive_fast and distance_wolf[now][1] < dist:
            continue

        for i in graph[now]:
            next_node, next_node_cost = i
            # 빠르게 도착했으니, 느리게 출발
            if arrive_fast:
                next_node_cost *= 2
                cost = dist + next_node_cost
                if distance_wolf[next_node][1] > cost:
                    distance_wolf[next_node][1] = cost
                    heapq.heappush(q, (cost, next_node, False))
            else:
                next_node_cost //= 2
                cost = dist + next_node_cost
                if distance_wolf[next_node][0] > cost:
                    distance_wolf[next_node][0] = cost
                    heapq.heappush(q, (cost, next_node, True))


dijkstra_fox(1)
dijkstra_wolf(1)

answer = 0
for i in range(2, N + 1):
    if distance_fox[i] < min(distance_wolf[i][0], distance_wolf[i][1]):
        answer += 1

print(answer)

DP

이미 계산된 결과는 메모리 영역에 저장하여 다시 계산하지 않도록 하는 방식 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 사용한다. 동일한 작은 문제를 반복적으로 해결해야 할 때 사용한다.

메모이제이션

DP를 구현하는 방법 중 하나로 한번 계산한 결과를 메모리 공간에 메모하는 기법

• 같은 문제를 호출하면 메모했던 결과를 그대로 가져옴 (다시 계산X)
• 값을 기록해놓는다는 점에서 캐싱이라고도 함

📌 [골드3. 백준 1520 내리막길] (https://www.acmicpc.net/problem/1520)

DP는 문제 푸는 방법이 보일 때까지 반복 또 반복하자!!!!!!

풀이

DFS, BFS 뭘 해도 시간초과가 안 잡혀서 해설을 찾아봤다. DP를 적용시켜야 하는 문제였다.

참고한 블로그

이 문제의 경우 시작, 도착점이 아닌 임의의 지점(a,b)에서 도착지점 (m-1, n-1) 까지 가는 경우의 수가 구해지면, 그 이전의 어떤 경로로 (a,b)에 도착하기만 하면 그 때부터의 경우의 수는 다시 구할 필요가 없다. 즉, 도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같아진다.

어떻게 메모이제이션을 할까 -> 시작 지점에서 출발해서 DP 테이블이 갱신되지 않은 곳(X)을 만난다면, 해당 지점(X)부터 도착 지점까지 갈 수 있는 경로의 수를 그곳에 업데이트. X지점의 DP 테이블이 이미 갱신되어 있다면 그 곳이 위에서 말한 부분 최적해가 되므로 그 값을 그대로 전체 정답에 더해주면 된다.

코드

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

# M : row, N : col
M, N = map(int, input().split(" "))

graph = [list(map(int, input().split(" "))) for _ in range(M)]

dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

dp = [[-1 for _ in range(N)] for _ in range(M)]

# dfs(r, c) -> (r, c)에서 출발하여 (N-1, M-1)까지 가는 경우의 수
def dfs(r, c):
    # 재귀함수 종료조건
    if r == M - 1 and c == N - 1:
        return 1

    # 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 리턴받아
    # 그 경우는 다시 탐색하지 않음
    if dp[r][c] != -1:
        return dp[r][c]

    dp[r][c] = 0
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < M and 0 <= nc < N:
            if graph[nr][nc] < graph[r][c]:
                dp[r][c] += dfs(nr, nc)

    return dp[r][c]

print(dfs(0, 0))

[골드4. 백준 16234 인구 이동] (https://www.acmicpc.net/problem/16234)

풀이

문제에서 나오는 대로 구현하면 되는 문제다. 그래프(BFS) + 구현 느낌?

상하좌우를 살펴보면서 좌표간의 차이가 L 이상 R 이하인 경우 연합 move_pos에 추가하고 방문처리를 해주었다.

한번이라도 인구이동이 발생했으면 is_move_ocurred를 True로 바꿔 다시 전체 BFS를 돌리도록 구현했다.

한번도 인구이동이 발생하지 않을 수 있으므로 인구이동이 발생한 날짜day의 기본값은 0으로 설정했다.

문제 조건 잘 읽고 이해한 뒤 예제 잘 적용시켜보고 구현했더니 30~40분정도 걸려서 기분이 좋았다.

코드

from sys import stdin
from collections import deque

input = stdin.readline

N, L, R = map(int, input().split(" "))
graph = [list(map(int, input().split(" "))) for _ in range(N)]

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


# 인구이동 발생 여부 return (발생시 True)
def bfs(sr, sc, visit):
    global is_move_ocurred
    move_pos = [(sr, sc)]
    total_ppl = graph[sr][sc]
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N and not visit[nr][nc]:
                if L <= abs(graph[r][c] - graph[nr][nc]) <= R:
                    move_pos.append((nr, nc))
                    total_ppl += graph[nr][nc]
                    q.append((nr, nc))
                    visit[nr][nc] = True

    if len(move_pos) != 1:
        is_move_ocurred = True
        num = total_ppl // len(move_pos)
        for r, c in move_pos:
            graph[r][c] = num


day = 0
is_move_ocurred = False
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
    for c in range(N):
        if not visit[r][c]:
            bfs(r, c, visit)

if is_move_ocurred:
    day = 1

while is_move_ocurred:
    is_move_ocurred = False
    visit = [[False for _ in range(N)] for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if not visit[r][c]:
                bfs(r, c, visit)

    if is_move_ocurred:
        day += 1

print(day)

[DFS 문제 추천 블로그] (https://coding-grandpa.tistory.com/122) 위 블로그를 보고 DFS 문제를 좀 풀어봐야겠다.

그래프 탐색 문제의 경우

1. DFS or BFS 둘 다 무관한 경우
2. DFS를 사용하는것이 압도적으로 편한 경우
3. BFS를 사용하는것이 압도적으로 편한 경우

정도가 있겠다.

DFS, BFS를 선택할 때 어떤 기준으로?

본인이 더 익숙한 방식으로 풀어도 되는 경우가 많지만, 특정 알고리즘을 쓰는 것이 유리한 경우가 있다.

DFS 재귀, 백트래킹을 이용한 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제 (순열, 조합 등)

BFS depth(깊이)를 이용한 문제 (최단경로 등) 가중치가 같은 그래프에서 최단거리를 찾을 때

[골드3. 백준 2206 벽 부수고 이동하기] (https://www.acmicpc.net/problem/2206)

풀이 (해설참고)

현재까지 벽을 뚫은 여부만 단순히 갖고 접근하면 안된다. (이렇게 풀면 해당 좌표까지 벽을 뚫고 접근했을 때와 벽을 뚫지 않았을 때를 구분할 수 없다)

최단거리를 구하는 문제이기 때문에 BFS로 접근해서 풀면 된다. 다만 벽을 뚫었을 때의 거리와 벽을 뚫지 않았을 때의 거리를 계산해야 하므로 거리를 계산하는 배열을 3차원으로 갖고 있어야 한다.

• visit[0][row][col] : 벽을 뚫지 않고 해당 좌표까지 접근한 거리
• visit[1][row][col] : 벽을 뚫고 해당 좌표까지 접근한 거리

코드

from sys import stdin
from collections import deque

input = stdin.readline

# N : row, M : col
N, M = map(int, input().split(" "))

graph = [list(map(int, input().rstrip())) for _ in range(N)]

# 상하좌우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

visit = [[[0 for _ in range(2)] for _ in range(M)] for _ in range(N)]


def bfs(sr, sc):
    # 벽 안 부순 상태 : 0
    q = deque([(sr, sc, 0)])
    visit[sr][sc][0] = 1
    while q:
        r, c, wall = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if visit[nr][nc][wall] == 0:
                    # 벽이 아니라면 이동
                    if graph[nr][nc] == 0:
                        q.append((nr, nc, wall))
                        visit[nr][nc][wall] = visit[r][c][wall] + 1
                # 벽 아직 안 부쉈고, 벽인 경우
                if wall == 0 and graph[nr][nc] == 1:
                    # 벽 부순 상태 : 1
                    q.append((nr, nc, 1))
                    # 이전경로 + 1 저장
                    visit[nr][nc][1] = visit[r][c][wall] + 1


bfs(0, 0)
max_dist = int(1e9)
if visit[N - 1][M - 1][1] != 0:
    max_dist = min(max_dist, visit[N - 1][M - 1][1])
if visit[N - 1][M - 1][0] != 0:
    max_dist = min(max_dist, visit[N - 1][M - 1][0])

if max_dist == int(1e9):
    print(-1)
else:
    print(max_dist)

크악 오늘 뭘 했다고 하루가 다 끝났냐!! 내일 하루종일 코테만 풀어주지

deepcopy보다 slicing이 훨씬 빠르다

# 1차원 리스트 복사
a= [1, 2, 3]
b = arr[:]

# 2차원 리스트 복사
a = [[1, 2], [3, 4]]
b = [item[:] for item in a]

그래프

[골드4. 백준 1753 최단경로] (https://www.acmicpc.net/problem/1753)

풀이

정점과 정점 사이의 간선이 여러개일 수 있어 한번 더 처리해줘야 하는 문제이다. 시작 정점(K)이 주어지므로 다익스트라 알고리즘을 사용하면 된다.

최대 정점의 개수가 많아 매번 정점을 다 훑으면서 최소 거리 간선만 저장하는 것은 비효율적이어 딕셔너리를 사용했다.

만약 딕셔너리에 (시작정점, 도착정점) 값이 존재한다면 그 값과 입력받은 간선 값 중 작은 것을 저장한다. get 메서드를 사용하여 만약 한번도 입력받은 적이 없다면 int(1e9)를 기본값으로 불러오게 설정했다.

딕셔너리에 모든 입력값을 다 저장했다면 그래프에 값을 넣어준다. 이제 일반적인 다익스트라 방식으로 풀면 된다.

그래프[시작노드]에는 (도착노드, 가중치)가 담겨있으며, 최단거리 배열은 모두 int(1e9)로 초기화한다.

시작 노드의 거리값은 0으로 계산하며, 최단거리를 갖는 노드를 효율적으로 뽑아내기 위해 heapq를 사용한다. 힙에 (거리, 노드) 값을 넣고 만약 최단거리 배열[노드] 값보다 거리가 길다면 볼 필요 없으니 패스한다. 거리가 짧다면 연결된 노드를 모두 살펴보며 해당 노드로 가는 것이 더 유리한 경우 최단거리 배열을 업데이트하고 힙에 값을 넣어준다.

코드

from sys import stdin
import heapq

input = stdin.readline

V, E = map(int, input().split(" "))

# 시작정점의 번호
K = int(input())

# 그래프
graph = [[] for _ in range(V + 1)]

mydict = {}
for _ in range(E):
    u, v, w = map(int, input().split(" "))
    # 간선이 여러개일 수 있으니 최솟값만 저장하기
    mydict[(u, v)] = min(mydict.get((u, v), int(1e9)), w)

for key in mydict:
    s, e = key
    graph[s].append((e, mydict[key]))


# 최단거리 테이블
distance = [int(1e9) for _ in range(V + 1)]


# 다익스트라
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # (비용, 노드)로 힙에 값 넣기
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        # 최단거리 테이블을 살펴봤더니
        # 지금 길이가 더 길어서 살펴볼 필요가 없는 경우는 패스
        if distance[now] < dist:
            continue

        # 연결된 노드 살펴보기
        for i in graph[now]:
            next_node, next_node_dist = i
            cost = dist + next_node_dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))


dijkstra(K)

for i in range(1, V + 1):
    if distance[i] == int(1e9):
        print("INF")
    else:
        print(distance[i])

[골드5. 백준 10026 적록색약] (https://www.acmicpc.net/problem/10026)

풀이

BFS를 돌릴때 경우에 따라 방문해야되는 노드가 다르다. 만약 적록색약이 있는 경우, R, G를 같은 영역으로 체크한다. 따라서 BFS를 버전별로 다 만들어주었다. R, G, B, R/G 를 체크할 수 있는 BFS 함수를 만들어 풀었다.

방문처리는 visit 배열을 만들어서 처리해주었다.

코드

from sys import stdin
from collections import deque

input = stdin.readline
N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]


dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def blue_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "B" and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


def red_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "R" and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


def green_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "G" and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


def red_green_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if (graph[nr][nc] == "R" or graph[nr][nc] == "G") and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


# 적록색약 X
count = 0
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
    for c in range(N):
        if not visit[r][c]:
            if graph[r][c] == "B":
                blue_bfs(r, c, visit)
            elif graph[r][c] == "R":
                red_bfs(r, c, visit)
            else:
                green_bfs(r, c, visit)
            count += 1

print(count, end=" ")

# 적록색약 O
count = 0
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
    for c in range(N):
        if not visit[r][c]:
            if graph[r][c] == "B":
                blue_bfs(r, c, visit)
            else:
                red_green_bfs(r, c, visit)
            count += 1
print(count, end="")

[골드5. 백준 7569 토마토] (https://www.acmicpc.net/problem/7569)

풀이

3차원 그래프에서 BFS를 돌려주면 된다. 2차원과 크게 차이는 없다. 살펴봐야하는 인덱스가 하나 더 늘어났을 뿐이다.

토마토가 여러군데에 있을 수 있다는 것에 주의하자! 즉, 시작하는 좌표(토마토 위치)를 싹 다 deque에 넣고 bfs를 돌려주면 된다.

저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, : 시작하는 좌표의 길이가 3차원 배열의 크기와 같은 경우

토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다. : bfs를 돌리고 나서 graph에 0이 존재하는 경우

토마토가 익는데 걸리는 최소 날짜 : graph 내의 가장 큰 숫자 - 1

왜? : 방문처리 연산을 graph[좌표]+1로 해줬기 때문에 (시작하는 토마토의 값이 1이라서) 하루 빼줘야한다

골드로 넘어오면 확실히 고려할 것이 이것저것 생기는 느낌. 얼른 골드도 안전하게 1시간 안에 다 풀고싶다 ㅠ

코드

from sys import stdin
from collections import deque

input = stdin.readline
# M : col, N : row, H : height
M, N, H = map(int, input().split(" "))

graph = []
tomato = deque([])
for h in range(H):
    temp = []
    for r in range(N):
        data = list(map(int, input().split(" ")))
        for c in range(M):
            if data[c] == 1:
                tomato.append((h, r, c))
        temp.append(data)
    graph.append(temp)

# 6가지 방향 고려
# 3차원 기준 상하, 2차원 기준 상하좌우
dir_ = [[1, 0, 0], [-1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, 1], [0, 0, -1]]


def bfs():
    while tomato:
        h, r, c = tomato.popleft()
        for i in range(len(dir_)):
            nh = h + dir_[i][0]
            nr = r + dir_[i][1]
            nc = c + dir_[i][2]

            if 0 <= nh < H and 0 <= nr < N and 0 <= nc < M:
                # 빈 칸
                if graph[nh][nr][nc] == -1:
                    continue
                # 안 익은 토마토
                if graph[nh][nr][nc] == 0:
                    graph[nh][nr][nc] = graph[h][r][c] + 1
                    tomato.append((nh, nr, nc))


# 모든 토마토가 익어있는 상태
if len(tomato) == H * M * N:
    print(0)

else:
    bfs()

    # 만약 0이 한개라도 존재한다면 -1 출력
    # 아니면 가장 큰 값-1 출력
    max_date = -int(1e9)
    for h in range(H):
        for r in range(N):
            for c in range(M):
                if graph[h][r][c] == 0:
                    print(-1)
                    exit(0)
                max_date = max(max_date, graph[h][r][c])

    print(max_date - 1)

[실버3. 백준 2606 바이러스] (https://www.acmicpc.net/problem/2606)

풀이

BFS로 풀면 되는 문제. 그래프를 양방향 연결해준 뒤, 1번 노드에서 BFS를 돌려 연결된 경우 visit 배열을 True로 바꿔준다. 2번째 노드부터 visit 배열을 돌면서 만약 값이 참인 경우, 감염된 컴퓨터이므로 그 수를 세어주면 된다.

코드

from sys import stdin
from collections import deque

input = stdin.readline

N = int(input())
edge = int(input())

graph = [[] for _ in range(N + 1)]

for _ in range(edge):
    n1, n2 = map(int, input().split(" "))
    # 양방향 연결
    graph[n1].append(n2)
    graph[n2].append(n1)

visit = [False for _ in range(N + 1)]


def bfs(start):
    q = deque([start])
    visit[start] = True
    while q:
        node = q.popleft()
        for next_node in graph[node]:
            if not visit[next_node]:
                visit[next_node] = True
                q.append(next_node)


bfs(1)

answer = 0
for i in range(2, N + 1):
    if visit[i]:
        answer += 1

print(answer)

[실버1. 백준 2667 단지번호이어붙이기] (https://www.acmicpc.net/problem/2667)

풀이

BFS로 풀면 되는 문제. 그래프를 돌면서 상하좌우로 값이 1인 경우, 집이 있는 곳이므로 해당 구역의 크기를 체크한다. 방문 처리용 배열을 따로 두지 않고, 만약 방문한 경우 그 값을 2로 바꿔 방문처리를 체크했다.

구역의 크기를 배열로 저장한 뒤, 배열의 길이와 배열을 오름차순으로 정렬한 결과를 출력해주면 된다.

코드

from sys import stdin
from collections import deque

input = stdin.readline

N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    q = deque([(sr, sc)])
    count = 1
    graph[sr][sc] = 2  # 방문처리
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "1":
                    count += 1
                    graph[nr][nc] = 2  # 방문처리
                    q.append((nr, nc))
    return count


answer = []
for r in range(N):
    for c in range(N):
        if graph[r][c] == "1":
            answer.append(bfs(r, c))

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

for num in answer:
    print(num)

[실버4. 백준 1244 스위치 켜고 끄기] (https://www.acmicpc.net/problem/1244)

풀이

문제에 나온대로 구현해주면 된다. 인덱스를 문제와 통일시켜주기 위해 0번째 인덱스는 -1 값으로 초기화했고, 접근하지 않도록 구현했다.

남자의 경우, 입력받은 인덱스의 배수번째만 바꿔주면 된다. 여자의 경우, 입력받은 인덱스 기준으로 양쪽 대칭이 값이 같으면 바꿔주면 된다. 어디까지 같은 값을 같는지 체크하고 그 범위만큼 값을 바꿔주는 식으로 했다.

20번째 요소마다 줄바꿈을 해주고 값을 출력해줘야 하는 것에 유의!

코드

from sys import stdin

input = stdin.readline

N = int(input())
switches = [-1]
switches += list(map(int, input().split(" ")))

students = int(input())


def male(idx):
    for i in range(idx, N + 1, idx):
        if switches[i] == 0:
            switches[i] = 1
        else:
            switches[i] = 0


def female(idx):
    before = idx - 1
    after = idx + 1
    is_symmetry_exist = False
    while True:
        if 1 <= before < idx and idx < after <= N:
            if switches[before] == switches[after]:
                is_symmetry_exist = True
                before -= 1
                after += 1
            else:
                before += 1
                after -= 1
                break
        else:
            before += 1
            after -= 1
            break

    if not is_symmetry_exist:
        if switches[idx] == 0:
            switches[idx] = 1
        else:
            switches[idx] = 0
    else:
        for i in range(before, after + 1):
            if switches[i] == 0:
                switches[i] = 1
            else:
                switches[i] = 0


for _ in range(students):
    gender, idx = map(int, input().split(" "))
    if gender == 1:
        male(idx)
    else:
        female(idx)


for i in range(1, N + 1):
    if i % 20 == 1 and i != 1:
        print()
    print(switches[i], end=" ")

[실버3. 백준 1913 달팽이] (https://www.acmicpc.net/problem/1913)

풀이

문제에 나온대로 배열을 가운데서부터 빙글빙글 돌아가면 되는 문제다. 규칙을 찾아보니 다음과 같았다.

첫번째 빙글 : up right down*2 left*2 up*2 두번째 빙글 : up right*3 down*4 left*4 up*4 세번째 빙글 : up right*5 down*6 left*6 up*6 ... i번째 빙글 : up right*(1+i*2) down*(2+i*2) left*(2+i*2) up*(2+i*2)

위에서 찾은 규칙대로 몇번 빙글 돌아야하는지 구해서 계산해주면 된다.

코드

from sys import stdin

input = stdin.readline

N = int(input())

target = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]
start = N // 2
count = N // 2

x = start
y = start
num = 1


def up(count):
    global num, x, y
    for _ in range(count):
        x -= 1
        num += 1
        graph[x][y] = num


def right(count):
    global num, x, y
    for _ in range(count):
        y += 1
        num += 1
        graph[x][y] = num


def down(count):
    global num, x, y
    for _ in range(count):
        x += 1
        num += 1
        graph[x][y] = num


def left(count):
    global num, x, y
    for _ in range(count):
        y -= 1
        num += 1
        graph[x][y] = num


for i in range(count):
    graph[x][y] = num

    up(1)
    right(1 + (i * 2))
    down(1 + (i * 2) + 1)
    left(1 + (i * 2) + 1)
    up(1 + (i * 2) + 1)


target_r, target_c = 0, 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == target:
            target_r = i + 1
            target_c = j + 1
        print(graph[i][j], end=" ")
    print()

print(target_r, target_c)

[골드3. 백준 16236 아기 상어] (https://www.acmicpc.net/problem/16236)

풀이

문제에 나온대로 구현해주면 되는 문제다. 잘 구현해놓고!!! 문제를 잘못 읽은 부분이 있어서 엄청나게 헤맸다.

헤맨 포인트

1. 물고기의 크기 == 상어의 크기 -> 못 먹음!!! (지나가기만 함)
2. 물고기가 남아있어도 상어의 크기가 작아 다 못먹고 종료해야 하는 경우가 존재

위 2개를 놓쳐서 아주 2시간동안 뱅뱅 돌았다. 테스트케이스를 보고 왜 다르게 나오는지 깨닫느라 한참 걸렸다. 맞게 푼 것 같은데 안 풀릴때는 문제를 처음부터 다시 차근차근 읽어봐야겠다.

코드

from sys import stdin
from collections import deque

input = stdin.readline
N = int(input())

# 물고기의 수
fish = 0

# 상어 좌표
sharkX, sharkY = 0, 0

# 상어 크기
shark_size = 2

# 상어가 먹은 물고기의 수
eat = 0

# 그래프 입력받기
graph = []
for i in range(N):
    data = list(map(int, input().split(" ")))
    for j in range(N):
        if data[j] != 0 and data[j] != 9:
            fish += 1
        elif data[j] == 9:
            sharkX, sharkY = i, j
    graph.append(data)

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc, cnt, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = cnt
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] <= shark_size and visit[nr][nc] == 0:
                    visit[nr][nc] = visit[r][c] + 1
                    q.append((nr, nc))


def check(visit):
    fish_pos_dist = []
    for i in range(N):
        for j in range(N):
            if visit[i][j] != 0 and 1 <= graph[i][j] < shark_size:
                fish_pos_dist.append((visit[i][j], i, j))
    return fish_pos_dist


graph[sharkX][sharkY] = 0
answer = 0
while fish > 0:
    visit = [[0 for _ in range(N)] for _ in range(N)]
    bfs(sharkX, sharkY, answer, visit)
    fish_pos_dist = check(visit)

    # 물고기의 수가 남아있어도 먹을 수 있는 물고기가 없을 수 있음
    if len(fish_pos_dist) == 0:
        break
    fish_pos_dist.sort(key=lambda x: (x[0], x[1], x[2]))

    dist, x, y = fish_pos_dist[0]
    # 물고기 먹기
    eat += 1
    fish -= 1
    graph[x][y] = 0
    if shark_size == eat:
        shark_size += 1
        eat = 0
    sharkX, sharkY = x, y
    answer = dist

print(answer)

그래프

[실버1. 백준 2468 안전 영역] (https://www.acmicpc.net/problem/2468)

풀이

문제에서 힌트를 다 준 상냥한 문제다.

비가 올 수 있는 경우가 최대 100이므로 모든 경우에 대해서 안전영역을 체크해주면 된다. 안전영역은 해당 좌표 값이 비 높이h보다 큰 경우 해당되며, 상하좌우로 인접한 영역만 동일한 영역으로 고려한다. 따라서 인접한 영역을 전부 훑어야하므로 BFS방식을 사용했다.

모든 높이에 대해서 훑어봐야 하므로 입력받은 배열을 deepcopy메서드를 사용해서 복사한 뒤 사용했다.

방문여부는 따로 배열을 만들어서 관리하지 않고, 높이가 될 수 없는 값인 0으로 바꿔서 처리해줬다.

주의할 점은 문제에도 나와있지만, 모든 영역이 비에 잠기지 않을 수 있다는 것이다. 즉, 안전영역의 최솟값은 1이다.

위의 설명 그대로 구현하면 된다.

코드

from sys import stdin
from collections import deque
from copy import deepcopy

input = stdin.readline

N = int(input())

max_height = 0
graph = []
for _ in range(N):
    data = list(map(int, input().split(" ")))
    max_height = max(max_height, max(data))
    graph.append(data)

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(i, j, graph, h):
    q = deque([(i, j)])
    # 방문처리
    graph[i][j] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                # 물에 잠기지 않은 영역일때
                if graph[nr][nc] > h:
                    graph[nr][nc] = 0
                    q.append((nr, nc))


# 아무 지역도 안 잠기는 경우, 안전영역은 전체(1)
safe_area = 1
for h in range(1, 101):
    copy_graph = deepcopy(graph)
    count = 0
    for i in range(N):
        for j in range(N):
            # 물에 잠기지 않은 영역일때
            if copy_graph[i][j] > h:
                bfs(i, j, copy_graph, h)
                count += 1
    safe_area = max(count, safe_area)

print(safe_area)

[실버1. 백준 2583 영역 구하기] (https://www.acmicpc.net/problem/2583)

풀이

괜히 x,y 섞어쓰지말자... 항상 그래프 문제를 풀때는 row, col 개념으로 접근해야 안 헷갈리는 것 같다. (적어도 나는)

입력으로 주어지는 값들은 다음과 같다.

M = 최대 row N = 최대 col K = 색칠할 사각형의 범위

사각형은 왼쪽 아래 좌표(LeftRow, LeftCol) 오른쪽 위 (RightRow, RightCol) 값이 주어지는데 색칠되는 범위를 고려하면 LeftRow ~ RightRow-1, LeftCol ~ RightCol-1 범위다. 색칠해야 되는 영역을 1로 처리해준 뒤 방문하지 않은 영역(0)에 대해서 BFS를 돌리면 된다.

BFS를 돌면서 총 몇 칸인지를 count 변수에 저장했고, 그 값을 오름차순으로 출력해주면 된다.

실버 1 난이도라기엔 쉽다.

코드

from sys import stdin
from collections import deque

input = stdin.readline

M, N, K = map(int, input().split(" "))  # M : row, N : col, 사각형 개수

graph = [[0 for _ in range(N)] for _ in range(M)]


for _ in range(K):
    lc, lr, rc, rr = map(int, input().split(" "))

    for r in range(lr, rr):
        for c in range(lc, rc):
            # 색칠
            graph[r][c] = 1

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    count = 1
    q = deque([(sr, sc)])
    # 방문처리
    graph[sr][sc] = 2
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < M and 0 <= nc < N:
                # 색칠X 영역
                if graph[nr][nc] == 0:
                    # 방문처리
                    graph[nr][nc] = 2
                    count += 1
                    q.append((nr, nc))
    return count


answer = []
for r in range(M):
    for c in range(N):
        if graph[r][c] == 0:
            answer.append(bfs(r, c))

answer.sort()
print(len(answer))
print(" ".join(map(str, answer)))

[골드5. 백준 2589 보물섬] (https://www.acmicpc.net/problem/2589)

풀이

모든 육지값에 대해서 각각 BFS를 돌려서 최대경우일때를 구해아한다. 다만 이렇게 풀면 Pypy로만 통과해서 파이썬 통과하는 경우를 구글링해봤다.

육지가 가장 끝에 있는게 아니라면 (위아래/양옆에 육지가 있다면) 절대 최대거리가 나올 수 없으므로 그 경우를 빼주면 파이썬으로도 통과가 된다!

두 가지 경우를 모두 정리해두었다.

코드 (Pypy 통과)

from sys import stdin
from collections import deque

input = stdin.readline

ROW, COL = map(int, input().split(" "))

graph = [list(input().rstrip()) for _ in range(ROW)]

# 상하좌우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    visit = [[-1 for _ in range(COL)] for _ in range(ROW)]
    max_val = -int(1e9)
    q = deque([(sr, sc)])
    visit[sr][sc] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < ROW and 0 <= nc < COL:
                if graph[nr][nc] == "L" and visit[nr][nc] == -1:
                    visit[nr][nc] = visit[r][c] + 1
                    max_val = max(visit[nr][nc], max_val)
                    q.append((nr, nc))
    return max_val


answer = -int(1e9)
for r in range(ROW):
    for c in range(COL):
        if graph[r][c] == "L":
            answer = max(answer, bfs(r, c))

print(answer)

코드 (파이썬 통과!)

from sys import stdin
from collections import deque

input = stdin.readline

ROW, COL = map(int, input().split(" "))

graph = [list(input().rstrip()) for _ in range(ROW)]

# 상하좌우
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def bfs(sr, sc):
    visit = [[-1 for _ in range(COL)] for _ in range(ROW)]
    max_val = -int(1e9)
    q = deque([(sr, sc)])
    visit[sr][sc] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < ROW and 0 <= nc < COL:
                if graph[nr][nc] == "L" and visit[nr][nc] == -1:
                    visit[nr][nc] = visit[r][c] + 1
                    max_val = max(visit[nr][nc], max_val)
                    q.append((nr, nc))
    return max_val


answer = -int(1e9)
for r in range(ROW):
    for c in range(COL):
        if graph[r][c] == "L":
            # 위아래가 육지라면
            if 0 <= r - 1 < ROW and 0 <= r + 1 < ROW:
                if graph[r - 1][c] == "L" and graph[r + 1][c] == "L":
                    continue
            # 양옆이 육지라면
            if 0 <= c - 1 < COL and 0 <= c + 1 < COL:
                if graph[r][c - 1] == "L" and graph[r][c + 1] == "L":
                    continue
            answer = max(answer, bfs(r, c))

print(answer)

가장 짧은 경로를 찾는 알고리즘

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 / 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 등의 사례가 해당

다익스트라 최단 경로 알고리즘

그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

다익스트라 알고리즘의 원리

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화 (무한의 값 int(1e9사용)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 (그리디) : 가장 짧은 노드를 빠르게 찾을 수 있도록 힙 (heapq) 자료구조 사용
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3,4번 과정 반복

heapq 시간복잡도

원소가 N개일때 원소의 삽입/삭제 : O(logN)

다익스트라 알고리즘 소스코드

# 개선된 다익스트라 알고리즘

import heapq
from sys import stdin
input = stdin.readline

# 노드의 개수, 간선의 개수
n, m = map(int, input().split(" "))

# 시작 노드 번호
start = int(input())

graph = [[] for _ in range(n+1)]

# 최단 거리 테이블 초기화
distance = [int(1e9) * (n+1)]

# 모든 간선 정보 입력
for _ in range(m):
    a,b,c = map(int, input().split(" ")) # a -> b 비용 : c
    graph[a].append((b,c)) # (도착노드, 비용 순서)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # (비용, 노드). 힙은 0번째 요소를 기준으로 정렬하므로
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        # 이미 처리된 노드라면 넘어가기
        # 현재 경로가 더 비용이 커 처리해줄 필요 X
        if distance[now] < dist:
            continue

        # 현재 노드와 연결된 다른 노드 보면서 최단거리 테이블 갱신
        for i in graph[now]:
            cost = dist + i[1]
            # cost가 더 작다면 업데이트
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

# 모든 노드로 가는 최단 거리 출력
for i in range(1, n+1):
    if distance[i] == int(1e9):
        print("INF")
    else:
        print(distance[i])

플로이드 워셜 알고리즘

그래프에서 여러 개의 노드가 있을 때 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용

단계마다 최단 거리를 가지는 노드를 찾을 필요 없이, 노드의 개수가 N개일때 N번의 단계를 수행하며 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 O(N^3)의 시간복잡도를 가진다.

현재 노드(ex. k번 노드)를 제외하고, N-1개의 노드 중에서 서로 다른 노드 (A,B) 쌍을 선택한다. A -> k번 노드 -> B로 가는 비용을 확인한 뒤 최단 거리를 갱신한다.

다익스트라는 1차원 최단 경로 테이블을 가지나, 플로이드 워셜은 2차원 리스트를 통해 처리한다. (모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하므로)

플로이드 워셜 소스코드

from sys import stdin

input = stdin.readline

# 노드의 개수, 간선의 개수
n, m = map(int, input().split(" "))

# 2차원 리스트를 사용하여 그래프 초기화
graph = [[int(1e9)] * (n + 1) for _ in range(n + 1)]

# 자기 자신 -> 자기 자신 비용은 0으로 초기화
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

# 각 간선 정보 입력받기
for _ in range(m):
    # a -> b 비용 : c
    a, b, c = map(int, input().split(" "))
    graph[a][b] = c

# 노드i -> 노드k -> 노드j 거쳐가는 것과 vs 현재거리 (i->j) 중 짧은 요소로 업데이트
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 결과 출력
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] == int(1e9):
            print("INF", end=" ")
        else:
            print(graph[i][j], end=" ")
    print()

[Lv 3. 가장 먼 노드] (https://school.programmers.co.kr/learn/courses/30/lessons/49189)

풀이

다익스트라 알고리즘을 사용하여 풀면 되는 문제다. 문제 조건 상 그래프는 양방향 연결 그래프이며, 간선의 weight는 1이다.

따라서 다익스트라 알고리즘을 통해 최단 경로 테이블을 업데이트해준 뒤, 가장 거리가 긴 노드가 총 몇개인지 체크해주면 된다. (단순히 max() 함수를 쓰다간 int(1e9) 값이 최댓값이 되어버리니 주의!

코드

import heapq

def solution(n, edge):
    answer = 0

    graph = [[] for _ in range(n+1)]
    for a,b in edge:
        graph[a].append((b, 1)) 
        graph[b].append((a, 1)) 

    # 최단 경로 테이블
    distance = [int(1e9) for _ in range(n+1)]

    def dijkstra(start):
        q = []
        heapq.heappush(q, (0, start))
        distance[start] = 0

        while q:
            dist, now = heapq.heappop(q)

            if distance[now] < dist:
                continue
            # 연결된 노드 살펴보기
            for i in graph[now]:
                # 비용 업데이트
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
    dijkstra(1)
    max_dist = -int(1e9)
    for i in range(2, n+1):
        if distance[i] != int(1e9) and max_dist <= distance[i]:
            max_dist = distance[i]

    for i in range(2, n+1):
        if distance[i] == max_dist:
            answer += 1
    return answer

[Lv 3. 순위] (https://school.programmers.co.kr/learn/courses/30/lessons/49191)

풀이

2등에게 이기면 1등, n-1등에게 지면 꼴등이라는 것에 집중하면 안된다...^^ 이 문제는 플로이드 워셜로 접근해야한다. 플로이드 워셜 위에서 바로 공부해놓고 직접 문제에는 대입 못하는 거 조금 눈물난다.

a가 k에게 이기고, k가 b에게 이긴 경우, a는 b를 이긴 것이다. a가 k에게 지고, k가 b에게 진 경우, a는 b에게 진 것이다.

위 포인트에 집중해서 풀면 된다.

참고하기 좋은 풀이 (프로그래머스 다른 사람 풀이에서 가져옴)

def solution(n, results):
    total = [['?' for i in range(n)] for j in range(n)]

    for i in range(n):
        total[i][i] = 'SELF'

    for result in results:
        total[result[0]-1][result[1]-1] = 'WIN'
        total[result[1]-1][result[0]-1] = 'LOSE'

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if total[i][k] == 'WIN' and total[k][j] == 'WIN':
                    total[i][j] = 'WIN'
                elif total[i][k] == 'LOSE' and total[k][j] == 'LOSE':
                    total[i][j] = 'LOSE'

    answer = 0

    for i in total:
        if '?' not in i:
            answer += 1

    return answer

[Lv 5. 방의 개수] (https://school.programmers.co.kr/learn/courses/30/lessons/49190)