Door

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/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 알고리즘을 풀 때마다 느끼지만 혼자 쉐도우 복싱 오지게 하다가 힌트를 보면 현타가 많이 옵니다...하... 우선, 저는 예시는 통과했는데 제출해보니 오답이라고 떴습니다. 그래서 방법을 어떻게 바꿀까하다가 고민을 상당히 많이 했고 힌트를 보다가 이렇게 하면 되겠구나 라는 감이 왔습니다. 첫 번째로, 크레인과 박스를 정렬해줍니다. 이건 모든 그리디 알고리즘의 기본. 대체적으로 ..

알고리즘 공부 2022. 7. 15. 13:44

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/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 이건 하나 하나 모든 경우를 다 봐야하는 완전탐색의 유형입니다. 시간이 많이 걸릴 것 같은 유형의 문제. 이 문제를 푸는데 파이썬이라서 다행이라는 생각. 파이썬은 상대적으로 자료형을 다루는 것이 C에 비하면 확실히 쉬운 편. 이 문제를 풀 때는 가로,세로 축을 다 보면서 공차도 하나하나씩 다 바꿔가면서 모든 경우를 다 따져야합니다. 길찾기 문제에 익숙한 저는 '이런 식이면 시간초과떠서 터..

알고리즘 공부 2022. 7. 12. 11:34

https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 이 문제도 그리디 알고리즘 문제입니다. 어떻게하면 최소의 비용으로 최대의 비용을 구할 수 있는지 구하는 문제. 처음 이 문제를 만났을 때 이런 점들이 어려웠습니다. 1. K개의 조를 만드는데 조를 하나씩 다 만들어? 3개의 조의 조합이 겁나 많을텐데 그걸 다 조합한다면 시간초과가 날텐데? 2. 만든다 치자. 어떻게 묶지? 범위로??아니면 다른 방법?? 그렇게 고민고민하고 구글링을 하다가 이 ..

알고리즘 공부 2022. 7. 11. 14:09

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 그리디 알고리즘에서 흔히 볼 수 있는 유형이라 꼭 풀어보고 넘어가도록 마음을 먹었습니다. 이 문제는 N개만큼 회의시간이 주어지고 어떻게 회의실을 사용해야 가장 많은 회의를 할 수 있는지가 포인트입니다. 우선 그리디알고리즘의 첫 시작. 정렬을 해줍니다. 데이터 안에 [시작,끝] 이렇게 각각을 저장합니다. 그 후에는 데이터를 정렬합니다. #백준 1931 회의실 배정 N=int(input()) time=[] for _ in range(N): S,F=map(int,input().split()) time.app..

알고리즘 공부 2022. 7. 10. 23:48

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 길찾기 문제인데 엘리베이터로 되어있는 독특한 문제. 현재 시작점이 S이고 U는 위로 가는 거 D는 아래로 가는 거 이렇게 각각 구현해주고 BFS를 구현해주면 됩니다. #백준 5014번 스타트 링크 from collections import deque F,S,G,U,D=map(int,input().split()) visited=[False]*(F+1) q=deque() q.append([S,0]) v..

알고리즘 공부 2022. 7. 9. 21:27