[Algorithm] 깊이/너비 우선탐색(DFS/BFS) [타겟넘버]

 

문제 ]

n개의 음이 아닌 정수가 있습니다.

이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

[제한사항]

주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

각 숫자는 1 이상 50 이하인 자연수입니다.

타겟 넘버는 1 이상 1000 이하인 자연수입니다.

DFS와 BFS ]

[ DFS ] 

깊이 우선 탐색(depth-first search)은 맹목적 탐색방법의 하나로, 노드가 트리일시 좌측노드를 기점으로 깊이 제한에 도달할 때 까지 목표노드를 찾는다. 제한 깊이까지 목표노드가 발견되지 않으면 최근노드의 부모노드로 되돌아가서 거치지 않은 다른 자식노드로 탐색을 시작한다. 여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라고 한다.

- 장점

• 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

- 단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다.

• 얻어진 해가 최단 경로가 아닌 노드 전체를 탐색해야하는 경우가 있을 수 있다. 즉 최적의 방법으로 구한 해는 아닐 수 있다.

[ BFS ]

너비 우선 탐색(Breadth-first search)은 맹목적 탐색방법의 하나로, 루트 노드를 방문한 후 인접한 모든 노드들을 우선적으로 검색하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때 까지 검색을 하는데 트리의 너비를 기준으로 검색한다.

- 장점

• 출발 노드에서 목표노드까지의 최단 길이 경로를 보장한다.

- 단점

• 너비경로가 길 경우 탐색가지가 증가함에 따라 보다 많은 기억 공간이 필요하다.

제출 DFS ] 

class Solution {

    public int solution(int[] numbers, int target) {

        int current = numbers[0];

        int answer = 0; 

        answer += dfs(current, 1, numbers, target);         

        answer += dfs(-current, 1, numbers, target); 

        

        return answer;

    }

    

    public int dfs(int prev, int index, int[] numbers, int target){

        

        if(index >= numbers.length){

            if(target==prev) return 1;

            return 0;

        }

        

        int cur1 = prev + numbers[index];

        int cur2 = prev - numbers[index];

        

        int ans = 0;

        ans += dfs(cur1, index+1, numbers, target);

        ans += dfs(cur2, index+1, numbers, target);

        return ans;

    }

}

풀이 DFS ]

재귀를 이용하여 DFS를 활용한다.

제출 BFS ]

import java.util.Queue;

import java.util.LinkedList;

class Solution {

    

    class Pair{

        int cur;

        int index;

        

        Pair(int cur, int index){

            this.cur = cur;

            this.index = index;

        }

    }

    

    public int solution(int[] numbers, int target) {

        int answer = 0;

        Queue<Pair> queue = new LinkedList<Pair>();

        queue.offer(new Pair(numbers[0],0));

        queue.offer(new Pair(-numbers[0],0));

        

        while(!queue.isEmpty()){

            Pair p = queue.poll();

            if(p.index == numbers.length-1){

                if(p.cur == target){

                    answer += 1;

                }

                continue;

            }

            int c1 = p.cur + numbers[p.index+1];

            int c2 = p.cur - numbers[p.index+1];

            

            queue.add(new Pair(c1, p.index+1));

            queue.add(new Pair(c2, p.index+1));

        }

        return answer;

    }

    

}

풀이 ]

Queue는 인터페이스 형태로 LinkedList를 통해 생성한다. FIFO(Firtst in first out)이 큰 특징이다. 

Class Pair를 원소로 하는 Queue를 이용하여 너비우선탐색을 실행한다. Pair클래스는 깊이를 나타내는 index와 해당 값 (1 +1 +1 -1 ...)을 나타내는 cur를 변수로 가진다.

Index가 numbers길이와 같다면 cur를 target값과 비교해 일치하는지 확인하여 answer에 값을 +할지 안할지 결정한다. 

Apache Kafka - 토픽삭제가 안되는 경우

[ 토픽삭제 안되는 경우 ]

server.properties 파일의 delete.topic.enable=true임에도 

토픽이 삭제되지 않는경우

1. 카프카 dir.log파일과 관련 주키퍼로그 파일 삭제

2. 카프카 브로커를 재시작한다.

참조 

: https://stackoverflow.com/questions/23976670/when-how-does-a-topic-marked-for-deletion-get-finally-removed

: https://stackoverflow.com/questions/44564606/how-can-i-remove-kafka-topics-marked-for-deletion

Apache Phoenix [2] - CDH 피닉스 초기 설정 [Init Configuration]

CDH Phoenix 초기설정

1. HBase 서비스 탭

2. hbase-site.xml에 대한 HBase 서비스 고급 구성 스니펫(안전 밸브) 검색

[1] Secondary Index

피닉스의 Secondary Index를 사용하기 위해 설정값 추가

이름 : hbase.regionserver.wal.codec

값 : org.apache.hadoop.hbase.regionserver.wal.IndexedWALEditCodec

피닉스 인덱싱에 관한 참조 : 

https://phoenix.apache.org/secondary_indexing.html

[2] 사용자정의 함수 사용

사용자 정의함수를 사용하도록 다음 속성을 설정

이름 : phoenix.functions.allowUserDefinedFunctions

값 : true

[3] 양방향을 위한 컬럼 인코딩

피닉스쿼리서버로 데이터 저장시 HBase에선 인코딩된 값으로 보여지게 된다.

해당 설정을 통해 열 매핑을 사용하지 않으므로써 HBase에서 피닉스테이블 데이터를 인코딩되지 않은 값으로 볼 수 있다.

이름 : phoenix.default.column.encoded.bytes.attrib

값 : 0

피닉스 저장포맷 인코딩 참조 : 

https://phoenix.apache.org/columnencoding.html

[4] 스키마 생성을 위한 설정

쿼리서버 네임스페이스를 위한 스키마 생성과 삭제 등을 사용하기 위한 설정

이름 : phoenix.schema.isNamespaceMappingEnabled

값 : true 

이름 : phoenix.schema.mapSystemTablesToNamespace

값 : true

피닉스 Namespace Mapping 참조 : 

https://phoenix.apache.org/namspace_mapping.html

[5] 조인을 위한 설정

해쉬맵 조인, 서브쿼리 등 쿼리결과 사이즈를 정해주는 설정

설정 값보다 작으면 MaxServerCacheSizeExceededException오류, 기본값은 100MB

이름 : phoenix.query.maxServerCacheBytes

값 : 2097152000

피닉스 설정값 참조 : 

https://phoenix.apache.org/tuning.html

3. hbase-site.xml에 대한 HBase 클라이언트 고급 구성 스니펫(안전 밸브)

해당구성 값을 다른 xml에도 추가한다.

이름 : phoenix.schema.isNamespaceMappingEnabled

값 : true

이름 : phoenix.schema.mapSystemTablesToNamespace

값 : true

CDH Phoenix 설정방법 참고 : 

https://docs.cloudera.com/documentation/enterprise/6/latest/topics/phoenix_installation.html

https://docs.cloudera.com/documentation/enterprise/latest/topics/phoenix_mapping_schemas_namespaces.html

[Algorithm] 탐욕법 ( 체육복 )

문제 ]

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

n    lost    reserve    return

5    [2,4]    [1,3,5]    5

5    [2,4]    [3]        4

3    [3]      [1]        2

제출 1]

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        List<Integer> reserve_list = new ArrayList<>(); 
        for (Integer t : reserve) { 
            reserve_list.add(t); 
        }
        
        for(int i=0; i<lost.length; i++){
            int idx = lost[i];
            int idx1 = 0;
            if(i+1 < lost.length) idx1 = lost[i+1];

            if(reserve_list.indexOf(idx)>-1){
                reserve_list.remove(reserve_list.indexOf(idx));
                continue;
            }

            else if(reserve_list.indexOf(idx-1)>-1){
                reserve_list.remove(reserve_list.indexOf(idx-1));
                continue;
            }

            else if(reserve_list.indexOf(idx+1)>-1){
                reserve_list.remove(reserve_list.indexOf(idx+1));
                continue;
            }
            else answer++;                
        }
        
        return n-answer;
    }
}

풀이 ]

문제 풀이를 위한 단계를 정리하자면,

1. 여벌학생들 중 잃어버린 학생이 있으면 reserve에서 삭제
2. 잃버학생들 앞번호에 여벌학생있으면 잃버학생 lost에서 삭제, 여벌학생 reserve에서 삭제
3. 잃버학생들 뒷번호에 여벌학생있으면 잃버학생 lost에서 삭제, 여벌학생 reserve에서 삭제
4. n - lost.len 으로 체육수업 듣는 학생수 계산

위 코드 제출시 테스트케이스 12번 오류가 발생한다. n=8, lost= [4,5] , reverse=[5,6] 인 경우에 lost [5]는 reserve[5]로 사전처리되어 lost[4]가 reserve[5]를 이용하지 못해야한다. 따라서 위의 코드는 n=8이 나온다.(정답 n=7)

즉 추가되는 예외처리는 "여분을 가져왔지만 체육복을 잃어버린사람은 체육복을 빌려주지 못한다"라는 조건이 추가되어야한다.

제출2 ]
import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;
       
        //여분을 가져옴과 동시에 잃어버린사람 선처리
        for (int l : lost)
            people[l-1]--;        
        for (int r : reserve) 
            people[r-1]++;

        //잃버사람, 앞뒤번호 여벌을 가져온사람에게 체육복 빌리기
        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) {
                if(i-1>=0 && people[i-1] == 1) {
                    people[i]++;
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) {
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--;
            }
        }
        return answer;
    }
}

[Algorithm] 완전탐색 (모의고사)

문제 ]

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answer : [1, 2, 3, 4, 5] / [1,3,2,4,2]

return : [1] / [1,2,3,]

제출 ]

import java.util.*;

class Solution {

    public int[] solution(int[] answers) {

        int[] n1_array = {1,2,3,4,5};

        int[] n2_array = {2,1,2,3,2,4,2,5};

        int[] n3_array = {3,3,1,1,2,2,4,4,5,5};

        int[] result = new int[3];

        int n1_len = n1_array.length;

        int n2_len = n2_array.length;

        int n3_len = n3_array.length;

        for(int i=0; i<answers.length; i++){

            if(answers[i] == n1_array[i%n1_len]) result[0]++;

            if(answers[i] == n2_array[i%n2_len]) result[1]++;

            if(answers[i] == n3_array[i%n3_len]) result[2]++;

        }

        // 가장 높은 점수 

        int max = Math.max(result[0], Math.max(result[1], result[2]));

        

        List<Integer> list = new ArrayList<>();

        if(max == result[0])

            list.add(1);

        if(max == result[1])

            list.add(2);

        if(max == result[2])

            list.add(3);

        

        int[] answer = new int[list.size()];

        int size=0;

        for(int i=0; i<list.size(); i++) answer[i] = list.get(i);

        

        return answer;

    }

}

풀이 ]

첫번째 for문만 잘 작성한다면 나머지는 문제될게 없다.

각 다른 길이의 배열을 동일한 인덱스 값으로 반복문을 돌 수 있게 만드는게  포인트이다.

- 수포자배열[ 인덱스 % 수포자배열길이 ]

수포자1 : 1  2  3  4  5  1  2  3  4  5  ....

수포자2 : 2  1  2  3  2  4  2  5  2  1  ....

수포자3 : 3  3  1  1  2  2  4  4  5  5  ....

Apache Nifi - 카프카 데이터 분산처리 ( Distribute Kafka Data)

1. Nifi Processor MergeContent

MergeContent프로세서를 이용해 Input processor(ex.Kafka, File)에서 들어오는 데이터를

적절한 크기로 Merge한 다음에 다음 단계로 넘겨주는 Flow를 기대했다.

그러나 MergeContent는 이미 받은 데이터를 다시 병합하여 데이터를 복제하는 형식으로 기대했던 결과를 가져오지는 못했다.

예를 들어 100의 데이터가 들어온다면 100개의 데이터를 차곡차곡 쌓았다가 하나의 데이터로 병합하여 결국 1개의 데이터가 들어와야 하는것을 결과로 예상했지만, MergeContent는 100개의 데이터를 일단 Nifi 저장 후, 그 데이터들을 병합한 데이터셋 복제복을 만들어 다음 프로세스로 넘겨준다. 결국 병합된 1개의 데이터셋을 전달하지만, 이중 저장을 하기 때문에 비효율적이다.

2. 하나의 클래스터에서 에서 3개의 nifi processor로 분산처리

해당 그림처럼 관련 processor를 여러개 만들어 분산처리가 될 때 

확인해야 할 사항이 

1. 데이터가 중복이 되는가?

2. 데이터가 누락이 되는가?

3. 처리속도가 늘어나는가?

정도가 있을 것 같다.

테스트를 위해 카프카데이터를 받아오는 Flow 3개를 셋팅하고, 

인위적으로 프로듀서에 데이터를 넣는 코드를 작성한다. 

테스트 토픽은 partition 3개로 설정하여 테스트하였다.

[ Nifi Flow ]

[ Python 코드 ]

from kafka import KafkaProducer
import time

producer = KafkaProducer(bootstrap_servers=['192.111.111.111:9092','192.222.222.222:9092','192.3333.333.333:9092'])

for i in range(1,5000):
    producer.send('test',str.encode('kafka:-%d' % i))
    time.sleep(0.5)

Hive테이블에 저장 후 데이터들을 보니 중복,누락 없이 3개의 프로세서가 데이터를 받아온다.

( 파일명 : 1_날짜_tuuid / 2_날짜_tuuid / 3_날짜_tuuid )

3. 3개의 NiFi 클래스터로 분산처리

2.에서는 하나의 클래스터에서 3개의 프로세스로 처리했다면, 클러스터 단계에서도 여러 서버를 두어 트래픽을 분산시킬 수 있다.

카프카 partition과 나이파이 kafka-consumer는 N:1로 매칭된다. 즉 partition 3개 : kafka-consumer 3개로 설정하면 1:1로 매칭되어 최적의 효율을 보여준다.

아래그림을 보면 이해가 편하다. Concurrent Task를 2.에서 작성한 kafka-consumer processor라고 보면 될 것이다.

반면 Partition 2개 : kafka-consumer 3개로 설정하면 kafka-consumer 1개는 데이터를 소비하지 않으므로 비효율적이다.

Partition 4개 : kafka-consumer 2개 로 설정하면 2:1로 매칭되어 아래와 같은 구성이 된다. 

2.와 3.의 방법을 둘다 적용하는 3개의 클러스터에서 2개의 nifi processor로 분산처리하는 방법도 있다.

NiFi에서 특정 파티션으로 연결할 수 있는 기능은 없으며 자동적을 NiFi cluster와 concurrent Task 수에 따라 지정된다. 따라서 시스템을 구성하기 전에 파티션수와 컨슈머 수, 트래픽량을 먼저 고려해야한다.

[ 참조 ]

MergeContent : 

https://nifi.apache.org/docs/nifi-docs/components/org.apache.nifi/nifi-standard-nar/1.5.0/org.apache.nifi.processors.standard.MergeRecord/additionalDetails.html

Remote Process Group 을 이용 : 

https://pierrevillard.com/2017/02/23/listfetch-pattern-and-remote-process-group-in-apache-nifi/

Nifi Distribute : 

https://community.cloudera.com/t5/Community-Articles/Integrating-Apache-NiFi-and-Apache-Kafka/ta-p/247433

[Algorithm] 정렬 (K번째 수)

문제 ]

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

제출 ] 

import java.util.Arrays;

class Solution {

    public int[] solution(int[] array, int[][] commands) {

        int[] answer = new int[commands.length];

        int[] temp = {};

        for(int i=0; i <commands.length; i++){

            int idx = commands[i][2]-1;

            temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);

            Arrays.sort(temp);

            answer[i] = temp[commands[i][2]-1];

          }

        return answer;

    }

}

풀이 ]

1. Out Of Index 에러를 막기위해 answer INT배열을 새로운 길이로 재선언한다. 

2. Arrays.copyOfRange함수를 이용해 배열을 자른다.

Arrays.copyOfRange(자를 배열, 시작인덱스, 끝인덱스)를 통해 배열을 잘라도 

원 배열의 값은 변경되지 않는다.