본문 바로가기

BaekJoon

[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 11266 : 단절점 문제 -> 문제 링크 : https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 문제풀이 단절점이란 해당 정점이 사라졌을 때 그래프가 여러 개의 그래프로 나눠지는 정점이다. dfs를 활용하면 단절점을 쉽게 찾을 수 있다. 단절점 찾기 알고리즘의 핵심은 dfs를 통해 먼저 방문한 순서대로 정점에 순서를 매길 때 현재 정점 이후에 발견되는 정점들이 방문할 수 있는 정점의 최소 순서가 현재 정점의 순서보다 크거나 같으면 단절점이.. 더보기
[python] baekjoon 1202 보석 도둑 문제 -> 문제 링크 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 문제풀이 가방의 개수와 보석의 개수 모두 30만으로 O(logN) 이하의 시간 복잡도로 문제를 해결해야 한다. 가방에 들어가는 보석을 선택하는 문제이든 보석을 담을 수 있는 가방을 선택하는 문제이든 시간이 O(logN)으로 찾을 수 있어야 문제를 해결할 수 있다. 기준을 가방으로 잡고, 현재 가방에 들어갈 수 있는 보석 중 가장 비싼 보석을 넣는 방식으로 문제를 해.. 더보기
[python] baekjoon 2879 풀이 문제 문제 링크 -> https://www.acmicpc.net/problem/2879 2879번: 코딩은 예쁘게 문제 백준이는 한 작은 회사에 취직했다. 이 회사에서 백준이는 소스 코드의 뒤죽박죽인 인덴트를 고치고 있다. 인덴트는 각 줄을 탭 키를 이용해 들여 쓰는 것을 말한다. 다행히 백준이가 사용� www.acmicpc.net 문제풀이 문제를 보면 최대한 많은 줄에 탭을 추가하거나 삭제해야 최솟값으로 일을 끝낼 수 있다.각 줄에서 어떤 행동을 해야하는지 알아내기 위해서 첫째 줄을 둘째 줄에 있는 값으로 빼주면 각 줄에서 해야할 행동을 구할 수 있다.양수가 있으면 탭을 추가해야하는 부분이고 음수가 있으면 제거해야하는 부분이다. 반복문을 통해 첫 줄부터 끝까지 탐색해간다. 만약 현재 줄이 이전 줄과 같.. 더보기
[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부터 시.. 더보기

티스토리툴바