0과 1의 모든 기록저장소

2021년 10월 03일 일요일 16시 [백트래킹] 백준_9663_NQueen_백트래킹_골드5 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net import java.util.Scanner; public class Main { public static int[] arr; public static int N; public static int count = 0; public static void main(String[] args) { Scanner in = new ..

2021년 10월 03일 일요일 15시 [백트래킹] 백준_15649_N과M(1) _백트래킹_실버3 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.util.Scanner; public class Main{ public static boolean[] visit; public static int[] arr; public static void main(String[] args) { Scanner in = new Scanner(..

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 📌여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 출처 https://developer-mac.tistory.com/64 💡 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다. 예를 들어, 미..

이번에 살펴볼 개념은 백트래킹에 관한 내용입니다. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. Backtracking(백트래킹) 완전탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략 대표적 예 : 재귀 호출 or 스택을 통한 DFS 백트래킹의 원리 어떤 노드의 유망성을 점검 후, 유망하지 않으면 배제시킨다. = 가지치기 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축 유망성과 가지치기 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준 가지치기(Pruning) : 유망성을 따져보고, 유..

1.알고리즘(algorithm) 문제를 해결하기 위한 여러 동작들의 모임 어떤 기능이 일어나기 위해 내재된/독립된 단계적 명령어들의 집합 1) 알고리즘의 조건 입력 : 외부에서 제공되는 자료가 0개 이상 존재 출력 : 적어도 2개 이상의 서로 다른 결과 도출 명확성 : 모호하지 않은 명령어로 구성되며 수행 과정이 명확해야 함 (→ 정밀/유일성) 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내) 종료 효율성 : 모든 과정은 명백하게 실행가능(검증가능) 한 것이어야 한다. (=타당성) 2) 알고리즘 전략세우기(Pseudo-code) 일반적인 알고리즘 순서 ① 문제 정의 → ② 모델 고안 → ③ 명세 작성 → ④ 설계 → ⑤ 검증 → ⑥ 분석(복잡도 등) → ⑦ 구현 → ⑧ 테스트 → ⑨ 문서화..

2021년 10월 03일 일요일 14시 백준_11729_하노이탑_재귀_실버2 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static StringBuilder sb = new StringBuilder(); public..

2021년 10월 02일 토요일 12시 백준_10870_피보나치수 5_재귀_브론즈2 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net -> Bufferedreader 연습 -> 기본적인 구현문제 -> 어렵지 않다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Mai..

2021년 10월 02일 토요일 12시 백준_10872_팩토리얼_재귀_브론즈3 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net -> Bufferedreader 연습 -> 기본적인 구현문제 -> 어렵지 않다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { //Scanner sc = new Sc..

2021년 10월 02일 토요일 10시 백준_17472_다리만들기2 삼성 SW A형 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; impor..

2021년 9월 25일 토요일 13시 백준_17471_개리멘더링_ 삼성 SW A형 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; im..