* 다음 포스팅의 모든 내용은 BaaaaaaaaarkingDog 님의 [실전 알고리즘] 0x0B강 - 재귀 강의를 공부한 뒤 개인적인 공부 용도로 간략하게 요약하여 정리한 글 입니다. 자세한 내용은 아래 바킹독님의 블로그에서 확인해 주세요. BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹 (encrypted.gg) [실전 알고리즘] 0x0C강 - 백트래킹 이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는 blog.encrypted.gg #1 백트래킹 #1.1 BOJ15649 N과M(1) #1.2 BOJ9663 N-Queen [미완성] #1 백트래킹 ..
#INFO 난이도 : GOLD4 문제유형 : 재귀 출처 : 2448번: 별 찍기 - 11 (acmicpc.net) 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net #SOLVE 같은 패턴이 반복되는 재귀 유형 알고리즘 문제이다. 가장 기본이 되는 삼각형의 규칙을 찾아 base condition으로 설정한 뒤, 삼각형 각각의 좌표를 fill_star(배열에 알맞은 *을 채워 주는 함수)의 파라미터로 보낸 뒤 재귀로 호출하여 풀이하였다. void fill_star(int x, int y){ board[x][y] = '*'; board[x+1][y-1] = '*'; b..
* 개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있습니다. 출처 : 해킹 입문자를 위한 TCP/IP 이론과 보안 2/e #1 ARP 캐시테이블 #2 ping 8.8.8.8 분석 #3 DNS 캐시테이블 #1 ARP 캐시테이블 ARP(Address Resolution Protocol)는 IP주소와 맥주소 사이를 연결해 주는 기능을 수행하는 중요한 프로토콜이다. cmd창에 arp-a 명령어를 치면 아래와 같이 IP주소와 맥 주소의 대응 관계를 저장한 테이블이 출력되는데, ARP 캐시 테이블(ARP Cache Table)이라고 부른다. 이는 마치 IP주소와 도메인 네임의 관계를 관리하는 DNS서비스와 유사한 형태이다. ping 8.8.8.8 명령어를 입력한 뒤 동작 과..
#INFO 난이도 : SILVER2 문제유형 : 백트래킹 출처 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net #SOLVE i번째 수를 더할지 말지 정한 뒤 i+1번째 수를 정하러 들어가는 방식으로 풀이했다. {-3, -2, 5} 수열을 예시로 들어보도록 하자. 왼쪽은 현재 수를 더하지 않는 케이스 오른쪽은 현재 수를 더하는 케이스이다. 아래 그림과 같이 백트래킹 방식을 이용해 모든 경우를 탐색한 뒤 합이..
#INFO 난이도 : SILVER3 문제 유형 : 백트래킹 출처 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #SOLVE 백트래킹 N과 M시리즈 4번째 문제이다. 문제의 조건은 수열을 사전 순으로 증가하는 순서로 출력해야 한다. st(시작)변수를 이용해 조건문을 작성하여 가지치기를 수행하면 풀리는 간단한 문제이다. int st = 1; if(k != 0) st = arr[k-1]; for(int i = st; i