더듬이의 헬로월드

난이도 Silver3 문제 링크 https://www.acmicpc.net/problem/15651 문제 해결 과정 N과M(1)에서 중복을 허용하는 경우를 출력한다. 간단하다. N과M(1)에서 if문을 통해 방문했는지 안했는지에 대한 코드를 삭제해주면 중복을 허용하는 코드로 바뀐다. 출력해본다면, 이전과는 비교도 안되게 경우의 수가 많아진 것을 볼 수 있다. 백트래킹이 필요한 이유를 체감할 수 있다. 주의할 점 1.현재 경우를 모두 탐색했다면, 다음 경우의 수를 위해 꼭 방문처리를 false로 바꿔주어야 한다. 2.이상한거 삭제하지 말고, if문만 삭제하자. 이상한거 삭제하다가 큰일난다. 코드 #include using namespace std; int nm_array[9]; bool nm_isvisit..

난이도 Silver3 문제 링크 https://www.acmicpc.net/problem/15650 문제 해결 과정 N과M(1)에서 이전 숫자보다 현재 숫자가 큰 경우에만 출력한다. 저장된 배열을 확인해서 탐색 조건으로 배열에 저장된 이전 수보다 현재 탐색하는 수가 더 큰 경우를 추가한다. 주의할 점 1.현재 경우를 모두 탐색했다면, 다음 경우의 수를 위해 꼭 방문처리를 false로 바꿔주어야 한다. 2.최초의 경우에는 nm_array[0] 를 검사하므로 1보다 작은 수를 넣어주어야 한다.(최초로 0으로 초기화되니 ㄱㅊ) 코드 #include using namespace std; int nm_array[9]; bool nm_isvisit[9]; void N_and_M(int number,int digit..

난이도 Silver3 문제 링크 https://www.acmicpc.net/problem/15649 문제 해결 과정 DFS, 백트래킹 기법을 이용해서 풀었다. 사전순 출력은, 반복문을 1부터 시작하면 자연스럽게 해결된다. N_and_M 함수의 인자로 ~까지의 수, 자릿수, 현재 탐색하는 순번 을 인자로 두어 ~까지의 수까지 반복문을 진행하며, 다음 탐색 수가 방문했던 수면 PASS, 현재 탐색하는 순번이 자릿수가 될 때까지 결과를 저장했다가 출력한다. 주의할 점 1.현재 경우를 모두 탐색했다면, 다음 경우의 수를 위해 꼭 방문처리를 false로 바꿔주어야 한다. 2.뒤에 나오는 N과M 시리즈의 베이스가 되는 코드이기 때문에 깔끔하고, 잘 알아볼수 있게 짜야 한다. 코드 #include using name..

난이도 SIlver2 문제 링크 https://www.acmicpc.net/problem/11724 문제 해결 과정 반복문을 통해 1번 노드부터 노드의 개수만큼 시작 노드 로 두고, DFS탐색을 진행하였다. 시작노드가 이미 방문된 노드라면, PASS하고 아니라면 결과값에 +1을 더해준다. 반복문이 끝났을 때, 결과값을 출력한다. 주의할 점 1.간선으로 연결되지 않은, 혼자 있는 노드의 경우도 체크해 주어야 한다. 2.무방향 그래프라는 점은 잘 인지하고, 그래프를 구현해야 한다 코드 #include #include using namespace std; //구현이 비교적 간단한 DFS를 이용하였다. void DFSDFS(vector *Pvec,bool* visit,short StartNode) { //현재 ..

난이도 Silver3 문제 링크 https://www.acmicpc.net/problem/2606 문제 해결 과정 DFS, BFS와 같은 그래프 탐색 알고리즘을 이용하여 1번 컴퓨터부터 시작해서 탐색하여, 그 탐색한 횟수를 검사해, 결과를 출력하였다. BFS는 구현이 어렵고, 복잡하기 때문에, DFS를 이용해 알고리즘을 구성하였다. 주의할 점 1.출력해야 할 값은 1번 컴퓨터를 통해서 감염된 컴퓨터의 수이므로, 1번 컴퓨터는 결과값에서 제외한다. 2.재귀함수 이용 시, 방문 처리를 잘 해주어 무한 루프에 빠지지 않도록 주의한다. 코드 #include #include using namespace std; //1번 컴퓨터를 통해 감염되는 컴퓨터의 숫자 int result=0; //구현이 비교적 간단한 DFS..

난이도 Silver2 문제 링크 https://www.acmicpc.net/problem/1260 문제 해결 과정 BFS, DFS의 기본 동작을 이해하고, 함수를 제작 후, 출력 형식에 맞추어 출력하면 된다. STL의 사용이 필수! 주의할 점 1.정점이 여러 개라면, 가장 작은 노드부터 탐색해야 하므로, 정렬을 해주어야 한다. 2.동적 할당을 이용한다면, 포인터 이용과 메모리 해제에 주의하자. 코드 #include #include #include #include using namespace std; void ShowDFS(vector *Pgraph,bool *visit,short StartNode) { //재귀함수를 이용해 구현 //현재 노드를 방문처리 후, 데이터 출력 visit[StartNode] =..

난이도 Silver3 문제집 링크 https://www.acmicpc.net/workbook/view/3953 문제 링크 https://www.acmicpc.net/problem/1874 문제 해결 과정 숫자를 입력 받고 현재 스택에서 가장 높은 숫자보다 높으면, 입력받은 숫자가 될 때까지 최고치를 하나씩 늘리면서 스택에 넣어준다. 그러고 나서, 입력받은 값이 현재 스택의 top이라면, pop! top이 아니라면 NO! 주의할 점 1.문자를 한번에 입력받고 출력해야 버퍼를 덜 사용해야, 실행 시간 을 줄일 수 있다. 2.반복문 사용에 주의해야 한다. 코드 #include #include using namespace std; int main() { stack BOJstack; string result; i..

난이도 Silver3 문제집 링크 https://www.acmicpc.net/workbook/view/1406 문제 링크 https://www.acmicpc.net/problem/1406 문제 해결 과정 커서를 기준으로, 앞과 뒤 2개의 스택으로 나누어서 각 문자를 스택에 넣는다. (커서 왼쪽 스택) | (커서) | (커서 오른쪽 스택) 커서를 왼쪽으로 옮기면 왼쪽에서 하나 빼서 오른쪽에 하나 넣는다. 커서를 오른쪽으로 옮기면 오른쪽에서 하나 빼서 왼쪽에 하나 넣는다. 지울거면 왼쪽 스택에서 하나뺀다. 추가할거면 왼쪽 스택으로 추가한다! 마지막 출력시에는 커서 전 스택을 pop하고 커서 후 스택으로 push후, 커서 후 스택을 pop하며 차례대로 출력하면 된다 주의할 점 1.만약 pop할 스택이 비어있다..

Silver4 문제집 링크 https://www.acmicpc.net/workbook/view/3953 문제 링크 https://www.acmicpc.net/problem/9012 문제 해결 과정 한줄의 문자열을 입력받고, 문자 하나 하나를 검사해가며, 괄호의 첫부분, '(' 라면 스택에 적립, 끝부분 ')' 이라면, 스택에서 pop한다! 모든 문자를 점검했을때, 스택이 비어있다면, 성공 아니면 실패를 출력한다. 주의할 점 1.스택이 비어있는데 ')' 가 나온다면, 오류가 나므로, 이 경우를 잘 검사해야 한다. 코드 #include #include using namespace std; int main() { int repeat; cin >> repeat; for (int i = 0; i < repeat;..

난이도 Silver4 문제집 링크 https://www.acmicpc.net/workbook/view/3953 문제 링크 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 해결 과정 C++의 STL을 이용하여 스택을 구현하여 해결했다. stack 라이브러리의 함수들을 알고 있다면 어렵지 않게 풀 수 있었다. 주의할 점 1.pop이나 top함수 호풀시 스택이 비어있다면 오류가 발생하므로 꼭 empty를 이용해 검사하자! 코드..