본문 바로가기

C++105

[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++] 프로그래머스 : 행렬 테두리 회전하기 https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 문제 풀이 쉬운 편의 구현 문제이다. map[x1][y1+1]에서 값이 다르기 때문에 마지막에 추가해주는 것만 조심하면 된다. 느낀 점 처음에는 너무 간단한 구현이지만 코드가 길어서 의심을 했다. 근데 정말 저게 다다! 코드 #include #include #include using namespace std; int map[101][101]; .. 2021. 10. 12.
[C++] 백준 2800번 : 괄호 제거 https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 풀이 DFS로 문자열을 구현하면 되는 문제였다. check 함수를 통해서 백트래킹 중 일정 조건을 만족시킬 때 셋에 값을 추가하도록 한다. 사전 배열로 출력하기 위해서 set을 사용했다! 느낀 점 처음에 갈피를 제대로 못 잡아서 살짝 헤매던 문제이다. 조금 생각해보니 전형적인 백트래킹 문제였다. 또, 자료구조인 척하는데 딱히 자료구조 같지는 않다. 코드 #in.. 2021. 10. 11.
[C++] 프로그래머스 : 위클리 챌린지 (9주차) https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 문제 풀이 노드의 최대 개수가 100개이므로 전부 탐색을 하면서 간선의 길이를 구해서 따지면 된다. BFS를 통해서 간선의 최대 길이를 따지고 STL::set을 이용해서 각 노드마다 연결된 노드를 저장해준다. 느낀 점 처음에는 전혀 접근하 지를 못해서 조금의 구글링으로 도움을 받았다. 그래프 관련된 문제를 좀 더 많이 풀어봐야 할 것 같다. 코드 #include #include.. 2021. 10. 10.
[C++] 프로그래머스 : 짝지어 제거하기 https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 문제 풀이 괄호 풀기와 비슷하게 스택으로 푸는 문제이다. 비어있거나 스택의 top과 str[i] 다르면 push 하고 아니라면 pop 해준다 끝난 뒤 스택이 비어있다면 1을 반환한다. 느낀 점 처음에 문자열로 풀려고 했는데 바로 스택이 떠올라서 금방 해치웠다! 코드 #include #include using namespace std; stack s;.. 2021. 10. 9.

티스토리툴바