본문 바로가기
반응형

알고리즘 풀이164

[백준 18870] 좌표 압축(Java) https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 좌표 압축 문제 좌표 압축을 적용한 결과를 출력하는 문제 사용 알고리즘 # 정렬 📌문제 접근 포인트 1. 좌표 압축의 개념에 대해서 먼저 생각해보자. 좌표 압축은 쉽게 생각하면 중복을 제거하여 오름차순 정렬 후, 해당 순서 인덱스 값을 가져오란 뜻이다. 예를 들어 예제를 좌표 압축을 적용하면 2 4 -10 4 -9를 생각해보면 중복을 제거해서 오.. 2023. 6. 8.
[백준 9084] 동전 (python) https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동전 문제 동전의 종류가 주어 질 때 주어진 금액을 만드는 모든 방법의 수를 세는 프로그램을 작성하는 문제 사용 알고리즘 #다이나믹 프로그래밍 📌문제 접근 포인트 1. 동전의 종류가 오름차순으로 주어진다. 해당 동전들로 주어진 금액을 만들어보자. 2. 단순하게 다이나믹 프로그래밍을 구상해보자. 먼저 dp를 구상할때 0원으로 만들 수 있는 경우의 수는 무조건 1이므로 dp[0] = .. 2023. 6. 8.
[백준 1463] 1로 만들기 (python) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기 문제 주어진 숫자를 요구조건에 맞춰서 1로 만들 경우의 최소 연산 수를 구하는 문제 다이나믹 프로그래밍을 활용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 요구 제한 시간이 굉장히 짧다. 단순 완전 탐색 등의 방법이 아닌 다이나믹 프로그래밍 방법을 생각해보자. 2. 2가지 방향을 생각할 수 있다. 일반적인 다이나믹 프로그래밍 처럼 DP 1부터 X까지 규칙을 찾아 만들어 가는 방법이 있고, X부터 규칙에 맞춰 1로 찾아 갔을 때의 최소 연산을 찾는 방법이 있다. 3. 요구 조건 대로 X가 3으로 .. 2023. 6. 5.
[백준 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.
반응형

티스토리툴바