본문 바로가기

분류 전체보기

 (43)
[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)와 같이 집합의 ..
그리디 알고리즘 그리디 알고리즘이란? 탐욕 기법 이라고도 불리며, 현재 상황에서 가장 좋은 해만 선택하는 것 그러므로 한번 선택을 번복하지 않는다(백트래킹 x) 그리디 알고리즘을 적용하기 위해서는 현재의 최선의 선택이 최적 해에 도달한다는 것을 확인해야 함 또한 같은 유형의 문제라도 선택지에 따라 그리디 알고리즘이 최적해를 보장하지 못할 수도 있다. 최적해임을 보장하기 위해 탐욕적 선택 + 하위 문제의 최적해가 전체 문제의 최적해임을 증명해야 한다. -> 탐욕적 선택 속성 + 최적 부분 구조그리디 알고리즘의 타당성 파악 그리디 알고리즘은 주로 귀류법(부정문에서 모순을 찾아내서 원 명제가 참임을 증명)으로 타당성이 증명되는 경우가 많다. 예시) - 회의실 배정문제 - 회의 시간이 겹치지 않으면서 최대한 많은 회의가 배정될..
[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으로 서로..
자바 - 순열/조합 generator 구현하기 기존 순열/조합 알고리즘의 문제점 기존의 순열 조합을 찾는 알고리즘은 적절한 배열이 아니더라도 끝까지 탐색을 한다는 문제점이 있다. 또한, 모든 경우의 수를 탐색하기 때문에, 경우의 수를 만드는 시간이 오래 걸린다. 예를 들어 bitmask를 이용해 조합을 만들 경우, 2^n가지의 경우를 탐색해봐야 한다. 그러나, next permutation 기법으로 생성할 경우, 함수를 호출할때만 다음 결과를 리턴하므로, 메모리와 시간 복잡도 측면에서 효율적이다. 구현 이론 가장 먼저, 정렬된 배열을 기준으로 bubble sort를 한 단계씩만 진행하는 함수를 만든다고 생각하면 쉽다. 순열 next permutation 구현 public static void main(String[] args) { int[] resu..
[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)로 풀리는 문제이다. 문자열의 밑에서부터 탐색을 진행하면서, 서로 같은 값들에 대해 같은 집합으로 묶어주고, 윗줄을 탐색하면서 같은 집합에 대해서만 같은 값이 있는지 확인..

티스토리툴바