✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺

    [자료구조] [BJ1158] 요세푸스 문제
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

    [자료구조] [BJ1158] 요세푸스 문제

    🚩 문제 설명 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net ⏱️ 시간 복잡도 ▪ 총 N명의 사람을 제거해야한다. ▪ 시간 복잡도는 O(N)이라고 볼 수 있다. ◾ 원을 그리고 있는 사람들을 스텝 순서 대로 없애는 문제 ◾ 제거되는 값을 반환한다. ✅ 입출력 N: 원을 이루고 있는 사람의 수 K: 제거되는 스텝의 수 return ➡️ 제거되는 사람의 인덱스 수를 순서대로 반환 ✔️ 예시 📑 문제 풀이 with 파이썬 (Python) import sys from collections import deque N, K = map(int, ..

    [자료구조] [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 ▪️ 이러면 시간초과가 나온다. ..

    [TC0404] [구현] 게임 개발
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/이것이 코딩 테스트다

    [TC0404] [구현] 게임 개발

    🚩 문제 설명 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 높은 메뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향 (반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향..

    [자료구조] [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 ) 이라고 볼 수도 있음. ◾ 문장이 주어지고 문장의 각 단어를 뒤집어서 출력하는 프로그램을 ..

티스토리툴바