본문 바로가기
반응형

Computer Science86

[백준 10799번] 쇠막대기 (C++, Python) 이번 포스트에서는 백준 알고리즘 문제인 쇠막대기 를 리뷰하겠습니다. 해당 문제는 solved.ac 기준 실버 2에 위치한 문제입니다. 먼저 문제입니다. 쇠막대기와 레이저의 배치를 나타내는 String이 입력으로 주어집니다. 이때, 레이저는 여는괄호와 닫는괄호의 쌍으로 표현되고, 쇠막대기는 왼쪽 끝이 여는괄호, 오른쪽 끝이 닫는괄호로 표현됩니다. 그 결과, 잘려진 쇠막대기의 조각 개수를 구하는 문제입니다. 이 문제는 다음과 같은 알고리즘으로 해결합니다. 먼저 스택이 공백이 아닌 경우입니다. 쇠막대기의 왼쪽 끝을 의미하는 여는괄호가 인식될 때, 결과값을 1 증가시키고 스택에 1을 PUSH 합니다. (왼쪽 끝으로 막대기 1개가 있다고 가정) 직전 문자가 여는괄호이고 현재 문자가 닫는괄호라면, 스택에서 POP .. 2023. 9. 19.
[백준 9012번] 괄호 (C++, Python) 이번 포스트에서는 백준 알고리즘 문제인 괄호 문제를 리뷰하겠습니다. 이 문제는 solved.ac 기준 실버 4에 위치한 문제입니다. 먼저 문제입니다. 테스트 케이스 개수인 T를 입력받고 T개의 괄호 문자열을 입력받습니다. 이때, 주어진 괄호 문자열이 올바른 괄호 문자열인지 판별하여 "YES" 혹은 "NO"를 출력하는 문제입니다. 올바른 괄호 문자열을 만들려면 다음과 같은 조건들이 있습니다. 여는괄호 로 시작하여야함. 닫히지 않은 괄호가 1개라도 있을 때 닫는괄호 사용이 가능함 닫는괄호와 여는괄호의 개수가 같음 따라서, 위 조건을 스택의 원리에 빗대어 생각해보면 여는 괄호는 PUSH 연산을 수행하고, 닫는 괄호는 POP 연산을 수행합니다. 1번 조건은 스택이 공백일 때 POP 연산을 할 수 없다 고 정의할.. 2023. 9. 15.
[백준 1021번] 회전하는 큐 (C++, Python 3) 이번 포스트에서는 백준 알고리즘 문제인 회전하는 큐에 대해서 리뷰하겠습니다. solved.ac 기준 실버 3에 위치한 문제입니다. 먼저 문제 입니다. 문제에서 N개의 원소를 가지는 양방향 순환 큐와 뽑아내려는 수의 개수 M을 입력받습니다. 다음으로 M개의 뽑아내려는 원소의 인덱스 위치를 입력받습니다. 이때, 원소를 뽑아내기 위해 큐를 왼쪽 혹은 오른쪽으로 이동하는 연산이 몇번 수행되는지 출력하는 문제입니다. 큐를 왼쪽, 오른쪽으로 회전하기 위해선, 큐의 앞 혹은 뒤에서 원소를 빼서 반대쪽으로 삽입하는 연산이 필요합니다. 따라서, 이 문제는 덱 자료구조를 활용하여 문제를 해결합니다. 해당 문제는 다음과 같은 순서로 풀이합니다. 큐의 크기 N과 뽑아내려는 수의 개수 M을 입력 받습니다. 덱에 1~N의 숫자를.. 2023. 9. 14.
해쉬테이블의 구현 이번 포스트에서는 해쉬테이블의 대한 내용과 그 구현에 대해서 설명하도록 하겠습니다. 해쉬테이블 해쉬테이블이란, 해쉬함수에 기반하여 키, 값의 쌍을 저장하는 자료구조 입니다. 삽입, 삭제, 탐색의 연산을 평균적으로 O(1)의 시간복잡도로 처리할 수 있고, 최악의 경우 O(n)의 시간복잡도가 소요됩니다. 키, 값의 쌍을 저장하는 경우 사전의 표현이 가능하고, 키만 저장하는 경우 집합의 표현이 가능합니다. 여기서 말하는 사전이란, 키와 값의 쌍들의 모음을 다루는 추상자료형으로 삽입, 삭제, 탐색의 연산이 가능합니다. 해쉬함수 해쉬함수란, 키를 입력으로 받아 해쉬테이블 내 키와 값이 저장될 위치 인덱스를 출력해주는 함수입니다. 이때 출력 값을 보통 해쉬 값, 해쉬 코드 등으로 부릅니다. 하지만, 해쉬함수를 거쳐.. 2023. 9. 12.
반응형

티스토리툴바