Problem Solving

    Problem Solving/백준

    [백준] 3079번: 입국심사

    3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 문제 해설 N개의 입국심사대가 있고 M명의 사람이 있을 때, 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제이다. 처음 문제를 접하면 설명을 읽고 혼란이 온다. 줄 서있는 맨 앞 사람은 특정 심사대가 비게 되면 그곳으로 이동이 가능하다고 하니 이걸 어떻게 구하나 싶어진다. 시뮬레이션을 돌려보기엔 범위들이 $1 \leq N \leq 100,000, 1 \leq M \leq 1,000,000,000$ 이기에 1초 만에 돌아갈 수 없음은 자명하다. 하..

    [백준] 23823번: 초코칩 케이크
    Problem Solving/백준

    [백준] 23823번: 초코칩 케이크

    23823번: 초코칩 케이크 첫 번째 줄에 두 정수 $n$, $q$가 공백으로 구분되어 주어진다. $(1 \leq n \leq 30,000, 1 \leq q \leq 100,000)$ $n$은 가로줄과 세로줄의 개수이며, $q$는 장식 횟수이다. 이후로 $q$개의 줄에 두 정수 $t$, $a$가 www.acmicpc.net 문제 해설 입력 받은 $a$번째 가로줄 혹은 세로줄에 초코칩을 1개씩 올릴 때마다 가장 많은 초코칩을 가지고 있는 조각의 개수를 출력하면 된다. 단순하게 2차원 배열로 생각을 하게 되면 $1 \leq n \leq 30,000$이라는 범위가 있기 때문에 int arr[30000][30000]은 메모리 초과에 시간 초과가 발생한다. 하지만 초코칩을 올릴 때 해당 줄의 모든 조각에 올린다는..

    [백준] 11660번: 구간 합 구하기 5
    Problem Solving/백준

    [백준] 11660번: 구간 합 구하기 5

    11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 해설 지금까지의 누적합은 1차원 배열이었다. 1 2 3 4 5 값이 들어있는 1차원 배열이 있다고 가정해보자. 누적합은 배열의 값들을 계속 더해가서 어디부터 어디까지의 합이 얼마인지 $O(1)$만에 알 수 있는 방법이다. 위의 배열을 누적합 배열로 변경하면 1 3 6 10 15가 된다. 이제 원래 배열에서 2번째부터 4번째까지의 합을 구하려면 15 - 3만 하면 된다. 15는 1+2+3+4+5의 결과값이고, 3은 1..

    Problem Solving/백준

    [백준] 5639번: 이진 검색 트리

    5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 해설 트리, 그것도 이진 검색 트리이다. 심지어 어떤 조건을 만족하는지 문제에서 제공해주고 있다. 문제의 입력에서는 전위 순회한 결과를 주고 있는데, 전위 순회는 현재 노드 → 왼쪽 서브트리 → 오른쪽 서브트리의 순서를 가진다. 따라서 현재 키를 기준으로 어디까지가 왼쪽 서브트리이고 오른쪽 서브트리인지만 구분하면 된다. 그런데 이진 검색 트리는 "노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다."와 "노드의 오른쪽 서브트리에 ..

    자료구조 [3]: 덱
    Problem Solving

    자료구조 [3]: 덱

    덱 (Deque) 덱이란? 큐는 한방향으로만 데이터 조작이 가능했던 반면, 덱은 양방향을 지원하는 자료구조 배열, 리스트로 구현이 가능하지만 일반적으로는 양방향 연결 리스트를 사용하므로 비교적 구현 난이도가 높음 뒤에서도 데이터 삽입 및 제거가 가능해야하기 때문 연결 리스트로 구현 시 데이터 삽입과 제거에 O(1) 배열로는 어떻게 구현해도 연결 리스트보다 시·공간복잡도 면에서 비효율적 코드 // C++ STL deque dq; dq.push_front(1); dq.push_back(2); dq.pop_front(); // 클래스를 활용한 덱 구현 template class Node { public: T data; Node *nextNode; Node *prevNode; Node(): nextNode(nu..

    자료구조 [2]: 스택, 큐
    Problem Solving

    자료구조 [2]: 스택, 큐

    스택 (Stack) 스택이란? LIFO (Last In First Out) 구조를 가지는 자료구조 배열, 리스트로 구현이 가능하지만 일반적으로는 단방향 연결 리스트를 사용 연결 리스트로 구현 시 데이터 삽입과 제거에 O(1) 배열로는 어떻게 구현해도 연결 리스트보다 시·공간복잡도 면에서 비효율적 스택으로 재귀함수를 재현할 수 있으며 재귀함수도 내부적으로는 스택을 이용 코드 // C++ STL stack stk; stk.push(1); stk.push(2); stk.pop(); // 클래스를 활용한 스택 구현 template class Node { public: T data; Node *nextNode; Node(): nextNode(nullptr) {} Node(T data, Node *nextNode)..

    자료구조 [1]: 배열, 연결 리스트
    Problem Solving

    자료구조 [1]: 배열, 연결 리스트

    자료구조란? 사전적 정의로는 "데이터들의 집합" 컴퓨터 상의 데이터를 표현하고 저장하기 위해 사용 상황에 따라 다른 자료구조를 활용하여 시간과 공간 모두 효율적인 데이터 관리가 가능 대표적인 자료구조의 종류 리스트 배열 연결 리스트 스택 큐 덱 그래프 트리 해시 테이블 배열 (Array) 배열이란? 데이터가 메모리 연속적으로 나열된 자료구조 일반적으로는 같은 종류의 데이터들이 저장됨 데이터들의 순서가 존재하기에 임의로 접근하는 것이 가능 용량(capacity)이 고정되어 있고 확장 및 축소가 불가능 코드 int arr[10]; // 10개의 정수를 연속적으로 저장할 수 있는 자료구조 cout nextNode; } Node *getBack() { Node *nowNode = head; while (nowN..

    Replit에서 백준 풀기 tip
    Problem Solving/백준

    Replit에서 백준 풀기 tip

    군대에서부터 알고리즘 문제를 풀 때 Replit을 이용했다. 채점 서버는 대부분 리눅스 기반이기에 최대한 환경을 비슷하게 맞춰야 예제 출력도 동일해지기 때문이다. 다만 Replit에는 Ideone이나 Coding Blocks IDE 같이 여타 온라인 ide에서 제공하는 Input을 미리 입력할 수 있는 기능이 없는 점이 불만이었다. 그래서 파일 입출력을 통해 미리 Input을 저장해두려고 했는데, freopen("input.txt", "r", stdin); 이 한 줄만 있으면 백준에 제출할 때마다 주석 처리하거나 지워야 하는 게 너무 번거로웠다. 이 불편함을 Replit에서 제공하는 환경변수 기능으로 해소해보자. Replit IDE의 좌측 메뉴를 보면 자물쇠 모양이 있는데 여기서 환경변수를 추가할 수 있..

    [프로그래머스] 헤비 유저가 소유한 장소
    Problem Solving/프로그래머스

    [프로그래머스] 헤비 유저가 소유한 장소

    코딩테스트 연습 - 헤비 유저가 소유한 장소 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 programmers.co.kr 문제 해설 SQL 문제는 차근차근 보는 것이 중요하다. 공간을 둘 이상 등록한 사람을 "헤비 유저"라고 부릅니다. 헤비 유저가 등록한 공간의 정보를 아이디 순으로 조회하는 SQL문을 작성 순서대로 쿼리를 작성해보자. 먼저 "공간을 둘 이상 등록한 사람"을 알아내야하는데, 이를 다르게 말하면 "사람 별로 공간을 등록한 개수가 둘 이상"이라고 할 수 있다. SQL에서 '~별로' 의미로 이용되는 문법은 GROUP BY ..

    [프로그래머스] 다단계 칫솔 판매
    Problem Solving/프로그래머스

    [프로그래머스] 다단계 칫솔 판매

    코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 문제 해설 카카오에서 트리 DP 문제를 내기 시작한 이후로 트리만 보면 시간복잡도를 확인하는 버릇이 생겼다. 문제를 보자마자 떠오르는 naive한 방법으로 계산해보자. 문제를 보아하니 seller 배열 순서대로 DFS를 돌려서 구성원마다 이익금을 분배해주면 될 거 같다. 또한 DFS는 각 정점의 부모로만 탐색하기 때문에 시간복잡도는 $O(V)$이고 이걸 seller의 길이만큼 반복하므로 최종 시간복잡도는 $O(V * N)$이다. 여기서 V는 enroll의 ..

티스토리툴바