백 트래킹(Back Tracking) 한정 조건이 주어졌을 때 해를 얻을 때까지 모든 경우의 수를 검사하는 알고리즘으로 가다가 다시 돌아와서 다른 길로 간다. 모든 경우를 고려해야 하므로 재귀 함수를 이용한 DFS를 사용한다. 기본 원리 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net #include using namespace std; int n, m; int number[8]; bool ck[9]; // 중복 없이 M개를 고른 수..

브루트 포스(Brute Force) 연산이 1억회가 안 넘어갈 때 모든 경우의 수를 검사하는 알고리즘으로 완전 탐색이라고도 한다. 문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #include #include using namespace std; bool board[50][50]; int compare(int x, int y, bool white) { int cnt = 0; for (int i = 0; i < 8; i++) { f..

해시(Hash)정렬이 필요 없고 빠른 검색을 원할 때 해시를 사용한다. 문제 https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수��programmers.co.kr#include #include #include // 해시맵using namespace std;string solution(vector participant, vector completion){ string answer = "";..

1. 기본적인 정렬 알고리즘 시간 복잡도 O(n^2) 1) 선택 정렬 배열 안에서 가장 큰 원소를 찾아 배열의 맨 끝 자리와 바꾸는 방식이다. for (int i = 0; i 0; i--) f..

OSI(Open Systems Interconnection Reference Model) 7 계층 개방형 시스템 간의 데이터 통신 시 필요한 장비 및 처리 방법 등을 7단계로 표준화하여 규정했다. 일반적으로 하위 계층은 하드웨어로 상위 계층은 소프트웨어로 구현된다. 1. 물리(Physical) 계층 네트워크 통신을 위한 물리적인 표준을 정의하는 계층으로 두 컴퓨터 간의 전기적, 기계적, 절차적인 연결을 정의한다. 장비: 통신 케이블, 리피터, 허브 전송 단위: Bit 2. 데이터 링크(Data Link) 계층 인접한 개방 시스템들 간의 신뢰성 있고 효율적인 정보 전송을 제공한다. 이러한 서비스를 위해 물리적 주소(MAC) 지정, 에러 검출, 흐름 제어 등의 기능을 가진다. 장비: 브리지, 스위치 스위치:..

재귀 함수를 이용한 하노이 탑 문제 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net #include using namespace std; void hanoi(int n,..