본문 바로가기
반응형

알고리즘 풀이164

[백준 14499] 주사위 굴리기(python) https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 주사위 굴리기 문제 주사위를 굴려서 바닥의 숫자가 0이면 주사위 바닥면의 숫자를 바닥에, 바닥의 숫자가 0이 아니면 주사위 바닥면의 숫자를 바닥의 숫자로 바꾸고 바닥의 숫자를 0으로 바꿔가는 것을 반복했을 때 주사위 상단에 쓰여있는 수를 구하는 문제 조건 나눠서 구현하는 문제였다. 📌 문제 접근 포인트 ※ 그림으로 보는 주사위 도면.. 2023. 4. 22.
[백준 4779] 칸토어 집합 (python) https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 칸토어 집합 문제 (3 ** 입력값)의 개수만큼 -로 이루어진 직선을 조건에 맞게 3 등분해 나가면서 자르는 문제 분할 정복을 활용하여 해결할 수 있었다. 📌문제 접근 포인트 ※그림으로 보는 진행 과정 1. 3등분으로 분할 2. 분할한 가운데 지우기 3. 각각의 선 다시 3 분할하기 4. 각 선 다시 지우기 5. 위 과정을 반복 1. 위 그림과 같은 과정으로 진행해 간다. 이걸 구현해 보자. 2... 2023. 4. 21.
[백준 12919] A와 B 2 (python) https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net A와 B 2 문제 조건에 맞게 A를 추가하고 B를 추가하고 뒤집는 형식으로 만들 수 있는지 체크하는 문제 재귀를 활용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 요구 조건대로 하나씩 늘려가면서 탐색하는 방법도 있겠지만, 반대로 T를 S로 만드는 게 더 간단하겠다 싶어서 T를 S로 만드는 방향으로 접근했다. 2. 조건에 만족하는 것을 찾아가기 위해 조건.. 2023. 4. 20.
[백준 18185] 라면 사기 (Small) (python) https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 라면 사기 (Small) 문제 공장에서 라면을 구매할 경우 어떻게 사면 제일 싸게 살 수 있는지 찾는 문제 약간의 함정을 조심한 그리디로 풀 수 있었다 📌문제 접근 포인트 1. 단순하게 생각해 보자, 3개를 연속하게 사야 하면 그때 사고, 그다음에 2개를 연속하게 사야 하면 그때 사고, 그다음에 1개를 사도록 구성해 주면 해결될 것 같다. 2. 중간에 함정이 숨어있다. 2, 3,.. 2023. 4. 19.
[백준 1543] 문서 검색 (python) https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문서 검색 문제 문자열에서 중복된 부분을 제외하고 주어진 문자열과 같은 문자열이 몇 번 나오는지 세보는 문제 완전 탐색으로 풀 수 있었다. 📌문제 접근 포인트 1. 문자열에서 같은 문자열이 몇 번 나오는지 찾아야 하니 탐색할 인덱스 값 i를 정의해 주자. 2. 문자열을 하나씩 슬라이싱 해보면서 비교해 보자. 만약 슬라이싱한 값이 주어진 문자열과 같으면 중복되는 값이 있으면 안 되니 i에 문자열 크기만큼.. 2023. 4. 18.
[백준 16163] #15164번_제보 (python) https://www.acmicpc.net/problem/16163 16163번: #15164번_제보 www.acmicpc.net #15164번_제보 문제 문자열 중에 회문인 것의 개수를 구하는 문제 Manacher 알고리즘을 이용해서 해결할 수 있었다. Manacher 알고리즘에 대한 개념은 아래 링크 참고 https://edder773.tistory.com/178 [알고리즘] Manacher 알고리즘 정리 (python) Manacher 알고리즘 회문(Palidnrome)에 관한 문제를 빠르게 풀 수 있도록 만들어주는 알고리즘 문자열 S의 부분 문자열 중에서 팰린드롬인 것 중 가장 긴 것의 길이를 구하는 알고리즘을 해결하는 것 edder773.tistory.com 📌 문제 접근 포인트 1. 회문의 부.. 2023. 4. 17.
반응형

티스토리툴바