[자료구조] 스택 (Stack)

Stack - 스택 데이터를 아래서부터 위로 쌓아 올린 것 후입선출 (LIFO) 흔히 게임에서 '?? 버프 스택을 쌓는다'라고 얘기하는 경우가 있습니다. Stack을 사전에 검색하면 무더기, 더미 혹은 쌓다, 포개지다는 뜻을 찾아볼 수 있습니다. 자료구조에서도 스택은 데이터들을 아래서부터 하나씩 쌓아둔 것을 말한다. 가장 먼저 들어온 데이터가 가장 밑에 깔리고 그 다음으로 들어오는 데이터가 점점 위로 쌓이는 구조이다. 스택의 아래는 막혀있고, 위로만 데이터가 들어오거나 나갈 수 있다. 스택 구조는 프링글스통에 비유되는 경우가 많다. 일반적인 경우 과자는 맨 위에 놓여있는 것부터 꺼내먹으며 (삭제, 팝), 꺼내놓은 과자를 다시 통에 넣어두려면 미리 들어있던 과자 위에 쌓아야 한다. (삽입, 푸시) 관련 용..

• format_list_bulleted Coding/알고리즘
• · 2023. 11. 29.
• textsms

[자료구조] 연결 리스트 (Linked List)

List - 리스트 데이터들을 정해진 순서대로 일렬로 나열한 것 리스트의 구현 방법에 따라 크게 순차 리스트, 연결 리스트로 나뉨 해당 글에서는 연결 리스트만을 다룸 원소(데이터)들을 순서대로 나열해 둔 자료구조를 '리스트'로 정의할 수 있다. 흔히 '버킷 리스트(Bucket List)', '체크 리스트 (Check List)'와 같이 1번 ~~~, 2번 ~~~ 의 형태로 정리되어 있는 것을 생각할 수 있는데, 컴퓨터의 자료구조에서도 비슷하게 작동한다. 1번 원소, 2번 원소, 3번 원소.... 와 같은 순차적으로 정의되어 있는 원소들을 하나로 묶어둔 것을 '리스트'라고 합니다. '배열'과 '리스트'는 혼동할 수 있지만 다른 개념입니다. '배열'은 자료형 (Data Type)의 이름이고, '리스트'는 자..

• format_list_bulleted Coding/알고리즘
• · 2023. 11. 26.
• textsms

[자료구조] 순차 리스트 (Sequential List, Array List)

List - 리스트 데이터들을 정해진 순서대로 일렬로 나열한 것 리스트의 구현 방법에 따라 크게 순차 리스트, 연결 리스트로 나뉨 해당 글에서는 순차 리스트만을 다룸 원소(데이터)들을 순서대로 나열해 둔 자료구조를 '리스트'로 정의할 수 있다. 흔히 '버킷 리스트(Bucket List)', '체크 리스트 (Check List)'와 같이 1번 ~~~, 2번 ~~~ 의 형태로 정리되어 있는 것을 생각할 수 있는데, 컴퓨터의 자료구조에서도 비슷하게 작동한다. 1번 원소, 2번 원소, 3번 원소.... 와 같은 순차적으로 정의되어 있는 원소들을 하나로 묶어둔 것을 '리스트'라고 합니다. '배열'과 '리스트'는 혼동할 수 있지만 다른 개념입니다. '배열'은 자료형 (Data Type)의 이름이고, '리스트'는 자..

• format_list_bulleted Coding/알고리즘
• · 2023. 11. 25.
• textsms

[BOJ 백준] 9012 - 괄호 (C++)

문제 바로가기 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 관련 알고리즘 - 해당 없음 정답 및 해설 괄호로 이루어진 문자열을 입력받아 문자열 내에서 괄호가 모두 닫히는지 확인하는 문제이다. 기본적으로 스택(Stack)이라는 자료구조를 활용하여 해결하는 문제이지만, 이번 풀이에는 간접적으로 비슷한 알고리즘을 구현하여 해결할 계획이다. 변수 N을 선언한 뒤, 문자열을 하나씩 확인하면서 '(' 일 경우 N++, '..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 25.
• textsms

[BOJ 백준] 2869 - 달팽이는 올라가고 싶다 (C++)

문제 바로가기 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 관련 알고리즘 - 수학 정답 및 해설 달팽이가 매일 이동할 수 있는 높이를 입력받아 높이 V를 올라가는데 걸리는 일수를 구하는 문제이다. 매일 높이 상승분을 구하여 간단하게 해결할 수 있는 문제이다. 이때 예제 입력 3과 같이 올라가는 높이와 미끄러지는 높이의 차이가 크지 않은 경우, 간단하게 나눗셈만으로 정답을 구할 수 없다. 마지막날 나무 막대의 정상에 올라가고나면 더 이상 미끄러지지 않기때문에, 마지막날의 상승분을 미리 이동시켜놓고 나..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 23.
• textsms

[BOJ 백준] 4153 - 직각삼각형 (C++)

문제 바로가기 https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 관련 알고리즘 - 수학 정답 및 해설 정수를 3개 입력받아서 세 정수로 이루어진 삼각형이 직각 삼각형인지 확인하는 문제이다. 직각삼각형은 가장 긴 변의 제곱이 나머지 두 변 각각의 제곱의 합과 같은지 확인하여 찾아낼 수 있다. 간단한 수학 문제이니 수식을 세워서 해결하기 간단한 문제이다. 그 전에 예제 입력으로 보아 항상 긴 변이 마지막에 올거라 생각할 수도 있겠지만 가장 긴 변을 찾아서 계산을 진행..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 23.
• textsms

[BOJ 백준] 1676 - 팩토리얼 0의 개수 (C++)

문제 바로가기 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 관련 알고리즘 - 수학 정답 및 해설 정수 N을 입력받아 N!(N팩토리얼)을 계산하여 뒤에서부터 0이 아닌수가 나오기전까지 0의 개수를 세는 문제이다. 다소 난잡하지만 끝자리에 연속된 0의 개수를 세는 문제이다. N=5 이면 5!=120으로 정답은 1, N=10 이면 10!=3628800으로 정답은 2인 것이다. N이 최대 500이기 때문에 팩토리얼값을 직접 계산해서 정답을 구하기는 불가능하다. 따라서 끝자리에 0을 만드는 요소인 10의 약수, 즉 2와 5의 개수를 세..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 20.
• textsms

[BOJ 백준] 1546 - 평균 (C++)

문제 바로가기 https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 관련 알고리즘 - 해당 없음 정답 및 해설 각 과목별 점수의 평균을 백분위로 환산하여 나타내는 간단한 수학 문제이다. 먼저 '총점/과목 수'로 평균을 구한 뒤, 최고점을 100점으로 환산해야 하기때문에 '100/최고점'을 곱하여 해결한다. C++ 더보기 #include using namespace std; int main(){ int n; double MAX=0,tot=0,sc..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 19.
• textsms

[BOJ 백준] 1436 - 영화감독 숌 (C++)

문제 바로가기 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 관련 알고리즘 - 브루트포스 정답 및 해설 정수 N을 입력받아 '666'이 포함되어 있는 숫자 중 N번째로 작은 수를 구하는 문제이다. 문제의 제한시간도 2초로 넉넉하게 주어졌고, N의 범위가 1~10000이기 때문에 브루트포스 알고리즘으로 해결하였다. 변수를 하나씩 늘려가면서 '666'이 포함되는지 여부를 체크하면서, 포함된다면 몇 번째인지 찾아 N번째 수가 나올 때까지 반복하여..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 18.
• textsms

[BOJ 백준] 1259 - 팰린드롬수 (C++)

문제 바로가기 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 관련 알고리즘 - 팰린드롬 정답 및 해설 앞뒤 어디로 읽어도 같은 단어를 팰린드롬이라 한다. 한글로는 '기러기', '스위스', '토마토' 등이, 영어로는 'level', 'eye', 'mom' 등이 팰린드롬이다. 위 문제는 숫자로 팰린드롬을 판단하는 문제인데, 문자열의 팰린드롬처럼 다루어도 좋지만 이번 문제에서는 정수를 이용한 팰린드롬 문제인 만큼 정수로 계산하도록 하겠습니다. 입력받은 정수를 일의..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 17.
• textsms

[BOJ 백준] 1181 - 단어 정렬 (C++)

문제 바로가기 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 관련 알고리즘 - 정렬 정답 및 해설 단어의 개수 N을 입력받은 다음, 입력받은 문자열을 1. 길이가 짧은 순, 2. 길이가 같으면 사전 순으로 정렬하는 문제이다. 이때 중복된 단어는 하나만 출력해야 하는데 입력단계에 발견하기 어렵기 때문에 정렬된 상태에서 중복을 체크한다 C++ 더보기 #include using namespace std; bool cmp(string s1..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 16.
• textsms

[BOJ 백준] 1018 - 체스판 다시 칠하기 (C++)

문제 바로가기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 블로그 글의 가독성을 위해 예제 입력 2까지만 포함하여 작성하였다. 본 사이트에서는 더 많은 예제가 제공되어 있으니 입출력 예제가 필요한 경우엔 위 문제링크를 클릭하시기 바랍니다. 관련 알고리즘 - 브루트 포스 정답 및 해설 검은색과 흰색으로 칠해진 보드를 받아 8x8 사이즈의 체스판을 만들려고 한다. 주어진 보드의 일부분 혹은 전체를 사용하여 항상 검은색과 흰색이 번갈아가며..

• format_list_bulleted Coding/BOJ
• · 2023. 11. 16.
• textsms