코테준비 : 주요 자료구조 및 활용 방안

1. 배열 (Array)

• 순차적 데이터 저장/접근이 필요한 경우

// 시간복잡도: 접근 O(1), 삽입/삭제 O(n)
const arr = [1, 2, 3, 4, 5];

실전 응용 예제:

두 수의 합 찾기

function findTwoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

 

배열 회전

function rotateArray(nums, k) {
    k = k % nums.length;
    return [...nums.slice(-k), ...nums.slice(0, -k)];
}

2. 스택 (Stack)

• LIFO(Last In First Out) 구조가 필요한 경우

// 배열로 구현
class Stack {
    constructor() {
        this.items = [];
    }
    push(element) { this.items.push(element); }
    pop() { return this.items.pop(); }
    peek() { return this.items[this.items.length - 1]; }
}

실전 응용 예제:

유효한 괄호 검사

// 실전 예제: 유효한 괄호 검사
function isValidParentheses(s) {
    const stack = [];
    const brackets = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (const char of s) {
        if (!brackets[char]) {
            stack.push(char);
        } else if (stack.pop() !== brackets[char]) {
            return false;
        }
    }
    return stack.length === 0;
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[})")); // false

3. 큐 (Queue)

• FIFO(First In First Out) 구조가 필요한 경우

// 배열로 구현
class Queue {
    constructor() {
        this.items = [];
    }
    enqueue(element) { this.items.push(element); }
    dequeue() { return this.items.shift(); }
    front() { return this.items[0]; }
}

실전 응용 예제:

// 실전 예제: 프린터 대기열
class PrinterQueue {
    constructor() {
        this.queue = [];
    }
    
    addDocument(doc, priority) {
        this.queue.push({ doc, priority });
    }
    
    printNext() {
        if (this.queue.length === 0) return null;
        
        let maxPriorityIndex = 0;
        for (let i = 1; i < this.queue.length; i++) {
            if (this.queue[i].priority > this.queue[maxPriorityIndex].priority) {
                maxPriorityIndex = i;
            }
        }
        
        return this.queue.splice(maxPriorityIndex, 1)[0].doc;
    }
}

const printer = new PrinterQueue();
printer.addDocument("보고서", 2);
printer.addDocument("긴급공지", 3);
printer.addDocument("일반문서", 1);
console.log(printer.printNext()); // "긴급공지"

4. 해시 테이블 (Hash Table)

• 키-값 쌍의 빠른 검색이 필요한 경우

// Map 객체 활용
const hashTable = new Map();
// 또는 객체 활용
const hashTable2 = {};

기본 사용법

// Map 사용
const hashMap = new Map();
hashMap.set('key1', 'value1');
hashMap.get('key1');  // 'value1' 반환
hashMap.has('key1');  // true 반환
hashMap.delete('key1');

// Object 사용
const hashObj = {};
hashObj['key1'] = 'value1';
hashObj.key1;  // 'value1' 반환

실전 응용 예제:

중복 문자 찾기

 

function findFirstDuplicate(str) {
    const seen = new Map();
    
    for (const char of str) {
        if (seen.has(char)) {
            return char;
        }
        seen.set(char, true);
    }
    return null;
}

console.log(findFirstDuplicate("ABCDA")); // "A" 출력

 

빈도수 카운팅 (가장 흔한 활용)

function countCharacters(str) {
    const charCount = new Map();
    
    for (const char of str) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    return charCount;
}

// 사용 예시
const result = countCharacters("hello");
// Map { 'h' => 1, 'e' => 1, 'l' => 2, 'o' => 1 }

5. 연결 리스트 (Linked List)

• 동적인 데이터 삽입/삭제가 많은 경우

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

class LinkedList {
    constructor() {
        this.head = null;
    }
    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
}

 

활용 예시

- 스택/큐 구현
- LRU 캐시 구현
- 다항식 덧셈/뺄셈

6. 그래프 (Graph)

• 네트워크 구조의 데이터 표현이 필요한 경우

// 인접 리스트로 구현
const graph = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'D'],
    D: ['B', 'C']
};

 

실전 응용 예제:

// 실전 예제: 섬의 개수 세기 (DFS 활용)
function countIslands(grid) {
    if (!grid.length) return 0;
    
    let count = 0;
    const rows = grid.length;
    const cols = grid[0].length;
    
    function dfs(i, j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === '0') {
            return;
        }
        
        // 방문한 땅을 물로 변경
        grid[i][j] = '0';
        
        // 상하좌우 탐색
        dfs(i+1, j);
        dfs(i-1, j);
        dfs(i, j+1);
        dfs(i, j-1);
    }
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    
    return count;
}

const grid = [
    ['1', '1', '0', '0'],
    ['1', '1', '0', '0'],
    ['0', '0', '1', '0'],
    ['0', '0', '0', '1']
];
console.log(countIslands(grid)); // 3