Door

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

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이 문제는 문제자체보다는 문제가 길어서 '이게 뭔소리야...' 하면서 문제를 이해하는 게 좀 걸렸습니다. (워낙 문제가 길어서) 이 문제는 구현만 잘 시켜주면 됩니다. 가로 세로 대각선 각각을 움직일 때 어떻게 움직일지 제대로 구현만 해주면 끝. # # from collections import deque # N=int(input()) # room=[list(map(int..

알고리즘 공부 2022. 8. 5. 10:54

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제를 풀 때 가장 어려웠던 부분은 사이클 구현에 대한 것입니다. DFS로 길찾기까지는 어느정도 이해가 가는데 그래서 어떻게 사이클을 만들지? 라는 고민이 들었습니다. 저는 root라는 것이 나오면 사이클이 있다고 판단하는 코드를 만들었습니다. 예를들면 1이 처음에 들어오면 root로 설정하고 이후에 1이 들어오면 사이클이 완성이 되었다고 판단하도록 만들었습니다. 그런데 이 방식은 위의 예시같은 경..

알고리즘 공부 2022. 7. 26. 11:33