본문 바로가기

백준(BOJ)

 (7)
[BOJ] 17471 - 게리맨더링(JAVA) 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 각각의 선거구를 미리 할당한 부분집합을 구한 뒤, 그래프 탐색을 돌리면서 부분집합과 모순이 없는지 확인하면 되는 문제이다. 만약, bfs로 탐색했을 때, 탐색하지 못한 구역이 있다면, 구역이 분리되어 있으므로 불가능한 경우가 된다. 최적화된 부분집합을 구하기 위해서 비트마스크 기법을 사용했다. 두 집합으로 나뉘지 않는 경우를 제거하기 위해 1부터 시작했으며, 01010(2)와 10101(2)와 같이 집합의 ..
[BOJ] 1052 - 물병(Python) 문제 https://www.acmicpc.net/problem/1052 풀이 같은 물병은 하나의 더 큰 물병으로 합쳐진다는 점에서 처음 주어진 n을 2진법으로 나타내면 초기에 만들 수 있는 물병의 개수를 알 수 있다. 첫번째 풀이 2진법으로 표현하고 나면, 해당 비트가 가리키는 인덱스에 따라, 현재 인덱스에서 다음 인덱스로 물통을 변환시키는데 필요한 물의 양을 알 수 있으므로, 계속 비트를 옮겨주면서 정답일 때까지 반복한다. 두번째 풀이 결국, 첫번째 풀이에서 물통을 줄이는데 중요한 것은, 현재 인덱스에서 값을 올릴 때, 다음 인덱스가 1일 때만 전체 물통의 개수가 줄어든다는 것이다. 그러므로, 반복문을 통해 정답을 구할 필요 없이, 이진법으로 된 string을 한번만 스캔하면 정답을 알 수 있다. 코드..
[BOJ] 16935 - 배열돌리기(JAVA) 문제 글이 길어서 링크로 대체합니다. https://www.acmicpc.net/problem/16935 풀이 기본적인 풀이는 r번의 연산에 대해서 배열을 변환시키면서 진행하는 것입니다. 그러나, 이번 문제에서는 좀 더 어렵지만 빠르게 풀어보고 싶었고, 이를 위해서 선형대수의 행렬 연산과 관련된 이론을 적용했습니다. 기존의 방식은 nm크기의 배열을 r번 변환시키는 연산이 필요했지만, 최적화한 코드에서는 2*2 배열로 회전과 반전에 대한 정보를 저장합니다. 이를 통해서 nmr의 연산에서 약 4r+nm의 연산으로 줄일 수 있었고, r의 값이 커지면 커질수록 기존보다 빠른 속도로 결과를 알 수 있습니다. 회전/반전은 5,6번 연산인 4분할 영역 이동과 translation과 transformation으로 서로..
[BOJ] 11003 - 최솟값 찾기(JAVA) 그냥 이 문제는 자바로 풀지 마세요. 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 기본적으로 일정 구간 안에서 1번의 스캔으로 최소/최대 값을 찾는 문제이다. 단 한번의 스캔으로 O(n) 시간에 풀기 위해서는 deque 자료구조의 삽입/연산을 활용한다. 가장 먼저, 전체 구간에서 최솟값을 구하는 방법이다. 배열의 앞에서부터 스캔을 해가면서, 스택에 최솟값을 가진 변수를 계속 넣어주면 된다. 만약, ..
[BOJ] 2866 - 문자열 잘라내기(Python) 문제 문제 풀이 이 문제는 y=r 개의 문자열을 받았을 때, y=0부터 지워나가면서 수직으로 모은 문자열들 중에 중복이 있는가를 물어보는 문제였다. 직관적인 접근 방법으로는 str_list[r]로 문자열을 받은 뒤, pop(0)을 해주면서 zip(*str_list)를 해주면 수직으로 잘린 값들이 나오고, 해당 값들 중에 중복이 있는지 확인할 수 있다. 하지만 해당 방법은 r이 길면 길수록, 문자열의 비교에 비용이 많이 들어서 최악의 경우 n*rlogr의 시간 복잡도가 된다. 이 문제는 y=0부터가 아닌 y=r-1부터 탐색한다면 O(rc)로 풀리는 문제이다. 문자열의 밑에서부터 탐색을 진행하면서, 서로 같은 값들에 대해 같은 집합으로 묶어주고, 윗줄을 탐색하면서 같은 집합에 대해서만 같은 값이 있는지 확인..
[BOJ] 1005_ACM Craft(Python) 문제 https://www.acmicpc.net/problem/1005 풀이 사용한 알고리즘 : DP, 위상정렬, BFS 가장 먼저 최적화 된 건설 시간을 구하기 위해 indegree=0인 노드에서 탐색을 시작한다. 이후, bfs나 dfs 등 원하는 방법으로 탐색하며 해당 노드의 indegree를 1씩 줄이다가 0이 되면 queue에 넣는다. indegree가 0이라는 것은 더 이상 해당 건물 건축 시간이 갱신되지 않는 다는 것을 뜻하게 된다. 그렇기에, 원하는 건물 w가 나왔을 때 정답을 리턴하여 계산을 좀 더 최적화 했다. 다만... 이번 문제는 알고리즘이 아닌 입력을 받는 방식에서 시간 초과가 생겼었고, 입력 받는 함수를 input()에서 sys.stdin.readline()으로 교체한 뒤 테스트를..
[BOJ] 1004_컨닝(Python) 문제 https://www.acmicpc.net/problem/1014 풀이 보자마자 DP와 비트마스킹을 사용하는 문제라는 것을 알았습니다. 현재 줄을 기준으로 이전에 사람들이 어떻게 앉았는지를 bitmask로 나타내고, 현재 줄에서 사람들이 앉는 형태에 따라 가능한 인원수를 dp에 저장하면 풀 수 있는 문제입니다. 그러나, 현재 줄의 조건에서 사람들이 앉을 수 있는 조합을 찾아내는데 많이 헤매서 시간이 걸렸던 문제입니다. DFS형태로 최적화된 비트마스크를 찾는 알고리즘을 구하려다 실패했네요... m

티스토리툴바