본문 바로가기
반응형

Algorithm296

[Python] 백준 10942번 - 팰린드롬? (골드 4) 혼자 힘으로 풀었는가? O알고리즘 분류 - 다이나믹 프로그래밍 (DP) https://www.acmicpc.net/problem/10942 문제명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.S = 3, .. 2024. 6. 17.
[Python] 백준 9252번 - LCS 2 (골드 4) 혼자 힘으로 풀었는가? ..?알고리즘 분류 - 다이나믹 프로그래밍 (DP) https://www.acmicpc.net/problem/9252 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.  .. 2024. 6. 14.
[Java/Python] 백준 2448번 - 별 찍기11 (골드 4) 혼자 힘으로 풀었는가? X알고리즘 분류 - 재귀 https://www.acmicpc.net/problem/2448 문제예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.입력첫째 줄에 N이 주어진다. N은 항상 $ 3×2^k $ 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력첫째 줄부터 N번째 줄까지 별을 출력한다.  재귀는.. 어렵다... 우선 규칙을 찾아야 한다. 수는 3, 6, 12, 24, 48...로 늘어나며 모든 패턴은   위와 같이 나온다. 우리가 찾아야 할 것은 가장 맨 위 *을 찾는 것이다. 3일 때 *의 위치를 배열로 기준하면 (0, 2)6일 때 *의 위치는 (0, 5)와 (3, 2), (3, 8)12일 때 위치는 (0, 11) / (3, 8).. 2024. 6. 11.
[Python] 백준 1261번 - 알고스팟 (골드 4) 혼자 힘으로 풀었는가? O알고리즘 분류 - 그래프 - 다익스트라 - 최단 경로 - 0-1 BFS https://www.acmicpc.net/problem/1261 문제알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미.. 2024. 6. 7.
반응형