[CNU SW Academy] 6일차(22.12.08.)

프로그래머스 - 프론트엔드 미니 데브코스

스택(Stack)

LIFO(Last In First Out), 바닥이 막힌 상자

push, pop, top

1. Array로 표현하기

2. LinkedList로 표현하기

 

JS에서 사용법

배열 - push, pop명령어 원래 지원

LinkedList - head를 top으로 지정

 

올바른 괄호 문제

function solution(s) {
	const stack = [];
    
    for (const c of s) {
    	if (c === '(') {
        	stack.push(c);
        } else {
        	if (stack.length === 0) {
            	return false;
            }
            stack.pop();
       	}
    }
     return stack.length === 0;
  }

큐(Queue)

FIFO(First In First Out)

빼는 것 : DeQueue, 추가 : EnQueue

 

Linear Queue

1. Array로

배열이기 때문에 빈 공간이 메꿔지지 않음 => 앞당기는 작업에 O(N)소요

2. LinkedList로

 

Circular Queue

front와 rear이 이어져 있는 queue

 

프린터

class Node {
	constructor(value) {
    	this.value = value;
        this.next = null;
	}
}

class Queue {
	constructor() {
    	this.head = null;
    	this.tail = null;
    }
    
    enqueue(newValue) {
    	const newNode = new Node(newValue);
        if (this.head === null) {
        	this.head = this.tail = newNode;
       	} else {
        	this.tail.next = newNode;
            this.tail = newNode;
        }
    }
    
    dequeue() {
    	const value = this.head.value;
        this.head = this.head.next;
        return value;
   }
   
   	peek() {
    	return this.head.value;
    }
}

function solution(priorities, location) {
	const queue = new Queue();
    for(let i = 0; i < priorities.length; i += 1) {
    	queue.enqueue([priorities[i], i]);
    }
    
    priorities.sort((a, b) => b - a);	//내림차순 정렬
    
    let count = 0;
    while(true) {
    	const currentValue = queue.peek();
        if (currentValue[0] < priorities[count]) {
        	queue.enqueue(queue.dequeue());
        } else {
        	const value = queue.dequeue();
            const += 1;
            if (location === value[1]) {
            	return count
            }
        }
    }
    return count;
}

해시 테이블

한정된 배열 공간에 key를 인덱스로 변환하여 값을 넣게 된다.

키와 값을 받아 키를 해싱하여 나온 인덱스에 값을 저장하는 선형 자료구조

삽입은 O(1), 키를 안다면 삭제, 탐색도 O(1)으로 수행

 

해시 함수의 결과가 겹친다면?  => Hash Collision

1. 선형 탐사법

충돌이 발생하면 옆으로 한 칸 이동

2. 제곱 탐사법

충돌이 발생한 횟수의 제곱만큼 옆으로 이동

3. 이중 해싱

또 다른 해시 함수 이용

4. 분리 연결법

버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가

 

Map, Set

 

---

객체지향 프로그래밍 특강 - 이성호교수님

 

자바는 동적디스패치 지원

 

추상 클래스와 인터페이스

메소드 오버로딩 : 동일한 이름의 새로운 메소드를 정의하는 것

(JS는 오버로딩 X)

- 파라미터 개수가 다르거나, 파라미터 타입이 다르거나

 

같은 이름의 함수 -> 어떤 것을 부를지는 컴파일러가 결정

컴파일러는 타입만 보고 결정한다.

 

추상클래스

추상클래스는 미완성 틀

구현이 정의되지 않은 추상 메소드를 포함한다. abstract 키워드로 정의

abstract 클래스는 선언 불가

 

인터페이스

상수와 추상 메소드만 멤버로 가질 수 있음, 오직 다른 클래스에 의해 "구현"될 목적

 

인터페이스는 인터페이스끼리 상속이 가능

하나의 인터페이스가 여러 인터페이스를 상속 받는 다중 상속도 가능

 

실제 상용 프로젝트에서 interface를 많이 사용함

 

---

프로젝트 설계, 구현 관련 특강 - 문현수 박사님

TIL(Today I Learned)

오늘 뭘 배웠는지 자료 정리, 하루하루 commit이나 posting하는

-> 팀 내에서 서로 확인하고 공유하기

 

---

코딩테스트 - 회문 확인

문제 : 회문 확인

import java.util.Scanner;

public class Main {
    static String s;
    static int n;
    static boolean result = false;
    public static void slice(int start, int end, int count) {
        if(start > end) {
            if(count > n) {
                result |= false;
            } else {
                result |= true;
            }
            return;
        }
        char a = s.charAt(start);
        char b = s.charAt(end);
        if(a==b) {
            slice(start+1, end-1, count);
        } else {
            slice(start+1, end, count+1);
            slice(start, end-1, count+1);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s = sc.next();
        n = sc.nextInt();

        slice(0, s.length()-1, 0);
        if(result) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }
    }
}

종료조건 지정하는 부분이 조금 헷갈렸다.