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/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

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 이 문제에서 구현해야할 것은 크게 2가지. 1. 지운 노드의 아래 자식 노드 전부 삭제. 2. 자식노드 판별 여부 이 문제를 처음 접할 때는 트리를 전부 구현해서 푸는 건가... 하고 생각이 들었습니다. 그래서 열심히 파이썬에서 트리를 구현한 걸 찾아봤으나 이 문제에 적용하기는 힘들었습니다. 그러다가, 이 문제의 힌트를 얻으면서 차근히 풀었습니다. 1. dfs를 이용해서 자식노드를 지운다. ..

알고리즘 공부 2022. 7. 6. 13:04

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 이 문제는 처음 문제를 쓱 읽으면 '뭐야. 문제 개쉬운데?' 라는 착각을 줍니다. 물론 예제를 푸는 정도 수준은 어렵지 않는 코드이지만 그렇게하면 시간초과가 뜰 것입니다. #백준 16932번 모양만들기 from collections import deque N,M=map(int,input().split()) room=[] zero=[] ones=[] for x in range(N): da..

알고리즘 공부 2022. 7. 4. 22:48

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제는 BFS를 해줄 것이 2가지입니다. 하나는 불이 퍼지는 것. 또 하나는 지훈이의 이동. 이 문제가 조금 애매하게 서술해서 어떤 걸 먼저 BFS해줘야할지 애매해서 질문글을 찾아보니 불을 먼저 BFS해주는 걸로 했습니다. #1. 불이 먼저 번짐 new_fire=deque() for x,y in fire: for d in range(4): nx=x+dx[d] ny=y+dy[d] ..

알고리즘 공부 2022. 7. 2. 17:54