본문 바로가기

알고리즘

 (403)
[1780]. 종이의 개수 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
[2630]. 색종이 만들기 [1. 문제 설명] 정사각형 모양의 2차원 배열에서 같은 색깔로 구성 된 정사각형의 개수를 찾는 문제. 정사각형 한변의 길이는 최대 128이고, 현재 정사각형이 모두 같은 색깔로 구성되지 않은 경우, 4등분하여 검사한다. [2. 풀이 접근] 재귀로 접근 재귀의 탈출 조건, 정사각형 한변의 길이가 1인 경우 2차원 배열 내 모든 값의 합이 0 이거나, N^2 이면, 모두 같은 색깔로 이루어진 것을 판별할 수 있다. => 배열이 크지 않으니, 시간 상 큰 문제 없다고 생각함. 모든 색깔이 같은 경우, 정사각형 내 아무 원소나 선택 하여 그 색깔을 알 수 있다. 모든 색깔이 같지 않은 경우, 분할 후 재귀로 처리한다. [3. 코드]
[1021]. 회전하는 큐 [1. 문제설명] 연산1: 첫번째 원소를 제거한다. 연산2: 첫번째 원소를 왼쪽으로 한칸 이동 연산3: 마지막 원소를 오른쪽으로 한칸 이동 큐에 처음 포함되어 있던 수가 N 개, 뽑고자 하는 원소의 위치가 입력으로 주어 질 때, 원소를 주어진 순서대로 뽑아내는데 필요 한, 2번, 3번 연산의 최소 값을 출력 [2. 풀이 접근] 완전 탐색 => deque 에 첫번째 원소가 찾고자 하는 원소인 경우, 연산 1 수행 후, 다음 재귀 호출 => 위 경우가 아닌 경우, 연산 2 수행 후 기존 deque 복원 후, 연산 3 수행 ==> 문제점, 무한 루프 발생 == ==> 2번 연산 수행 후 재귀 호출 시 연산 3을 수행 할 경우, 원래 상태로 복원 되버림 ==> 일종의 cycle 이 발생 함. 완전 탐색 Cycl..
[동적 계획법] JLIS [1. 문제 재정의 및 추상화] [2. 해결 계획] 두 수열의 LIS 를 찾은 뒤 각각 합치면 해결 할 수 없다 LIS 를 구하는 재귀 함수의 입력을 두개로 늘려야 함 => 각 수열을 받기 위해 => A[indexA] 와 B[indexB] 에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수 A[indexA] 와 B[indexB] 중 작은 쪽이 앞에 온다고 가정 이 증가 부분 수열의 다음 숫자는 두가지 경우가 존재 1. A[indexA +1] 이후 또는 2. B[indexA +1] 이후 수열 중 max(A[indexA], B[indexB]) 보다 큰 수 중 하나 => 증가 부분 수열이 되기 위해선 A[indexA], B[indexB] 보다 큰 값이 뒤에 와야 한다. [3. 계획 검증]
[동적 계획법] WILDCARD [1. 문제 재정의 및 추상화] 와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자 일치 시, 와일드카드 패턴이 파일명과 대응된다 말함 '?' 는 어떤 글자와도 대응된다 가정함 '*' 는 0글자 이상의 어떤 문자열에도 대응 됨. 주어진 와일드카드 패턴에 대응되는 문자열 출력 ex) 와일드카드 패턴 he?p 에 매치되는 문자열은 아래와 같다 heap, help helpp 는 ? 가 lp 에 대응 될 수 없기 때문이다 패턴이 아닌 문자열은 알파벳 대소문자와 숫자만으로 구성 됨. [2. 해결 계획] 완전 탐색 풀이 #include // w: 와일드카드 패턴 // s: 문자열 bool match(const std::string &w, const std::string &s) { int pos = 0;..
동적 계획법 [1. 도입] 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다 다만, 어떤 부분 문제가 두 개 이상의 문제를 푸는데 사용 될 때 이 문제의 답을 한번만 계산 하고 향후 이 결과를 재활용하여 속도 향상을 노려볼 수 있다. 여기서 두 번 이상 계산 되는 부분 문제를 중복되는 부분 문제라 한다. [2. 메모이제이션] 한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법 참조적 투명 함수인 경우 적용 가능함 참조적 투명 함수란? => 입력이 고정되어 있을 때 그 결과가 항상 같은 함수 => 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성이라 함. [3. 메모이제이션 구현 패턴] 기저 사례를 먼저 처리 => 입력이 범위를 벗어난 경우, ... 가능한 경우 cache[] 를 모두 -1로..
[분할 정복] FENCE [1. 문제 재정의 및 추상화] 너비가 같은 N 개의 나무 판자에서 잘라낼 수 있는 많은 직사각형 중 가장 큰 직사각형의 넓이 단, 비스듬히 잘라 낼 수 없다. N 은 최대 20000 까지 주어짐 TestCase 는 최대 50 까지 주어짐 [2. 해결 계획] 완전 탐색에서 시작 left = 0 ~ right = N 까지 범위에서 최대 넓이를 찾고 left = 1 ~ right = N 까지 범위에서 최대 넓이를 찾고, ... 분할 정복으로 계산 한다면, A) 가장 넓은 직사각형이 중앙에서 왼쪽에 존재하는 경우 B) 가장 넓은 직사각형이 중앙에서 오른쪽에 존재하는 경우 C) 가장 넓은 직사각형이 왼쪽과 오른쪽에 걸쳐있는 경우 Case C 의 경우, 최초에는 중앙에 두개의 판자를 모두 덮을 수 있게 둘 중 최..
[1316] 그룹 단어 체커 [1. 문제 재정의 및 추상화] 문제에서 정의하는 그룹 단어 => 단어에 존재하는 모든 문자에 대해서 각 문자가 연속해서 나타나는 경우 => kin: k, i, n 이 한번씩 연속해서 나타나므로 그룹 단어 => aabbbccb: b 가 불연속이므로 그룹 단어가 아님 입력으로는 단어의 개수 N 이 맨 처음줄에 있고, 그 밑으로 N 만큼 단어가 주어짐 1 0 { input, _ := r.ReadString('\n') input = strings.TrimRight(input, "\r\n") TC-- count += isGroupWord(input) } fmt.Println(count) }
[2941] 크로아티아 알파벳 [1. 문제 재정의 및 추상화] 크로아티아 알파벳을 특정한 패턴으로 변경 할 수 있음. 단어가 주어졌을 때 크로아티아 알파벳 개수를 세야함 테이블에 주어지지 않은 알파벳은 한 글자씩 세야함 입력은 최대 100개 의 단어로 구성되며, 알파벳 소문자와 '-', '=' 으로만 이루어 짐. 입력이 몇개의 크로아티아 알파벳으로 이루어져 있는지 출력해야 함 [2. 해결 계획] 변환 된 패턴을 정의하는 배열을 구성 입력된 문자열에 앞에서 부터 (1) 에서 정의 된 패턴과 매치되는 것이 있는지 확인 있으면, 해당 길이만큼 slice 를 부분 슬라이스하고, 없는 경우 1 만큼만 부분 슬라이스함 위 과정에서 알파벳 개수를 세야함. [3. 계획 검증] [4. 구현] package main import ( "bufio" "f..
[1157] 단어 공부 [1. 문제 재정의 및 추상화] 알파벳 대소문자로 구성된 단어가 주어짐 이 단어에서 대소문자 구분 없이 가장 많이 사용된 알파벳을 찾아야 함 주어지는 단어의 최대 길이는 1,000,000 가장 많이 사용된 알파벳을 대문자로 출력해야 함 단, 가장 많이 사용된 알파벳이 여러개인 경우 ? 를 출력해야 함. [2. 해결 계획] 입력의 최대 길이가 1M 이므로 GO 언어를 기준으로 단순히 fmt.Scanf 를 사용하는 것이 시간초과를 유발 할 수 있음. bufio 를 이용해서 io 시간을 단축해야 함. 각 알파벳의 사용 빈도수를 정렬해서 max 가 여러개인 경우를 확인해야 함. [3. 계획 검증] [4. 구현] package main import ( "bufio" "bytes" "fmt" "os" ) func ..

티스토리툴바