문제 풀이/백준(BOJ)201 [C++] 백준 22942번 : 데이터 체커 https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 문제 풀이 스택으로 구현한 문제이다! 원의 중심이 x선 상에 위치해 있다는 점을 통해서 괄호를 떠올렸다. 벡터에 (좌표, 열려있는지 여부, 순서) 를 저장하게 하는데 왼쪽 좌표와 오른쪽 좌표를 따로 받아 괄호의 열린 괄호, 닫힌 괄호를 구현했다. 그리곤 정렬을 해준다. 정렬 이후 위치값이 같은걸 우선적으로 찾아준다. 앞서 위치값이 같은 게 있는지 확인했고 정렬을 했기 때문에 순서가 다른 게 온다면 false를 리턴하면 된다. 느낀 점 처음에 아이디어 자체는 금방 떠올렸다. 근데 정렬을 하는 이유와 어떻게 구.. 2021. 10. 16. [C++] 백준 2493번 : 탑 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 풀이 스택으로 풀 수 있는 문제이다. 입력받은 높이를 스택에 담고 지금 입력받은 높이가 top의 높이보다 높다면 top의 idx 값을 출력해준다. 작다면 pop을 통해서 신호를 받을 수 있는 탑의 idx를 찾는다. 신호를 받은 탑은 스택에 남겨주고, 신호를 받지 못한 탑들은 필요가 없으므로 pop 해주는 것이다. 스택이 빌 때까지 신호를 받을 수 있는 탑이 없다면 0을 출력해주면 된다. 느.. 2021. 10. 14. [C++] 백준 2800번 : 괄호 제거 https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 풀이 DFS로 문자열을 구현하면 되는 문제였다. check 함수를 통해서 백트래킹 중 일정 조건을 만족시킬 때 셋에 값을 추가하도록 한다. 사전 배열로 출력하기 위해서 set을 사용했다! 느낀 점 처음에 갈피를 제대로 못 잡아서 살짝 헤매던 문제이다. 조금 생각해보니 전형적인 백트래킹 문제였다. 또, 자료구조인 척하는데 딱히 자료구조 같지는 않다. 코드 #in.. 2021. 10. 11. [C++] 백준 2504번 : 괄호의 값 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제 풀이 괄호를 다루는 스택 문제이다! 이 문제의 가장 중요한 포인트는 2가지이다. 1. 분배 법칙 2. 계산된 값을 언제 정답에 더할지 첫 번째는 쉽다. 예제를 예로 들면 (2 + 3 * 3) * 2 가 2 *2 + 3 * 3 * 2로 계산될 수 있다는 점이다. 두 번째는 생각이 필요하다. 단순하게 닫힌 괄호가 올 때마다 정답에 더한다면 우리가 원하는 값과 다른 값을 계산한다. 닫힌 괄호가 .. 2021. 10. 7. [C++] 백준 11729번 : 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 풀이 재귀에서 가장 대표적으로 뽑히는 문제이다. 가장 기본적인 개념은 다음과 같다. 기둥은 3개로 출발 지점, 도착 지점, 임시 지점으로 나눌 수 있다. 따라서 원반을 출발점에서 도착점으로 옮기려면 3단계만 거치면 된다. 1. From -> Other 2. From -> To 3. Other -> To 이 부분을 재귀적으로 구현해주면 된다! 느낀 점 분할-정복 알고리즘에 대해서 .. 2021. 10. 7. [C++] 백준 2346번 : 풍선 터뜨리기 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 풀이 덱에 숫자와 인덱스를 pair로 저장한다. 덱의 제일 첫 번째 값을 pop 하는데 숫자 따로 저장한다. 숫자가 양수라면 pop을 먼저하기 때문에 숫자-1 만큼 오른쪽으로 회전시킨다. 반대로 음수라면 숫자만큼 왼쪽으로 회전시키면 된다. 느낀 점 그렇게 어렵지 않은 덱 문제였다. 다르게 구현해볼까 하다가 그냥 빨리 풀었다. 코드 #include #include #inclu.. 2021. 10. 4. 이전 1 ··· 14 15 16 17 18 19 20 ··· 34 다음