본문 바로가기

백준

[python] baekjoon 2549 : 루빅의 사각형 문제 -> 문제 링크 : https://www.acmicpc.net/problem/2549 2549번: 루빅의 사각형 첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 www.acmicpc.net 문제풀이 입력값은 2차원 배열이지만 1차원 배열로 만들어 16자리의 수열을 정렬시키는 문제로 풀면 된다. 이때 숫자를 배열보다는 문자열로 만드는 게 딕셔너리를 사용할 때 시간이 적게 든다. 하지만 10을 넘는 숫자가 있어 2차원 배열에서의 자리를 유추하기가 힘들다. 모든 숫자가 한 글자가 되도록 16진수의 수로 바꿔 표현하면 1차원 배열의 자리를 보고 2차원 배열을 .. 더보기
[python] baekjoon 11400 : 단절선 문제 -> 문제 링크 : https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 문제풀이 단절선은 제거했을 때 그래프가 여러 개로 나눠지는 간선을 의미한다. 단절선 문제를 해결하기 위해서는 트리의 부모, 자식의 개념을 이용하면 쉽다. dfs를 이용해 방문 순서대로 정점에 순서를 매긴다고 하자. 이때 자식의 정점 순서는 부모의 정점 순서 + 1이 된다. 이때 현재 간선이 없다고 가정하고, 자식 정점에서부터 접근 가능한 모든 .. 더보기
[python] baekjoon 1202 보석 도둑 문제 -> 문제 링크 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 문제풀이 가방의 개수와 보석의 개수 모두 30만으로 O(logN) 이하의 시간 복잡도로 문제를 해결해야 한다. 가방에 들어가는 보석을 선택하는 문제이든 보석을 담을 수 있는 가방을 선택하는 문제이든 시간이 O(logN)으로 찾을 수 있어야 문제를 해결할 수 있다. 기준을 가방으로 잡고, 현재 가방에 들어갈 수 있는 보석 중 가장 비싼 보석을 넣는 방식으로 문제를 해.. 더보기
[python] baekjoon 3111 검열 문제 -> 문제 링크 : https://www.acmicpc.net/problem/3111 3111번: 검열 문제 김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다. 상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다. T에 A가 없으면 알고� www.acmicpc.net 문제풀이 문자열이 최대 30만자이기 때문에 문자열 T에 있는 문자들을 한번씩만 탐색하면서 문제를 해결해야 한다고 생각했다. 문자열 T를 앞에서부터 접근하는 리스트 front와 맨끝에서부터 접근하는 리스트 back을 만들고 한칸씩 이동하면서 새로운 문자가 들어올 때 마다 리스트에 문자열 A가 만들어지는지 검사하면서 나아간다. 만약 리스트 front나 back에 문자열 A가 만들어지면.. 더보기
[python] baekjoon 가장 큰 증가 부분 수열 문제 풀이 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 수열 A가 주어졌을 때, 합이 가장 큰 증가 부분 수열의 합을 출력하시오. 문제풀이 수열의 크기는 최대 1000으로 주어진다. 가장 단순한 방법으로는 만들 수 있는 모든 수열을 만들어보고 증가 부분 수열 중 최댓값을 찾는 것이다. 하지만 이 방법은 O(2^1000)이라는 엄청난 시간이 걸린다. 이 문제는 부분문제로 쪼갠 뒤 해결할 수 있다. 현재 문제가 인덱스 i부터 시.. 더보기

티스토리툴바