더듬이의 헬로월드

난이도 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] =..

난이도 Bronze2 문제 https://www.acmicpc.net/problem/1152 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 주의할 점 문자열의 길이는 1,000,000을 넘지 않는다 문자열의 앞과 뒤에는 공백이 있을 수도 있다 단어는 띄어쓰기 한 개..