y_lime 님의 블로그

🎈 코드 예시#include using namespace std;vector v;void printV(vector &v){ for (int i = 0; i  매개변수:n: 입력 데이터의 크기 (벡터 v의 길이)r: 선택할 개수 (여기서는 3개)depth: 현재 생성 중인 순열의 깊이 (재귀 깊이)작동 원리:종료 조건:r == depth: 선택할 개수만큼 선택한 경우(현재 순열 완성) printV(v)를 호출하여 순열을 출력하고 종료재귀 호출:반복문으로 현재 depth부터 n까지 순회하며 swap을 사용하여 요소의 순서를 변경순열을 하나씩 생성한 뒤, 다시 원래 순서를 복원(백트래킹).swap을 두 번 해주는 이유ex) {1,2,3}에서 swap하여 새로운 순열 {1,3,2}를 생성하고 makePe..

순열과 조합의 사용 상황순서와 상관 O 뽑는다면 ⇒ 순열{1,2,3} 중 2개 : {1,2}, {2,1}, {2,3}, {3,2}, {1,3}, {3,1}순서를 재배치하여...~한 순서의 경우 max 값을...순서와 상관 X 뽑는다면 ⇒ 조합{1,2,3} 중 2개 : {1,2}, {2,3}, {1,3} next_permutation (C++제공)매개변수 : from(시작지점), to(끝지점 : to부분은 포함되지 않기 때문에 +1해줘야함) from ≤ 순열  오름차순으로 정렬된 배열을 기반으로 순열을 만든다.참고) prev_permutation (C++제공)내림차순으로 정렬된 배열을 기반으로 순열을 만든다.🎈 코드 예시#include using namespace std;int main(){ int..

📄 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 🏷️ 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.4 5 11 21 31 42 43 4🏷️ 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다..

BFS : Breadth-First Search (너비 우선 탐색) 이란?- 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다. - DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다. -  queue(큐)를 이용해서 구현할 수 있다. - ex) 1을 큐에 넣고 빼면서 1과 인접한 2와 3을 큐에 넣는다. (이런 방식으로 계속 반복)🏷️ 변수 설명변수와 input은 DFS 설명한것과 다를 바가 없다.https://jaslime.tistory.com/24 🏷️ 코드 예시[Parameters]int v, e; // 정점의 개수, 간선의 개수vector> graph; // 인접 리스트vector visited; // 정점 방문 여부 저장 [..

DFS : Depth - First Search (깊이 우선 탐색)그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다.넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다.stack 또는 recursive(재귀 함수)로 구현할 수 있다.🏷️ 변수 설명그래프를 구현하는 방법에는 두 가지 방법이 있다.인접 리스트 (상대적으로 효율적)인접 행렬 (직관적 but 비효율적)1. int v, ev : 정점의 개수e: 정점 사이를 잇는 간선의 개수입력받은 정보를 통해 인접 리스트와 방문 여부를 저장하는 변수의 크기를 할당할 수 있다. 2. vector> graph이중 vector를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있으며, 유동적으로 사..

📄 문제세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열..

📄 문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.여러분은 입력으로 주어진 괄호 문자..

📄 문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 🏷️ 입력첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다..

📄 문제N*M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.🏷️ 입력첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. 3 3 1 1 1 2 2 20 1 0 3 3 3 4 4 4 5 5 100🏷️ 출력첫째 줄부터 N개의 줄에 행렬 A와 B를 더한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.4 4 4 6 6 6 5 6 100 🎈 풀이N, M을 입력 받고 각각의 NxN, MxM크기의 행렬 A,B를 만든다. 우선 "N과 M은 100보다 작거나 ..

📄 문제아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다.이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다. A A B C D Da f z z 0 9 1 2 1a 8 E W g 6P 5 h 3 k x한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다. 심심해진 ..