본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 9251] LCS (python) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 문제 최장 공통 부분 수열을 구하는 문제 다이나믹 프로그래밍을 통해 해결할 수 있었다. 📌문제 접근 포인트 1. 공통된 수열을 구하기 위해서 먼저 예제 입력을 표로 그려서 그려보았다. 표를 그려서 규칙을 찾아가보자. 2. 표를 보면 같은 알파벳이 나오는 부분을 기준으로 +1씩 늘어나는 구조고, 겹치지 않는 부분은 인덱스 i와 j를 기준으로 [i].. 2023. 6. 3.
[백준 17298] 오큰수 (python) https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수 문제 A[i]의 오른쪽에 있으면서 A[i]보다 큰 수 중에서 가장 왼쪽에 있는 수인 오큰수를 구하는 문제 스택을 이용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 오큰수를 저장할 리스트를 먼저 만들어주자. 요구 조건에 오큰수가 없을 경우 -1로 표시해야하니 [-1] * N 사이즈의 리스트를 만들어주자. 2. 스택과 해당 A[i]의 인덱스를 사용해보자. 오큰수는 오른쪽에 있으면서 A[i]보다 큰 수.. 2023. 5. 31.
[백준 17135] 캐슬 디펜스(python) https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 캐슬 디펜스 문제 궁수 3명을 배치해서 적을 최대 몇까지 제거할 수 있는지 세는 문제, BFS와 완전 탐색을 이용해서 해결 할 수 있었다. 📌 문제 접근 포인트 1. 조건이 많은 문제이므로, 각각 구현해야하는 조건을 먼저 생각하자. 2. 적이 앞으로 전진하는 형태로 구현해도 가능하지만, 궁수가 앞으로 이동하는 형태로 구성하는게 조금 더 쉽게 가능하다. 3. 반복적으로 탐색을 진행해야하니, 판을 복사해서 사용.. 2023. 5. 30.
[백준 28068] I Am Knowledge (python) https://www.acmicpc.net/problem/28068 28068번: I Am Knowledge 저택에 살고 있는 마법사는 지하의 도서관에 자주 방문한다. 어느 날, 마법사는 도서관에 있는 책 \(N\)권을 모두 읽기로 했다. 책은 한 번에 한 권씩만 읽을 수 있지만, 책을 읽는 순서는 마음대 www.acmicpc.net I Am Knowledge 문제 마법사의 즐거움 수치에 따라 책을 다 읽을 수 있는지 없는지 판별하는 문제 정렬과 그리디를 활용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 아직 읽지 않은 책을 읽을 때 a만큼 즐거움 수치소비하고, 읽을 시 b만큼 즐거움 수치를 얻는다. 단, 즐거움 수치가 0 미만이 되면 안된다. 2. b가 a보다 큰 경우, 즐거움 수치를 얻는 형태의 .. 2023. 5. 28.
[백준 2580] 스도쿠 (python) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠 문제 스도쿠를 모두 채울 수 있을 경우, 그때 가능한 경우의 수 1개 만을 출력하는 문제 백트래킹을 이용하여 해결 할 수 있었다. 📌문제 접근 포인트 1. 스도쿠에 대해서 생각해보자. 스도쿠는 가로 9칸에 숫자가 겹치면 안 되고, 세로 9칸에도 숫자가 겹치면 안 되며, 해당 3*3칸에서도 숫자가 겹치면 안 된다. 2. 유망한 조건으로 위에 3가지 조건을 만들어주자. 또, 비어있는 칸에 숫자.. 2023. 5. 21.
[백준 10798] 세로읽기 (Java) https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 세로읽기 문제 주어진 글자들을 세로로 읽어서 출력하는 문제 📌문제 접근 포인트 1. 조건을 확인하자. 조건은 5줄을 최대 15개의 단어로 이루어지게 받는다. 2. 배열을 char 타입으로 생성하자. char타입으로 해서 2차원 배열을 입력받자. 3. 앞서 받은 배열을 세로부터 출력하게 바꿔주자. 이때, char 타입의 null값은 \u0000으로 표현할 수 있다. 이걸 이용해서 출력해 보자.. 2023. 5. 17.
반응형

티스토리툴바