[BOJ] 2138번: 전구와 스위치 (Greedy)

> 문제 링크https://www.acmicpc.net/problem/2138    TIL그리디 알고리즘이지만, 무작정 푸는 것이 아닌 경우의 수를 나눠서 각 경우의 수를 그리디 돌려야하는 문제 !! 이런 문제 유형도 있으니 항상 고려하기1 0 반전하는 쉬운 방법value = 1-value 하면 됨 ( https://taltal.tistory.com/100 참고 )혹은 XOR 연산으로 가능 (^) 혹은 NOT 연산으로 가능 (not) > 대신 bool 타입으로 바뀜시간 초과에 대해서 그냥 bfs로 짠 코드는 최대 3의 100,000번 거듭제곱이므로 시간 & 메모리 초과실제로는 메모리 초과 뜸거듭 제곱의 지수가 100이상이면 무조건 안됨 !!!! 밑수가 2여도 안됨.참고: https://ourcalc.c..

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

[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

[프로그래머스] 도넛과 막대 그래프 (2024 카카오 코테)

(( 한 번 더 보기 )) 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=python3# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr    TILIT 기업의 코테 문제는 시간 초과를 매우 많이 신경 써야함!! 실제 코테에선 모든 테스트케이스가 주어지지 않기 때문에, 꼭 주어진 범위와 시간 생각해야함엣지 케이스 신경쓰는 연습하기 !! 마찬가지로 실제 코테에선 여러 개의 테스트케이스가 주어지지 않기 때문에 고려해서 생각해야 함그래프 문제 out edge 와 in edge의 특성을 잘 사용하기두 개를 나눠서 확인..

• format_list_bulleted Algorithm/Programmers
• · 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