본문 바로가기

문제 풀이262

[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.
[C++] 프로그래머스 : 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 풀이 따로 벡터를 선언해서 거기에 연산자를 넣어 DFS를 구현한 문제이다! 느낀 점 어렵지는 않았다. 근데 다른 분의 코드(코드2)를 참고해보니 내 코드가 너무나도 직관적으로 구현한 코드 같다. 다음엔 조금 더 응용을 해봐야겠다. 코드1 #include #include using namespace std.. 2021. 10. 8.

티스토리툴바