[BOJ] 6087번: 레이저 통신

(( 한 번 더 풀어보기 )) 문제 링크https://www.acmicpc.net/problem/6087  TIL[ 다익스트라 알고리즘 ]다익스트라 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.단, 모든 간선의 가중치는 0 이상이어야 합니다.visited 배열이 따로 필요하지 않음 !!!! >> 대신 최단거리 저장할 배열 필요 (dijk)우리가 다익스트라에서 보통 사용하는 우선순위 큐(min-heap) 기반 구현에서는, 이미 더 짧은 거리로 방문한 적이 있는 노드는 스킵되므로, 별도의 visited 배열이 없어도 무방if current_dist > distance[current_node]: continue 이게 가능한 이유는:우선순위 큐..

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

[BOJ] 2110번: 공유기 설치 (Aggressive cows) (이분탐색, BST)

문제 링크https://www.acmicpc.net/problem/2110( 한국어 번역이 이상해서 영어 원문 보는 걸 추천)원어 기준으로 문제를 품. 한글 버전과는 아래와 같이 대응됨.공유기 > 소집 > 마구간  TIL일단 정렬이 기본배치하는 모든 소 사이의 거리를 최대화하기 위해선 정중앙에 배치할 수록 유리 (그래야지 딱 절반만, 안그러면 최대 거리 감소)따라서 이분 탐색이 최적 !!!!거리 d에 대해: "소들을 최소 거리 d 이상으로 배치할 수 있는가?"를 판단하는 결정 문제를 정의가능한 거리 범위 [1, max(stalls) - min(stalls)]에서 이진 탐색으로 가능한 최대 d를 구하기정렬 : O(N log N)각 탐색에서 O(N) 확인 → 총 O(N log(max_dist))   Code..

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

[BOJ] 15683번: 감시 (DFS+백트래킹)

문제 링크https://www.acmicpc.net/problem/15683   TILDFS(깊이 우선 탐색)를 활용하겠다고 생각하는 사고 과정1️⃣ 문제의 핵심 파악CCTV가 감시하는 방향을 설정하고, 최적의 감시 영역을 찾는 문제다.✅ 주어진 정보각 CCTV는 회전할 수 있으며, 유형별로 감시 가능한 방향이 다르다.감시된 영역을 계산해서 **사각지대(0의 개수)**를 최소화해야 한다.CCTV가 최대 8개이므로 모든 경우를 탐색하는 완전 탐색(Brute-force)이 가능하다.✅ 문제 유형 분석모든 CCTV에 대해 감시 방향을 설정하는 모든 경우를 고려해야 한다.CCTV의 방향을 조합할 때 완전 탐색이 필요하다.감시 범위를 적용한 후에는 다시 원래 상태로 되돌려야 한다.이는 **"상태를 저장하고 복원하..

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

[BOJ] 1253번: 좋다

문제 링크https://www.acmicpc.net/problem/1253    TIL조건을 매우 잘 봐야한다(|Ai| ≤ 1,000,000,000, Ai는 정수) >> 음수도 가능하다는 소리음수가 가능하면 -5,0,5와 같은 상황이 벌어질 수 있기에 목표 숫자의 앞 리스트 요소만 보면 큰일남이런 경우를 코테에서는 꼭 꼼꼼하게 생각해야 함조건을 생각하는 것을 뺀다면 무난한 문제투포인터와 해시맵 둘 다 사용 가능하나, 해시 맵이 시간복잡도 더 낮아서 해시 맵 사용참고: https://brynn-park.tistory.com/56> 효율성을 따지는 문제일 가능성 높음특히 범위가 100,000이 넘어간다면 무조건 시간 효율성 문제 !!! >> 무조건 O(NlogN) " data-og-host="brynn-pa..

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

[BOJ] 3273번: 두 수의 합 (two-pointer) / sliding window, hash set

문제 링크https://www.acmicpc.net/problem/3273   TIL너무 쉬운 문제는 의심해보자 >> 효율성을 따지는 문제일 가능성 높음특히 범위가 100,000이 넘어간다면 무조건 시간 효율성 문제 !!! >> 무조건 O(NlogN) 이여야함 [ 투 포인터 (Two-pointer) ]투 포인터(Two-pointer) 알고리즘은 두 개의 포인터(pointer)를 사용하여 배열이나 리스트를 탐색하는 효율적인 알고리즘이 알고리즘은 정렬된 배열에서 특정 조건을 만족하는 요소를 찾거나, 최적화 문제를 해결할 때 유용함✅ 투 포인터의 핵심 원리정렬된 배열에서 사용 !!!왜 정렬을 하는가? 투 포인터 기법의 핵심은 두 개의 포인터(left, right)를 조정하여 목표 값을 빠르게 찾는 것입니다.정..

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

[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