[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] 2579번: 계단 오르기 (DP)

(( 다시 풀기 !! ))문제 링크https://www.acmicpc.net/problem/2579   TILDP문제는 보통 DP테이블을 무조건 배열로 정의 !!!!dp[i] 를 i번째 계단까지 올라갔을 때 얻을 수 있는 최대 점수 라고 정의점화식 필수 >> 이런 식으로 적당히 dp테이블과 그냥 score를 활용 !!dp[i]는 두 가지 경우 중 최댓값을 취함 i-2 번째 계단에서 i 번째 계단으로 이동하는 경우dp[i] = dp[i-2] + score[i]i-1 번째 계단에서 i 번째 계단으로 이동하는 경우 (단, i-1 번째를 밟았으므로 i-2 번째를 건너뛰어야 함)dp[i] = dp[i-3] + score[i-1] + score[i]순차적 DP 들어가기 전에 기본값 설정이 필요함 (초기 조건)dp[..

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

[프로그래머스] 도둑질 (DP)

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42897   TIL"인접한 두 집을 털면"을 "한 집에 인접한 양쪽의 집"을 털면으로 이해함그게 아니라 "연속으로 인접한 두 집"을 털면이 맞음선형 구조이기에 처음 집과 마지막 집의 인접도에 대한 고려가 필요dp, greedy에서 경우의 수 나누는 거 항상 생각이 문제의 경우, 앞의 선택에 따라 뒤의 선택이 달라지므로 dp를 사용 [ 처음 코드 ]def solution(money): n = len(money) if n==3: return max(money) # 첫 번째 집을 터는 경우 (마지막 집 안텀) dp1 = [0]*n dp1[0],..

• format_list_bulleted Algorithm/Programmers
• · 2025. 3. 14.
• 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