BOJ157 [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. [C++] 백준 10799번 : 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 풀이 입력받은 string의 크기만큼 반복문을 돈다. '(' 다음에 바로 ')'에 오면 레이저 처리라는 것이 중요하다. 스택이 비어있거나 string[i]가 '(' 일 경우 '('을 스택에 넣어주고 막대기의 개수를 +1 해준다. 만약 string[i+1]이 ')'라면 레이저 처리하므로 막대기의 개수만큼 조각 수에 추가한다. 레이저 처리일 경우 다다음 인덱스로 넘어가야 하므로 인덱스를 +1 해준다. st.. 2021. 10. 4. 이전 1 ··· 14 15 16 17 18 19 20 ··· 27 다음