Door

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

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 우선, 이 문제를 풀 때 양수,음수를 따로따로 받아줘야합니다. '그냥 리스트에 한번에 담으면 안되나요?' 그렇게 담으면 묶을 때 많이 불편해집니다. 만약에 -5 -3 0 0 0 0 0 1 2 3 4 이렇게 리스트가 주어져있다고 할 때 묶는 게 좀 많이 남감하겠죠? 그러니 양수 음수를 따로 받아주고 0의 갯수는 따로 저장해줍니다. 그 다음 절대값을 기준으로 정렬해줍니다. 양수는 sort(rever..

알고리즘 공부 2022. 7. 17. 20:58

https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 이 문제는 어떻게하면 화살을 적게 쓰고 풍선을 다 터트릴 수 있는가를 묻고 있습니다. 이 문제는 정렬을 절대 쓰면 안 됩니다. 화살의 조건을 보면 정렬을 잘못쓰면 문제의 상당부분이 틀어저버리죠. 정답 코드에 앞서, 제가 처음 풀었던 오답코드를 보겠습니다. #백준 11509번 풍선 맞추기 N=int(input()) ballons=list(map(int,input().split())) answer=1 now=ballons[0] for i in range..

알고리즘 공부 2022. 7. 17. 17:27

https://www.acmicpc.net/problem/21315 21315번: 카드 섞기 마술사 영재는 카드 더미를 이용한 마술을 개발하였다. 카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다. 영재는 마술을 www.acmicpc.net 처음에 문제를 읽고 이게 무슨말인지 이해가 되질 않았습니다. 카드를 섞는데 K가 왜 첫번째와 두번쨰가 있지? 이 문제를 다시 분해해보면 1. K 하나를 뽑아서 카드를 섞음 2. 근데 그걸 2번 한다. 3. 입력값은 카드를 그 2번 섞은 결과값이다. 이 문제에서 구현해줄 것은 크게 두 개로 나눴습니다. 1. K의 경우의 수 -->일반적으로 순열,조합을 떠올리기 쉽습니다. 하지만 이 경우에는 '모든 경우..

알고리즘 공부 2022. 7. 13. 11:05

https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 이 문제는 처음 문제를 읽다가 이게 뭔소리야? 하면서 이해를 못했던 문제. 1번 예시에서 최대길이를 2라고 출력했습니다. 어라? 삼각수열은 분명 3개가 들어가야하니깐 최소 3이 되어야할텐데. 이게 뭐지? 구글링해서 뒤지다가 배열이 2보다 큰데 삼각수열이 0이라면 저렇게 받아도 되는 걸 알게되었습니다. 이 문제에서 오랫동안 헤..

알고리즘 공부 2022. 7. 8. 16:41

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 이 문제를 처음 보고 오만가지 생각을 다 했습니다. 최대 K번만큼 원숭이가 말처럼 움직인다라... 그럼 원숭이가 움직일 때마다 있는 지점에서 상하좌우 이동+말이동 이걸 다 봐야하나? 그럼 K번만큼 움직이는 건 어떻게 구하지?? 시간초과 엄청날텐데... 문제의 접근조차 하지못해서 상당히 애를 먹었다가 이 문제에서 힌트를 얻었습니다. 2022.06.30 - [알고리즘 공부] - [백준..

알고리즘 공부 2022. 7. 6. 15:41