자료구조

    [자료구조] [BJ10845] 큐
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

    [자료구조] [BJ10845] 큐

    🚩 문제 설명 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ⏱️ 시간 복잡도 ▪️ 명령의 수가 N개 주어진다. ▪️ 명령어의 갯수는 총 6가지 이다. ▪️ 데이터에 대한 접근은 O(N)이라고 할 수 있다. ▪️ 데이터 접근은 back이나 front ▪️ 따라서 시간복잡도는 대략적으로 O(2 x N x N)이라고 할 수 있다. ▪️ 2 x 10^10 / 10^8 = 2 x 10^2 = 200s ▪️ 이러면 시간초과가 나온다. ..

    [자료구조] [BJ1406] 에디터
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

    [자료구조] [BJ1406] 에디터

    🚩 문제 설명 ⏱️ 시간 복잡도 ▪️ 문자열의 길이가 N으로 주어진다. ▪️ 명령어의 갯수는 M으로 주어진다. ▪️ 명령어의 갯수대로 문자열을 변환해야 하므로 시간 복잡도는 O (M) 이라고 할 수 있다. ▪️ 최악의 경우를 구해보자면 O(50만) 이라고 할 수 있다. ▪️ 이는 5 x 10^5 / 10^8 = 5 / 10^3 이므로 0.005초 라고 볼 수 있다. ◾ 한 줄로 된 간단한 에디터를 구현하는 문제 ◾ 마지막에 편집기에 나타나있는 문자열을 출력해야 한다. ◾ 영어 소문자만 편집 가능하다. ◾ 최대 60만 글자 까지 입력 가능. ◾ 커서가 존재할 수 있는 곳 (즉, 길이가 L인 문자열에서 커서의 위치는 L + 1 가지 경우가 있음.) 문장의 맨 앞 문장의 맨 뒤 문장 중간 임의의 곳 ◾ 편집기..

    [자료구조] [BJ9012] 괄호
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

    [자료구조] [BJ9012] 괄호

    🚩 문제 설명 ⏱️ 시간 복잡도 ▪️ 테스트 케이스의 갯수 T가 주어진다. ▪️ 각 테스트 케이스 마다 VPS 인지 아닌지 확인 해야한다. ▪️ 괄호 문자열의 길이는 2 이상 50 이하 이다. ▪️ 시간 복잡도는 O ( T x 50 ) 이라고 볼 수 있다. ▪️ O ( N x N ) 이라고 볼 수도 있다. ◾ 괄호 문자열이란 (Parenthesis String, PS) '(' 와 ')' 로 구성되어 있는 문자열을 뜻한다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 Valid PS로 VPS 라고 부른다. ◾ 주어지는 PS 들이 VPS인지 아닌지 구분하는 프로그램을 작성하는 문제. ✅ 입출력 return ➡️ PS가 VPS인지 아닌지 YES or No로 반환한다. ✔️ 예제 1 6 (())()) (((..

    [자료구조] [BJ9093] 단어 뒤집기
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

    [자료구조] [BJ9093] 단어 뒤집기

    🚩 문제 설명 https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net ⏱️ 시간 복잡도 ▪️ 테스트 케이스의 갯수인 T가 주어진다. ▪️ 단어의 길이는 최대 20이다. ▪️ 문장의 길이는 최대 1000이다. 즉 한 문장에 있는 단어의 수는 50개를 넘지않는다. ▪️ 즉 시간복잡도는 O( T x 50 ) 이라고 볼 수 있다. ▪️ 따라서 O( N x N ) 이라고 볼 수도 있음. ◾ 문장이 주어지고 문장의 각 단어를 뒤집어서 출력하는 프로그램을 ..

    [자료구조] [BJ10828] 스택
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

    [자료구조] [BJ10828] 스택

    🚩 문제 설명 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ⏱️ 시간 복잡도 : O(N)으로 해결 가능하다. ◾ 스택을 구현하고 주어진 명령어에 따라 숫자를 반환하는 문제 ◾ 명령어 설명 push X : 정수 X를 스택에 넣는 연산이다. pop : 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size : 스택에 들어있는 정수의 개수를 출력한다. em..

    [PG42586] 기능개발
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/프로그래머스

    [PG42586] 기능개발

    https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 🚩 문제 설명 ◾ 배포되는 일수를 리턴하는 문제 ◾ 작업은 순서가 있고, 만약 전에 있는 작업이 끝나지 않으면 배포하지 못한다. ✅ 입출력 progresses : 먼저 배포 되어야하는 우선순위가 적힌 배열 speeds : 각 작업의 개발 속도 return ➡️ 배포되는 일수마다 몇 개의 작업이 배포되는가 progresses speeds return [93..

티스토리툴바