본문 바로가기

2025/05/21

[Python/Java] 백준 10709번: 기상캐스터
[Python/Java] 백준 10709번: 기상캐스터 https://www.acmicpc.net/problem/10709 [설명] 기본적으로 구름이 절대 올 수 없는 곳에 대해 연산을 하지 않기위해 -1로 초기화해두었다.그 다음, 구름이 처음 위치한 곳에 대해서 0으로 초기화 하고, 그 다음 동쪽으로 한 칸씩 이동해가며 다음 구름을 만나기 전까지이전 상태에 대비해서 +1씩 값을 추가하여 갱신해나갔다. 여기서, 이전 값을 확인해야하므로, 최소한 j의 인덱스를 1 이상부터 비교해야 -1 위치인 0 인덱스와 비교할 수 있기 때문에 if문 조건식을 추가했다. 단순한 구현문제. [코드]- Pythonh, w = map(int, input().split())cloud = [list(input()) for _ in range(h)]result = [[-1] * w.. CS/Algorithm 2025. 5. 21.
[Python/Java] 백준 1149번: RGB거리
[Python/Java] 백준 1149번: RGB거리 https://www.acmicpc.net/problem/1149 [풀이]각 지붕에 대해 색을 칠할 수 있으며, 빨강, 노랑, 파랑 중 최소한의 비용으로 칠하고, 동시에 좌/우에 위치한 지붕과는 색깔이 달라야 한다. 일단 위의 사진에 있는 코드처럼 완탐으로 시도해보았다. 안되더라, 시간초과 뜨더라.그래서 가지치기를 할 수 있는 방법에 대해 고민해보았다. 메모이제이션을 활용하였다. [코드]- Pythonn = int(input())color = [list(map(int, input().split())) for _ in range(n)]dp = [[0] * 3 for _ in range(n)]dp[0] = color[0][:]for i in range(1, n): dp[i][0] = min(dp.. CS/Algorithm 2025. 5. 21.
[Python] 백준 10815번: 숫자 카드
[Python] 백준 10815번: 숫자 카드 https://www.acmicpc.net/problem/10815 [풀이]n개의 카드와 m개의 카드를 모두 비교하면 n * m만큼의 비교횟수가 발생한다.최악의 경우, 50만 x 1천만 = 5조 이것을 1초당 1억회 연산 기준으로 환산하면, 5조는 500초가 걸린다.시간 제한이 2초이므로, 시간 안에 절대로 연산 불가. 때문에, 시간복잡도가 O(1)인 자료구조 set을 활용했다. (자바에서는 HashMap이나 HashSet 등을 활용하면 된다)m개의 카드를 ns의 변수에서 O(1)만큼 확인하므로, 총 시간복잡도는 O(N)이 걸릴 것으로 예상된다. 이 경우, 최악의 경우 1천만이므로, 0.1초 이내로 연산이 가능하다.ns의 카드셋에서 중복되는 경우가 없었기 때문에 가능했다. 참고로, 파이썬에서 lis.. CS/Algorithm 2025. 5. 21.
[Python] 백준 15894번: 수학은 체육과목 입니다
[Python] 백준 15894번: 수학은 체육과목 입니다 https://www.acmicpc.net/problem/15894 [풀이]둘레만 구하면 되는 문제이다. 맨 위쪽을 구하자면, 1 + (0.5 * (n - 1))왼쪽은 n, 오른쪽은 n, 아래 밑변의 길이도 n이기 때문에결과적으로는 n의 길이만큼 4번 나오게 된다. int(input())으로 입력받은 n을 4번 곱하면 결과가 나오는 간단한 문제였다. [코드]print(int(input())*4) [시간복잡도]O(N) CS/Algorithm 2025. 5. 21.

티스토리툴바