코딩 검색 결과
271 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 2193: 이친수 (Python)

접근 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이친수란 0과 1로만 이루어진 숫자 중 문제에서 주어진 조건들을 만족하는 수이다. N자리 이친수의 개수를 구하기 위해서는 1~N 까지 i자리 이친수의 개수를 구하는 부분 문제들을 풀어야 한다. 이친수를 0으로 끝나는 수와 1로 끝나는 수 두가지로 구분하여 개수를 갱신한다. 0으로 끝나는 i자리 이친수의 경우, i - 1자리 이친수에 아무 조건 없이 0을 추가로 붙여 i자리 이친수를..

2023. 4. 15. 00:01
코딩/백준 (Python)

백준 2294: 동전2 (Python)

접근 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 전형적인 DP 문제여서 점화식을 파악하는 과정이 중요했다. 이전 단계인 2293번 '동전 1' 문제를 풀고오면 조금 수월하게 접근할 수 있는것 같다. 합이 K 일 때, 사용한 동전의 최소 개수를 구하기 위하여, 합이 i 일 때 사용한 최소 동전의 개수를 구하는 작은 문제로 쪼개었다. DP 배열을 K + 1 의 길이로 생성하고, DP[i]의 의미를 합이 i 일 때..

2023. 4. 14. 23:41
코딩/백준 (Python)

백준 2458: 키 순서 (Python, PyPy)

접근 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플로이드-와샬 문제라고 알고 풀었는데 아무리 봐도 dfs 로 푸는게 빠른 문제였다. 플로이드-와샬 알고리즘을 이용해서는 속도가 느려 pypy 컴파일러로만 통과할 수 있었고, dfs 를 이용해서는 python 컴파일러로도 충분히 시간 안에 들어올 수 있었다. 플로이드-와샬 알고리즘을 이용하면 각 노드에서 다른 노드로 이동할 수 있는 최단거리를 구할 수 있다. 키의 순서를 그래프의 화살표라고 가정..

2022. 9. 23. 23:28
코딩/백준 (JAVA)

백준 16118번: 달빛 여우 (Python)

접근 https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 다익스트라 알고리즘에 조금 양념을 첨가한 문제였던 것 같습니다. 오솔길들이 있고 달빛 여우는 목적지까지 일반적인 다익스트라 알고리즘을 통해 최단거리로 이동하여 목적지에 도달합니다. 반면 달빛 늑대는 처음에는 2배의 속도, 그리고 그다음에는 절반의 속도로 번갈아가며 오솔길을 통과합니다. 이때 속도가 2배가 된다는 것은 걸리는 시간이 절반..

2022. 9. 23. 20:25
코딩/백준 (Python)

백준 2616번: 소형기관차 (Python)

접근 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 누적합 문제인 것은 눈치 챘는데 재귀로 풀고나서 시간 초과 발생한 후에서야 dp 문제인 것을 깨달았습니다. 일단 연속된 객차를 끌 수 있기 때문에 누적합 배열을 만들어 길이가 L 인 객차의 승객 수를 한번의 계산으로 구할 수 있도록 계산해줍니다. 여기까지는 기본적인 누적합 문제와 같습니다. dp 를 dp[N + 1][4] 로 초기화하고 dp[i][j] 에 i 번째 객차까지 j 개의 소형..

2022. 9. 21. 23:27
코딩/백준 (Python)

백준 3020번: 개똥벌레 (Python)

접근 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 누적합을 이용해 높이 i 이상 석순의 개수, i 이상의 종유석의 개수를 저장해줍니다. 이 때, 종유석은 위서부터 아래로 내려온다는 점을 주의하여 풀어주면 문제를 해겷할 수 있습니다. 코드 import sys input = sys.stdin.readline N, H = map(int, input().split(" ")) down = [0] * (H + 1) up = [0] * (H + 1) min..

2022. 9. 21. 22:06
반응형