[BOJ] 15989, 15988번: 1, 2, 3 더하기 4 (DP)

((외우기))문제 링크https://www.acmicpc.net/problem/15989   TIL1+2+1, 2+1+1 이런 건 이미 1+1+2로 포함되므로 중복즉, "오름차순으로만 조합"하면 중복을 피할 수 있음이런 식으로 조합만을 계산할 때, 오름차순 생각하기 !!!!! (특히 조합의 원소가 정해져있을때)dp[0]을 지정하는 것이 낯설지만 기억하기 !! 뭔가 dp[1]은 1인 경우에 대해서 나타내기 때문에 0은 범위에 없어서 지정하는 것이 어색그치만 base로 필요한 경우가 많기에 생각해주기 이런 식으로 조합의 원소가 정해져 있는 경우bottom - up 방식for num in [1, 2, 3]:  # 가능한 숫자 오름차순으로    for i in range(num, 10001):  # num 이상..

• format_list_bulleted Algorithm/BOJ
• · 2025. 4. 1.
• textsms

[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] 1806번: 부분합 (투포인터/슬라이딩 윈도우)

문제 링크https://www.acmicpc.net/problem/1806   TIL주어진 범위의 숫자가 매우 크기 때문에 (100,000) 시간 효울성 문제 >> Two pointer 혹은 슬라이딩 윈도으탈출 구문은 right의 범위만으로 충분 코드 구조 상 left가 right보다 커질 수 없음누적합 문제의 경우, 처음 합은 한 개로 설정하고 cnt 도 1로 초기화 (nums[left], cnt =1)코드는 "="을 붙이냐 아니냐 하나로 큰 차이 발생 !!!!!! 꼭 신경쓰기while문 안에서 index의 변경 뒤에 적용이 있는 경우, index 범위 항상 신경쓰기while nums[left] 위 처럼 무조건 한 번 더 신경쓰기 문제에서 리스트의 순서가 중요하기 때문에, 한 쪽 방향에서 시작하는 투 ..

• format_list_bulleted 카테고리 없음
• · 2025. 3. 21.
• textsms