코딩/백준 (Python) 검색 결과
175 개의 검색 결과가 있습니다.
코딩/백준 (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
코딩/백준 (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
코딩/백준 (Python)

백준 11660번: 구간 합 구하기 5 (Python)

접근 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제의 제목에서 알 수 있 듯, 구간합을 이용하여 푸는 문제였습니다. arr 을 만들어 arr[i][j] 에는 (1, 1) 부터 (i, j) 까지 사각형에 들어간 수의 합을 저장해주면 됩니다. 구간 합을 빠르게 구하는 문제이기 때문에 입력이 많이 주어질 것이라고 예상하여 input 대신 sys.stdin.readline 을 사용해주었습니다. 예상대로..

2022. 9. 21. 03:17
코딩/백준 (Python)

백준 2661번: 좋은수열 (Python)

접근 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 문제였습니다. 문제에서 주어지는 N 길이의 좋은 수열 중 가장 작은 좋은 수열을 구하는 문제입니다. 이 수열은 숫자 1, 2, 3 으로만 이루어져 있으므로 첫번째 항부터 한개씩 채워가며 길이가 N 이 될 때까지 채워갑니다. 이때 숫자를 하나 채울때마다 지금까지의 수열이 좋은 수열인지 아닌지를 계속 체크해나가면서 진행하면 되고, 문제에서 가장 작은 좋은 수열을 구하라고 하였기 때문에 각 칸에 작은..

2022. 9. 19. 22:09
코딩/백준 (Python)

백준 14889번: 스타트와 링크 (Python)

접근 각 팀에 N/2명씩 나누었을 때 사람들 끼리 가지는 시너지를 계산하여 팀 사이의 능력치 차이가 가장 적도록 하는 문제이다. 예를 들어 1번 선수와 4번 선수가 같은 팀일 경우 table[1][4] 와 table[4][1]을 팀 능력치에 더해주면 된다. 처음에는 각 팀에 선수 한명씩을 배정해주고, 새로운 팀원이 들어올 때마다 기존 팀을 순환하면서 table[i][j]와 table[j][i]를 더해주는 방식으로 코드를 짰는데 시간도 오래걸릴 뿐더러 중복되는 경우를 구분하기 어려웠다. 따라서 방법을 바꾸어 첫번째 선수(아래 코드에서는 0번 선수)가 포함되는 N/2명의 선수 명단을 모두 구하고(0번 선수가 두번째 팀에 가서 순환해도 모두 기존 구한 팀 명단과 중복된다.), 각 경우에 팀이 가지는 능력치를 ..

2022. 9. 19. 21:40
반응형