Door

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제는 알고리즘로직보다도 시간초과,메모리 초과와의 싸움을 해야하는게 무척이나 힘들었습니다. 이런 경로를 찾는 알고리즘은 다익스트라 알고리즘을 쓰면 쉽게 풀립니다. https://justkode.kr/algorithm/python-dijkstra Python으로 다익스트라(dijkstra) 알고리즘 구현하기 최단 경로 알고리즘은 지하철 노선도, 네비게이션 등 다방..

알고리즘 공부 2022. 8. 21. 19:10

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제는 BFS로 외부 공기를 계속 구해주면서 치즈를 제거하는 문제입니다. 2022.06.30 - [알고리즘 공부] - [백준 2573번] 빙산(파이썬) [백준 2573번] 빙산(파이썬) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진..

알고리즘 공부 2022. 8. 21. 11:52

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 처음 이 문제를 보고 '와 개 쉽네' 라고 신나게 구현했다가 예제를 통과하지 못했습니다. 처음에는 dfs로 한칸씩 이동하다가 3칸째 이동했을때 여태까지 이동한 칸 합의 최대를 구하는 줄 알았습니다. 그런데...얼라라? 부메랑을 만든 것의 총합?? x된 칸에 부메랑을 넣는다가정하면 저렇게 1,2,3의 케이스가 있습니다. 저렇게 채우면 더이상 채울 수 없으니 그때의 합을 구합니다. ..

알고리즘 공부 2022. 8. 19. 14:01

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 이 문제에서 구현할 건 크게 두 가지. 1. 막대기로 미네랄 깨기 2. 클러스터 내리기 여기서 2가 상당히 복잡합니다. 여기서 클러스터라는 게 빡셉니다. 문제를 잘 읽어보면 클러스터는 한 덩어리입니다. 그래서 미네랄 하나만 내리는 것과 비교하면 많이 복잡한 편입니다. 그림으로 예시를 구현해봤습니다. 저렇게 한 덩이가 그대로 내려와야합니다. 그리고 저 내려오는 걸 구현하는 게 상당히 난해했습니다. https://..

알고리즘 공부 2022. 8. 18. 12:27

https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 이 문제는 유사한 연구소1,연구소3 등의 문제를 예전에 풀어본 적이 있어서 체감적으로 쉬웠습니다. 구현할 건 2가지. 1. 어떤 지점에서 바이러스를 처음 둘 것인가 2. 바이러스를 어떻게 퍼트리고 최댓값을 구할 것인가 1의 경우, 저는 combination을 사용했습니다. 백트레킹도 좋긴한데 저는 이 방식이 가장 간편했습니다. 2의 경우에는 bfs를 사용했습니다. 사전에 visited라는, -1로 되어있는..

알고리즘 공부 2022. 8. 15. 19:36

https://www.acmicpc.net/problem/20327 20327번: 배열 돌리기 6 크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 www.acmicpc.net 문제 길이가 상당합니다. 이 문제에서 크게 생각할 건 2가지. 1. 어떻게 배열을 나누지? 2. 어떻게 연산하지? 저는 연산에 따라 나누는 걸 다르게 하는 쪽으로 접근했습니다. 연산은 부분이냐 배열이냐 2가지인데 이 연산에 따라서 나누는 방식이 달라져야겠다 생각했습니다. # 배열 부분요소 if k상하반전 if k==1: for a in range(2**(l-1)): for b..

알고리즘 공부 2022. 8. 15. 09:37

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 구현해줘야할 부분은 2가지. 1. 배열 돌리기 2. 배열 돌리는 거 백트레킹 구현할 2가지가 난이도가 상당히 있는 편이라 체감난이도가 높았던 문제입니다. 우선 배열을 돌리는 것부터 차근히 보겠습니다. def rotate(r,c,s): #s의 수만큼 돌린다 for ro in range(s,0,-1): s_x=r-ro s_y=c-ro #돌리는 횟수는 ro*8 p=0 r_..

알고리즘 공부 2022. 8. 11. 11:26

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 야구게임을 구현하는 문제입니다. 이 문제에서 포인트는 이렇게 됩니다. 1. 선수들 케이스 구하기 2. 선수들 순서 유지하면서 이닝넘어가기 3. 아웃~홈런 구현하기 1-->permutation으로 1~8번째의 케이스를 구해줍니다. 그 후, 각 케이스를 리스트로 만든 뒤 (permutation,combination의 결과값은 tuple이 되므로 list로 전환시켜줘야함) insert(3,0)으로 4번째타자..

알고리즘 공부 2022. 8. 9. 09:27