내맘대로 공부일기

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. 백트래킹(Backtracking)이란? 완전 탐색 알고리즘에 조건을 추가하여 가능성이 없는 부분을 탐색하지 않도록 하는 알고리즘이다. 즉, 완전탐색 알고리즘은 "모든 부분을 전부 탐색한다"이고 백트래킹을 적용시키게 되면 "가능한 모든 부분을 전부 탐색한다"가 된다. 모든 경우의 수를 탐색하는 것이 아니라 가능한 부분만 탐색을 하도록 하여 반복 횟수를 줄임으로써 속도를 향상시키는 알고리즘이다. 핵심 키워드는 "배제"와 "풀이시간 단축"이다. 이렇게 배제시키는 것을 가지치기 라고 부른다. 해당 방향으로 진행했을 경우 답이 나올 수 있는지 확인하고 나올수 없다면 진행하지 않도록 가지치기를 진행한다. 예를 들어 1~..

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import jav..

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. 브루트포스(Brute-Force)란? Brute : 짐승같은 Force : 힘 짐승같은 즉, 무식한 방법으로 확인한다는 뜻이다. 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 전 부 다 탐색하면서 조건에 충족되는 값을 도출해내는 알고리즘이다. 예를 들어 1부터 100사이의 짝수의 갯수를 구하는 문제라고 가정해보자. 하나의 변수를 1부터 시작하여 해당 숫자가 짝수인지 파악하고, 짝수라면 카운트를 올려준다. 그 후 숫자에 1을 더하고 위 과정을 반복한다. 그러다가 숫자가 101이 되면 종료하는 방식이다. 간단한 코드로 나타내면 for(i = 1; i < 101; i++){ if(i % 2 == 0) coumt+..

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import ja..

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue;..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1-1. 깊이우선탐색(DFS)란? 그래프의 탐색 방법중 하나. Depth-First Search 연결된 것들을 최대한 깊게 내려가고 더이상 못내려가면 옆으로 이동하는 탐색방식. 이게 뭔소리냐. A가 BCD랑 연결되어있다고 생각하자. A에서 B와 연결되어있다는것이 확인되는 순간 바로 B로 이동한다. 그 후 B와 연결되어있는것을 파악하고 계속 이동하다가 더이상 연결된게 없다고 판단되면 C로 이동한다. Ex) 시작점 -> 연결된 값들 기본 설정 A -> BCD B -> EF C -> K D -> Q 진행 순서 A - B - E - F - C - K - D - Q 좀더 자세히 나타내면 A - B - C - 더이상 C에서 ..

붙었습니다 ㅎ

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. LCS란? Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. Substring 말고 Subsequence맞다. Substring은 연속된 것만 가능하고 Subsequence는 연속되지 않은 것도 가능하다. Ex) 1번 : ABCDE 2번 : BCNKE 제일 긴 Substring : BC (BCNKE) 제일 긴 Subsequence : BCE (BCNDE) 2. 그럼 어떤 상황에서 LCS를 사용하나? 염기서열 유사성 분석, 음파 단어 검색 및 교정 등에 사용된다. 3. 어떻게 사용하나? 0 A B C D E 0 0 0 0 0 0 0 B 0 C 0 N 0 D 0 E 0 위와 같..

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { BufferedReader bf = new Buff..