[BOJ] 2631번: 줄세우기 (LIS) / LIS 알고리즘 문제

LIS 유형 암기 !! (LCS랑 다름 주의) 문제 링크https://www.acmicpc.net/problem/2631 완전 똑같은 문제 유형12015번: https://www.acmicpc.net/problem/1201512738번: https://www.acmicpc.net/problem/127382352번: https://www.acmicpc.net/problem/235214003번: https://www.acmicpc.net/problem/14003 TILLIS(Longest Increasing Subsequence)는 언제 사용하면 좋을까?배열의 일부 원소를 유지하면서 순서를 정렬해야 할 때최소한의 이동, 제거, 삽입을 통해 정렬된 부분 수열을 만들 때데이터를 정렬된 상태로 유지하는 최적의 방..

• format_list_bulleted Algorithm/BOJ
• · 2025. 3. 20.
• textsms

[BOJ] 1967번: 트리의 지름 (DFS)

트리 지름 구하는 알고리즘은 정해져 있음 :: 그냥 외우기 !!!!!(( 한 번 더 하기 )) 코드 링크https://www.acmicpc.net/problem/1967 [ 비슷한 문제 ]https://www.acmicpc.net/problem/1167  TIL트리의 지름을 구하는 방법 중 가장 널리 사용되는 방법은 DFS(깊이 우선 탐색)를 두 번 수행하는 방식선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다트리에서 임의의 정점 x를 잡는다.정점 x에서 가장 먼 정점 y를 찾는다.정점 y에서 가장 먼 정점 z를 찾는다.트리의 지름은 정점 y와 정점 z를 연결하는 경로다.즉, 정리하면임의의 노드(보통 루트 노드인 1번)에서 가장 먼 노드를 찾는다.이 노드를 시작점으로 다시 DFS를 수행하여 가장 ..

• format_list_bulleted Algorithm/BOJ
• · 2025. 3. 19.
• textsms

[BOJ] 2573번: 빙산 (BFS/DFS)

문제 링크https://www.acmicpc.net/problem/2573    TILBFS가 DFS보다 빠르다 !!!! >> 시간 초과날 때, BFS로 풀면 풀림실제로 이 문제의 경우, 똑같은 로직인데 BFS로 하면 통과, DFS로 하면 시간 초과 발생DFS의 경우, pypy3로 제출하면 성공 (recursionlimit을 10**4로 해야 메모리초과 발생 안함)동시성 잘 체크하기동시에 발생해야 하는 일인지 vs. 순차적으로 앞에서부터 발생해야하는 일인지이 문제의 경우, 1년이 지난 뒤 빙하가 녹을 때 동시에 녹아야했음!!따라서 melt라는 배열 따로 생성list끼리의 그냥 연산은 안됨 (ice -= melt 를 시도했으나 리스트끼리 뺄셈 실패) Tip음수값이 저장되지 않도록 하기 위해 쓸 수 있는 팁..

• format_list_bulleted Algorithm/BOJ
• · 2025. 3. 18.
• textsms

[BOJ] 1926번: 그림 (DFS)

문제 링크https://www.acmicpc.net/problem/1926   TILif 0nyn and 0nxm and grid[ny][nx] == 1 and not visited[ny][nx]: stack.append((ny,nx)) visited[ny][nx] = Truestack안에 추가하는 부분에도 visited 처리 필수!!!!!! >> 그렇지 않으면 stack에는 들어갔지만 아직 처리되지 못한 좌표들이 중복 처리됨Python ValueError빈리스트에서 max 값을 찾는것과 같이 처리할 수 없는 매개값이 넘어왔을 때 발생따라서 위와 같이 dfs 한 것 중에서 최대값 찾는 문제에서는 빈 리스트를 처리하는 코드 필수 print(max(picture) if cnt != 0 else 0)  >> ..

• format_list_bulleted Algorithm/BOJ
• · 2025. 3. 18.
• textsms

[BOJ] 4485번: 녹색 옷 입은 애가 젤다지?

문제 링크https://www.acmicpc.net/problem/4485   TIL다익스트라 알고리즘최단 거리, 최소값 찾는 알고리즘이지만 "각 노드별 현재 최소값을 저장"하고 있다는 점이 특징현재 계산한 값이 기존 저장된 최소값보다 크거나 같다면 heappush 안함 (고려하지 않게 된다는 뜻)같아도 안됨. 무조건 더 작은 값만 !! 여기서 중요한 것은, 알고리즘이 '최단 경로의 길이'를 찾는 것이 목적이라면, 경로의 수나 경로 잔체는 중요하지 않음그러나, 모든 가능한 최단 경로를 기록하고자 한다면, 같은 길이의 경로도 갱신하고 저장해야 할 필요있음따라서 매 경로마다 최소값 비교를 하게 되고, 그 여부에 따라 push 여부가 결정되므로 visited check도 따로 안해도 됨 그래프의 여러 열 입력..

• format_list_bulleted Algorithm/BOJ
• · 2025. 3. 13.
• textsms

[BOJ] 16234번: 인구 이동

> 문제 링크https://www.acmicpc.net/problem/16234  TIL같은 코드 시간초과에 대해while 문을 메인 함수에 그대로 사용하면 시간 초과함수를 빼서 재귀 or while 함수 따로 빼면 통과파이썬은 지역변수 접근이 전역 변수 접근보다 훨씬 빠르게 이루어지기 때문참고https://www.acmicpc.net/board/view/149122https://www.acmicpc.net/board/view/86503추가적으로 이 문제에선 set()을 사용하는 게 조금 더 빨랐음아무래도 리셋을 많이 해야하고, open된 걸 다시 확인해야했어서 그런듯같은 날에 처리한 것들을 구분하는 방법으로 참고할 만한 코드https://www.acmicpc.net/source/63235749시간 1등..

• format_list_bulleted Algorithm/BOJ
• · 2025. 3. 13.
• textsms