Door

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/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제를 처음 읽고 당황했던 것. '궁수는 어디다가 배치하지??' 입력값은 빈칸 or 적이라서 궁수는 어디다가 배치하나 했더니 격자아래에 궁수가 배치되었다는 전제. 구현할 걸 순서대로 나열하면 이렇습니다. 1. 궁수 위치 -->combination으로 나타냈습니다. 이렇게하면 시간초과 뜰 것 같았는데 질문하기의 코드들을 참고해보니 combination써도 되겠다 싶었습니다. 2. 궁수가 적을 맞추기 -->BF..

알고리즘 공부 2022. 8. 8. 12:40

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 이 문제에서 중요한 포인트는 '어떻게 괄호를 묶는가'라는 부분. 이 부분이 상당히 난감했습니다. '아니....모든 괄호를 묶는 경우를 다 생각해야하는데 이걸 어떻게 묶냐고.... 묶을 때 각각의 데이터를 어떻게 저장하지? 이 부분이 도저히 생각이 안나서 구글링의 도움을 받았습니다. 제가 구글링을 통해 배운 건 "몇 번째를 묶어주는가" 하는 부분이었습니다. solve함수를 보면 try ..

알고리즘 공부 2022. 8. 2. 17:48

https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 이 문제를 처음 딱 접하면 어라???쉬운데? 라는 생각이 드실 수 있습니다. 처음에 문제를 마주할 때 생각은 토끼가 매일마다 당근을 훔쳐먹으니 매일 당근 중 최대를 찾아 먹고 튀는 걸로 계산할 수 있겠다는 생각입니다. 그런데, 이 문제는 그렇게 풀면 큰 코 다칩니다. 저런 아이디어를 코드화해서 예제1을 입력하면 어라? 왜 6이 나오지?? 예제1 출력은..

알고리즘 공부 2022. 7. 19. 12:00

https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 이 문제는 유사한 문제가 하나있는데요 2022.07.07 - [알고리즘 공부] - [백준 12919번] A와 B_2 (파이썬) [백준 12919번] A와 B_2 (파이썬) https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자),..

알고리즘 공부 2022. 7. 19. 09:16

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 약 2주정도 고민했으나 도저히 안풀려서 결국 구글링을 했습니다. 제가 처음 잡았던 아이디어와 가장 유사한 것을 기준으로 코드를 참고했습니다. 우선, 그림으로 그려본 것입니다. 참고로 문제에서 주어진 트리는 이진트리가 아니지만 이해를 돕기 위해 이진트리로 그렸습니다. 저는 맨 위의 부모트리에서 아래로 차근차근 내려가는 방식을 구했습니다. 편의상 왼쪽 오른쪽 경로를 나눴는데, 이건..

알고리즘 공부 2022. 7. 18. 15:47