곱연산 계산

곱연산이 헷갈려서 만들었다.

calc([50, 30, 20]);

function calc(persents){
 let value = 1;
 let calcPersent = 1;

 for(persent of persents){
  calcPersent *= (1-(persent/100));
 }
 value -= calcPersent;
 return value*100 + " %";
}

spacebar로 값을 구분하며 숫자만 입력

Read more →

프로그래머스 강좌, 자료구조와 알고리즘 - 3

자료구조와 알고리즘 - 3 link

14강. 큐(Queues)

큐는 Stack과 달리 선입선출(FIFO; First-In First-Out) 의 순서로 제어됩니다. 리스트 속에 데이터들의 시작과 끝의 포인터가 존재합니다. 입력(enqueue)시, 리스트의 rear pointer에 추가되며 출력(dequeue)시, 리스트의 front pointer 부분을 꺼내게 됩니다.

실습

목표: 배열과 양방향 연결 리스트 구현시, 연산 복잡도 확인

배열 - 출력시, 모든 개체의 위치를 옮기는 과정에서 O(n) 가 소요
양뱡향 연결 리스트 - 포인터만 변경하게 됨으로 O(1) 소요

15강. 환형 큐(Circular Queue)

dequeue 과정에서 발생한 front pointer 앞의 공간을 재사용하지 못하는 큐의 단점을 개선하여 리스트의 시작과 끝을 이음으로써 재사용 가능

실습

목표: 환형큐의 enqueue, dequeue, peek 구조를 구현

범위가 제한된 배열을 환형으로 이어서 쓴다는점을 감안하여 배열의 끝과 처음을 연속적으로 사용

16강. 우선순위 큐(Priority Queues)

FIFO 의 특성을 가진 일반적인 큐와 달리 우선순위에 따라 enqueue나 , dequeue의 대상이 선택되는 방식.

실습

목표: 양방향 리스트를 통해 enqueue할 때, 순차검색을 통해 일치하는 위치에 넣는 방식 사용, data의 값이 클수록 높은 우선순위.

enqueue => O(n), dequeue = O(1)
트리구조 사용시 더 유용하나 다음 과정에 진행, 퀵정렬과 비슷한 느낌일것으로 예상

17강. 트리(Trees)

트리의 각 노드를 정해진 순서로 방문하는 것, 순회 (traversal) 연산.

• 깊이 우선 순회 (DFT; Depth First Traversal)
• 넓이 우선 순회 (BFT; Breadth First Traversal)

DFT (Depth First Traversal) vs DFS (Depth First Search)? link

1. DFT는 DFS를 사용합니다.
2. DFS가 연결된 그래프에 적용되는 알고리즘 인 반면, DFT는 일반적으로 연결이 끊어진 그래프에 적용되는 순회입니다.
3. DFS는 DFT가 수행하는 동안 각각의 모든 노드를 방문 할 것이라고 보증하지 않았습니다.

하지만 같은것이라 보아도 크게 문제되지 않습니다. 두 용어 모두, 그래프 또는 트리 (모든 트리는 또한 그래프이기도 합니다) 를 대상으로 노드들을 방문하는 순서를 규정하는 방식을 뜻합니다.

근데 tree보단 root모양인데 왜 그렇게 굳어진걸까?

18강. 이진 트리(Binary Trees)

모든 노드의 자식노드; 차수가 2 이하인 트리구조

깊이 우선 순회(DFT; Depth First Traversal)

• 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
• 전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
• 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문

실습 1

목표: 이진트리의 depth 값 계산하는 기능 구현

class Node:
 # 초기화 & size()
 
    def depth(self):
        # 재귀적으로 호출하며 단말노드 부터 체크
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        # l 과 r 변수에 좌우 노드의 깊이값 저장
        return (l if l > r else r) + 1
        
class BinaryTree:
 # 초기화 & size()
 
    def depth(self):
        # 루트값 유무 확인
        if self.root:
            # root node 부터 depth 확인절차 진행
            return self.root.depth()
        else:
            return 0

실습 2, 3 - 깊이 우선 순회(DFT; Depth First Traversal)

목표: 이진트리의 전위순회, 후위순회 연산 기능 구현

class Node:
 # 초기화 & inorder()
 
 def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal

class BinaryTree:
 # 초기화 & inorder()
 
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

19강 이진 트리 - 넓이 우선 순회(BFT; Breadth First Traversal)

BFT는 트리 구조에서 낮은 level 중 왼쪽 노드부터 순회하게 됩니다. 이로써 DFT와 달리 재귀적으로 구현이 불가합니다. 하지만 Queue를 사용하여 다음에 방문할 노드를 enqueue 해두고 dequeue 하게되면 각각의 level별로 노드를 순회하게 됩니다.

실습

목표: 넓이 우선 순회 기능을 구현

    def bft(self):
        traversal = []
        queue = ArrayQueue()

  # root 존재여부 확인
        if self.root:
            queue.enqueue(self.root)

  # 하위 노드를 queue에 추가하며 노드의 값을 저장
        while not queue.isEmpty():
            node = queue.dequeue()
            traversal.append(node.data)
            if node.left:
                queue.enqueue(node.left)
            if node.right:
                queue.enqueue(node.right)

        return traversal

20강. 이진 탐색 트리(Bianry Search Trees) (1)

시간복잡도

1. Search Operation - O(n)
2. Insertion Operation - O(1)
3. Deletion Operation - O(n)

퀵정렬의 알고리즘을 트리의 형태로 접근하는 방식으로 생각하면 될 것 같다.

실습

목표: BST 에 insert 기능을 구현

    def insert(self, key, data):
     # 키 중복시 예외
        if self.key is key:
            raise KeyError('inserted key is duplicated')

        # key의 비중 확인
        if self.key > key:
            # 하위노드 존재여부 대응
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif self.key < key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
                
        return True

21강. 이진 탐색 트리(Binary Search Trees) (2)

트리노드 삭제시 고려사항 참조

1. 하위노드 X
   
2. 1개의 하위노드
   
3. 2개의 하위노드
   

3번을 처리하며 1, 2의 과정 모두 처리가능

def remove(self, key):
    node, parent = self.lookup(key)

    if node:
        nChildren = node.countChildren()
        
        if nChildren is 0: #하위노드 0개
            if parent:
                if node.key is parent.left.key:
                    parent.left = None
                else:
                    parent.right = None
            else:
                self.root = None
            
        elif nChildren is 1: #하위노드 1개
            childNode = None
            if node.left:
                childNode = node.left
            else:
                childNode = node.right
                
            if parent:
                if node.key is parent.left.key:
                    parent.left = childNode
                else:
                    parent.right = childNode
            else:
                self.root = childNode
                
        else: #하위노드 2개
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left
                
            node.key = successor.key
            node.data = successor.data
            
            if successor.key is parent.left.key:
                parent.left = successor.right
            else:
                parent.right = successor.right

        return True

    else:
        return False

22강. 힙(Heaps)

힙 (heap) 도 이진 트리의 한 종류이며 이진 힙 (binary heap) 이라고도 불립니다.

힙에는 최대 힙 (max heap) 과 최소 힙 (min heap) 이 있습니다. 최대 힙과 최소 힙은 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐만 달라지고 완전히 대칭이므로, 여기에서는 최대 힙을 기준으로 설명을 전개하겠습니다. 최대 힙은 세 가지의 성질을 유지하고 있는 이진 트리입니다. 그 세 가지 성질은:

• 루트 노드가 항상 최댓값을 가진다.
• 완전 이진 트리이다. (최하위 레벨을 제외하고 모든 레벨이 차있는 상태)
• 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

완전이진트리의 제약조건으로 인해 log(n)에 비례하는 실행시간을 가짐

배열을 이용해 이진트리 표현시 index 는
*노드 번호 n 기준

• 상위 : m // 2
• 좌측 하위: 2 * n
• 우측 하위: 2 * n + 1

실습

목표: 새로운 노드 추가

    def insert(self, item):
        self.data.append(item)
        index = len(self.data)-1
        
        while index > 1:
            if(self.data[index] > self.data[index // 2]):
             # 아래 방법으로도 손쉽게 값 교환을 할 수 있었다.
             # self.data[index], self.data[index // 2] = self.data[index // 2], self.data[index]
                self.data[index] = self.data[index // 2]
                self.data[index // 2] = item
                index = index // 2
            else:
                break

23강. 힙(Heaps) (2)

최대 힙에서의 삭제. logn의 복잡도

1. 루트노드의 제거 (루트노드에 최대값이 위치)
2. 트리의 마지막 노드를 루트노드로 이동
3. 양쪽 자식노드보다 작을때 까지 서로 값을 교환 (자식노드 중 둘다 클경우 더 큰쪽으로)

최대/최소 힙의 응용

우선 순위 큐 (priority queue)
삽입(enqueue)시, 느슨한 정렬(=반정렬; 큰값이 상위, 작은값이 하위에 있음)을 이루고 있도록 함. O(logn) 의 복잡도
출력(dequeue)시, 최대값을 순서대로 추출. O(logn) 의 복잡도

힙 정렬 (heap sort)
정렬되지 않은 원소를 최대힙에 삽입, O(logn) X 힙이 빌때까지 삭제순으로 정렬, O(logn) = O(nlogn)

Read more →

개발 환경의 자동화, CI

Continuous Integration

CI(Continuous Integration), 지속적 통합이란 소스관리, 빌드, 배포 등의 구조를 자동화 함으로써 소프트웨어 개발에 위험을 줄이는 방법으로 사용되고 있습니다.

CI 구성의 핵심 4요소

CI Server

빌드 스크립트를 작성하고 자동화 프로세스를 구성하여 빌드. 테스트를 포함한 자동화 절차를 통해 검증하며 오류를 감지한다.
예) Jenkins, Travis 등

Source Control, Version Control

소스 코드 관리 및 팀 단위 구성의 프로젝트 진행시 필수적이며 오류 수정과정을 돕는다.
예) Subversion(SVN), Git, GitLab 등

Build Tool

Source Control에서 구성된 소스 코드를 실행 가능한 형태로 가공하며 사전에 구성된 테스트 절차를 진행하여 구성된 소스 코드의 결함을 파악한다.
예) Maven, Gradle, Ant 등

Test Tool

사전 구성된 테스트 코드에 따라서 일련의 검증과정을 거친다. 기능의 검증 뿐만 아니라 코드 품질에 대해서도 검증과정이 진행되는것이 좋다.
예) Junit, SonarQube 등

참조

• http://www.nextree.co.kr/p10799/
• http://www.chidoo.me/index.php/2016/03/21/sonarqube-for-ci/
• https://asfirstalways.tistory.com/303
• https://codeship.com/continuous-integration-essentials

Read more →

프로그래머스 알고리즘, 가장 큰 수

목표 (문제)

주어진 배열의 수를 조합하여 가장 큰 수를 만든다.

조건

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

잡설

생각한 과정에서 문제가 생겨 더이상 진행하지 못하고 다른 풀이를 보았는데 comparator를 사용한걸 알게되었다. 해당 comparator에 대해 기록해봐야겠다.

코드

 public static String solution(int[] numbers) {

    String answer ="";
    List<String> list = new ArrayList<>();
    int length = numbers.length;

    for(int i=0; i<length; i++){
        list.add(Integer.toString(numbers[i]));
    }

    int size = list.size();
    Collections.sort(list, new Comparator<String>(){
        @Override
        public int compare(String num1,String num2){
            return (num2+num1).compareTo(num1+num2);
        }
    });
    if(list.get(0).equals("0")){
        return "0";
    }

    for(int i=0; i<size; i++){
        answer = answer + list.get(i);
    }
    return answer;
}

참조

잘못된 시도

잡설

처음 구조를 작성할때 Collections.sort를 string 일때 정렬하면 자리값 별로 비교하던것에 꽂혀서 구성을 했던것이 문제였던 것 같다. 비교하는 과정이 올바르지 않았기에 발생한 문제인것으로 생각한다.

코드

public static String solution(int[] numbers) {
 // int[0~9][0~n] 2차배열 생성
 List<LinkedList<String>> numberGroup = new ArrayList<>();
 for (int i = 0; i < 10; i++) {
     numberGroup.add(new LinkedList<>());
 }

 // 맨앞자리 숫자값으로 분류하여 배열 삽입
 for (int num : numbers) {
     String temp = Integer.toString(num);
     int numIndex = Integer.parseInt(temp.substring(0, 1));// 앞부분 때기
     numberGroup.get(numIndex).add(temp);
 }

 // 배열 정렬
 for (LinkedList<String> numberList : numberGroup) {
        Collections.sort(numberList, Collections.reverseOrder());
 }

 // 문자열 병합
 StringBuilder result = new StringBuilder();
 for (int i = numberGroup.size() - 1; i >= 0; i--) {
     System.out.println(numberGroup.get(i));
     for (String number : numberGroup.get(i)) {
         result.append(number);
     }
 }
 return result.toString();
}

참조 - https://n1tjrgns.tistory.com/139

Read more →

프로그래머스 알고리즘, 모의고사

목표 (문제)

1~5까지를 일정한 패턴으로 반복할때, 그 값들을 주어진 answers와 비교하여 일치하는 값의 갯수들을 배열로 반환하시요.

조건

• answers 의 길이는 최대 10,000 입니다.
• 배열값은 반드시 1, 2, 3, 4, 5 중 하나입니다.
• 일치하는 개수가 동일할 경우, Index를 기준으로 오름차순 정렬해주세요.
• 일치하는 값이 모두 없을때, 두 반환합니다.

코드

public class Main {

    public static void main(String[] args) {
//        int[] answers = { 1, 2, 3, 4, 5 };
//        int[] answers = { 1,3,2,4,2 };
        int[] answers = { 3, 1, 1 };
//        int[] answers = { 4, 4 };

        for (int val : solution(numbers)) {
            System.out.print(val + ",");
        }
    }

    public static int[] solution(int[] answers) {
        int persons[][] = { { 1, 2, 3, 4, 5 }, { 2, 1, 2, 3, 2, 4, 2, 5 }, { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 } };
        int result[][] = new int[persons.length][2];

  // 결과값 구조 초기화
        for (int i = 0, len = result.length; i < len; i++) {
            result[i][0] = i + 1;
            result[i][1] = 0;
        }
  
  // 패턴대로 순환하며 일치 개수 체크
        for (int i = 0, len = answers.length; i < len; i++) {
            for (int j = 0; j < persons.length; j++) {
                if (persons[j][i % persons[j].length] == answers[i])
                    result[j][1]++;
            }
        }

  // 일치개수 기반하여 정렬
        Arrays.sort(result, new Comparator<int[]>() {
            @Override
            public int compare(int[] back, int[] front) {
                return front[1] - back[1];
            }
        });

  // 출력할 길이 지정하여 반환값 설정
        int length = result[0][1] == 0 ? result.length : 1;
        int[] answer = new int[length];
        for (int i = 0; i < length; i++) {
            answer[i] = result[i][0];
        }

        return answer;
    }
}

Read more →

프로그래머스 알고리즘, 소수찾기2

목표 (문제)

주어진 numbers의 각각 숫자들을 조합하여 만들 수 있는 모든 소수의 수를 반환하세요.

조건

• numbers는 길이가 1 ~ 7 인 문자열입니다.
• numbers는 0~9 까지 숫자값만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자로 조합하면 됩니다.
• 11과 011은 같은 숫자로 취급합니다.

코드

동작

오류 발생

Set<Integer> lhs = new LinkedHashSet<Integer>();

public int solution(String numbers) {
    makeCombination("", numbers);
    return getPrimeCount(new LinkedList<Integer>(lhs));
}

public int getPrimeCount(LinkedList<Integer> numbers) {
    for (int prime : new int[] { 2, 3, 5, 7 }) {
        for (int i = 0; i < numbers.size(); i++) {
            int number = numbers.get(i);
            if (number < 2 || (number % prime == 0 && number != prime)) {
                numbers.remove(i--);
            }
        }
    }
    return numbers.size();
}

public void makeCombination(String s, String number) {
    if (number.length() == 0) {
        if (!s.equals("")) {
            lhs.add(Integer.parseInt(s));
        }
    } else {
        for (int i = 0; i < number.length(); i++) {
            makeCombination(s + number.charAt(i), number.substring(0, i) + number.substring(i + 1, number.length()));
        }
        for (int i = 0; i < number.length(); i++) {
            makeCombination(s, number.substring(0, i) + number.substring(i + 1, number.length()));
        }
    }
}

잡설

소수 구하는건 생각해냈지만 숫자조합을 도저히 생각해낼 수 없었기에 결국 찾아보게 되었다. 이곳 에서

Read more →

프로그래머스 알고리즘, H-index

목표 (문제)

int 배열값 들을 H라고 하고 전체 배열에서 조건에 해당되는 배열값의 갯수가 n이라고 할때, n값의 최대를 구하시요.

조건

• H는 n 이상
• n의 값은 1 ~ 1,000
• H의 값은 0 ~ 10,000

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {
//        int[] numbers = { 3, 0, 6, 1, 5 };
//        int[] numbers = { 0, 0, 0 };
        int[] numbers = { 22, 42 };

        System.out.println(solution(numbers));
    }

    public static int[] solution(int[] citations) {
        int answer = 0;

        //정렬위해 List 변환
        List<Integer> list = Arrays.stream(citations).boxed().collect(Collectors.toList());
        //정렬
        Collections.sort(list, Collections.reverseOrder());
        
        //X의 값이 H를 넘지않는 범위에서 순회
        for(Integer citation : list) {
            if (answer < citation) {
                answer++;
            } else {
                break;
            }
        }
        
        return answer;
    }
}

잡설

 boxed() 메서드는 int, long, double 요소를 Integer, Long, Double 요소로 변환하여 저장

Read more →