Door

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

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

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

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

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 비슷한 문제로 강의실이 있었습니다. 2022.07.13 - [알고리즘 공부] - [백준 11000번] 강의실 배정(파이썬) [백준 11000번] 강의실 배정(파이썬) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si..

알고리즘 공부 2022. 7. 24. 22:49

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