728x90 반응형 백준 알고리즘50 [백준 2665][파이썬] 미로 만들기 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력하는 문제이다. 그래프로 탐색을 하면서 특정 좌표에 도착하기까지 바꿔야 할 검은 방의 최소값을 갱신해가면 된다. 흰 방부터 생각해보자. 첫 번째 좌표인 (0, 0)에서는 바꿔야 할 검은 방의 개수가 0이다. 또한 이 첫 번째 좌표와 연결된 모든 흰 방의 좌표 역시 바꿔야 할 최소 검은 방의 개수가 0이다. 당연하게도 연결되어 있는 모든 흰 방의 좌.. 2023. 7. 31. [백준 12970][파이썬][그리디] AB https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 내 기준 상당히 어려웠던 문제. 내가 생각했던 방식과 개선해나가는 과정을 기록해보려고 한다. (A, B) 쌍의 개수 구하기 우선 특정 문자열에서 (A, B) 쌍의 개수는 어떻게 구할 수 있을까? 예를 들어 ABBAABBB 라는 문자열에서 (A, B) 쌍의 개수를 구해보자. 모든 A에 대해서 각 A 뒤에 있는 B의 개수를 구해서 더하거나 모든 B에 대해서 각 B 앞에 있는 A의 개수를 구해서 더하면 된다. 첫 번째 A에 대해서 .. 2023. 7. 18. [백준 12904][파이썬][그리디] A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 두 가지 연산을 통해 S에서 T로 바꿀 수 있는지 판단하는 문제이다. 처음에는 S에서 T로 바꾸는 방식으로 시도를 했는데 굉장히 까다로웠다. S에서 T로 바꾸는 방식은 하나의 단계마다 여러 가지 경우의 수가 존재하기 때문에 신경써야하는 부분이 많다. 그런데 T에서 S로 바꾸는 방식은 하나의 단계마다 단 하나의 경우의 수만 존재한다. 길이가 4인 문자열의 마지막.. 2023. 7. 16. [백준 1411][파이썬] 비슷한 단어 https://www.acmicpc.net/problem/1411 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복 www.acmicpc.net 시간 복잡도를 줄이기 위해서 전처리 과정을 진행했다. 각 문자를 해당 문자가 처음 등장한 순서로 변경한다. 'cacccdaabc'를 기준으로 보면 c는 처음 등장했기 때문에 1이고 a는 두 번째 등장했기 때문에 2이고 c는 세 번째 등장했기 때문에 3이다. 이런 식으로 문자열을 변환하면 '1211132241'이 된다. 그 다음 'cdcccaddbc'도 동일하게 변환하면 '121113224.. 2023. 7. 11. 이전 1 2 3 4 ··· 13 다음 728x90 반응형
