분류 전체보기 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 11780번: 플로이드 2 (Python)

접근 기존에 풀었던 플로이드 기본문제와 같이 플로이드 와샬 알고리즘을 이용하여 풀 수 있다. 다만 새로운 리스트를 작성하여 직전 도시를 저장해주면 된다. 플로이드 와샬 알고리즘 설명 및 기본 문제: 2021.04.21 - [코딩/백준 (Python)] - 백준 11404번: 플로이드 (Python) 백준 11404번: 플로이드 (Python) 접근 문제 풀이에 앞서 플로이드 와샬 알고리즘이 무엇인지 공부해보았다. 이전에 풀었던 다익스트라 알고리즘이 하나의 점에서 출발했을 때 모든 정점까지의 최단 경로를 구했다면, 플로이드 ca.ramel.be 기존 문제에서 어떤 코드가 추가되었는지 코드를 보면서 설명하도록 하겠다. 코드 import sys INF = float('inf') n = int(sys.stdin..

2021. 4. 28. 21:23
코딩/백준 (Python)

백준 9019번: DSLR (Python, PyPy3)

접근 문제 접근 및 풀이까지는 쉬웠는데 시간 초과 때문에 아주 오래 시간을 잡아먹었으나, 생각지 못했던 곳에서 해결된 문제였다. 시간 문제로 인해 PyPy3으로 해결하였다. 문제에 접근 자체는 매우 간단한 BFS 알고리즘 문제였다. 주어진 수에 D, S, L, R 연산을 각각 하고, 이를 queue에 추가한다. 동시에 길이가 10,000인 dp 리스트를 작성하여 해당 수까지의 경로를 저장한다. 이 이해하기도 쉬운 해결 방법을 시간 안에 들어가기 위하여 애를 많이 썼다. 끙끙 앓으면서 시간이 들어갈 만한 부분을 지워나가기도 했지만 마지막 해결 방법은 queue 순환 부분을 bfs 함수로 만든 것이다. 예전 문제에서도 한번 이렇게 간신히 시간안에 들었던 기억이 난다. 지역 변수를 읽는 것이 전역 변수를 읽는..

2021. 4. 27. 23:16
코딩/백준 (Python)

백준 13913번: 숨바꼭질 4 (Python)

접근 이전에 풀었던 숨바꼭질 문제에서 경로를 구해주는 것이 추가된 문제이다. 숨바꼭질 문제: 2021.04.12 - [코딩/백준 (Python)] - 백준 1697번: 숨바꼭질 (Python) 백준 1697번: 숨바꼭질 (Python) 접근 이전에 풀었던 미로탐색 등 BFS의 최단경로 방문 특성을 통해 푸는 문제이다. 조금 다른 점은 기존 문제는 좌표를 기준으로 위, 아래, 왼쪽, 오른쪽을 탐색했다면, 이 문제에서는 순간이동하 ca.ramel.be 기존 숨바꼭질 문제에서 BFS 알고리즘을 이용하여 최단거리를 구하였다. 이 알고리즘은 너비 우선 탐색 방법으로써 처음 위치에서 움직일 수 있는 모든 경우를 한번씩 방문한 후, 다음 위치에서 또 이동할 수 있는 경우를 모두 방문하는 식으로 순서대로 탐색하게 된다..

2021. 4. 26. 23:28
코딩/백준 (Python)

백준 14003번: 가장 긴 증가하는 부분 수열 5 (Python)

접근 바로 직전 문제와는 다르게 수열의 크기가 매우 커져서 2중 for문을 순환하는 알고리즘은 사용할 수 없다. 이전에 풀었던 '가장 긴 증가하는 부분 수열 2' 문제는 동일하게 수열의 크기가 매우 커서 dp 수열을 이분탐색하여 갱신하는 알고리즘을 사용하였는데, 이 방법을 발전시켜 이번 문제를 풀 수 있다. 2021.04.05 - [코딩/백준 (Python)] - 백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python) 백준 12015번: 가장 긴 증가하는 부분 수열 2 (Python) 접근 가장 긴 증가하는 수열은 동적계획법에서 나왔던 문제이고, 그때도 굉장히 오래 고민했던 기억이 난다. 2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열..

2021. 4. 25. 20:57
코딩/백준 (Python)

백준 14002번: 가장 긴 증가하는 부분 수열 4 (Python)

접근 이번 문제는 입력 받는 수열의 길이가 길지 않아 전체를 다 탐색하는 dp 알고리즘을 이용하였다. dp 알고리즘으로 길이만 구하는 문제: 2021.03.28 - [코딩/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 백준 11053번: 가장 긴 증가하는 부분 수열 (Python) 접근 수열 A 0번 요소부터 i - 1번 요소 중 A[i]보다 작은 수만 탐색하면서, 해당 요소가 가지고 있는 dp값 중 최대값을 찾는다. dp[i]에 해당 최대값보다 1 큰 값을 입력해주고 다음 수로 넘어가 계산 ca.ramel.be 이전 문제와는 다르게 해당 수열을 구해야 한다는 점이 다르다. 따라서 dp에 부분 수열의 길이만 저장하는 것이 아닌, 해당 길이의 부분 수열을 같이 ..

2021. 4. 25. 19:11
코딩/백준 (Python)

백준 18870번: 좌표 압축 (Python)

접근 좌표를 압축한 결과는 그 값보다 작은 '서로 다른 좌표의 개수'와 같다. 따라서 입력받은 좌표들을 set으로 바꾸어 중복을 제거해주고 정렬해주면 해당 좌표가 몇번째로 작은 좌표인지, 즉 해당 좌표보다 작은 좌표가 몇개인지를 확인할 수 있다. 인덱스를 딕셔너리 형태로 저장해주고, 각 좌표에 따라 불러옴으로써 문제를 해결할 수 있다. 코드 import sys n = int(sys.stdin.readline()) points = list(map(int, sys.stdin.readline().split())) points2 = list(sorted(set(points))) dic = {points2[i]: i for i in range(len(points2))} print(*[dic[i] for i in ..

2021. 4. 25. 18:40
반응형