오초의 기록 오초의 기록

[백준 1920] 수 찾기문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.출력M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.예제 입력 154 1 5 2 351 3 7 9 5예제 출력 111001 접근 방법arrM 배열의 값이 arrN 배열에 있는지 ..

이진 탐색 / 이분 탐색 (Binary Search) 정의정렬 되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법선형 탐색제일 앞에 원소 2부터 하나씩 차례대로 확인하는 것22를 찾으려면 0 → 1 → 2 → 3 → 4 → 5 → 6O(N)이분탐색범위를 절반으로 줄여나가는것22를 찾으려면 0 → 5 → 6O(log N) : N이 커지면 커질수록 둘은 아주 큰 속도의 차이가 남구현M개의 수에 선형 탐색을 한다면 : O(NM)이여서 시간초과가 발생한다.배열을 정렬해준 다음에 이분 탐색을 수행하면 O(NlogN + MlogN)NlogN : 정렬에 필요한 시간복잡도MlogM : 이분탐색에 필요한 시간복잡도배열의 시작 : st, 끝 :..

위상 정렬(Topological Sort)개념방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬BFACED는 잘못된 위상 정렬의 예시사이클이 존재하지 않는 방향 그래프(DAG, Directed Acyclic Graph)에서만 잘 정의된다. 구현제일 앞에 오는 원소로 가능한게 무엇인지 먼저 생각할 것제일 앞에 오기 위해서는 자신보다 앞에 위치한 정점이 하나도 없어야 한다 = 자신에게 들어오는 간선이 없어야 한다. = (indegree = 0)B는 A가 앞에 나와야지 나올 수 있음을 뜻한다. 그렇기 때문에 B는 제일 앞에 올 수 없다.위상 정렬 결과 - A C D G E B F 구현의 편의를 위한 성질정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 ..

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다 위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다. "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다. "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다. "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우..

N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다. 10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다. 이렇게 게임을 진행할 경우, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, … 순으로 숫자를 말하면 된다. 한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는 0,..

깊이 우선 탐색(DFS) DFS는 가능한 모든 경로(후보)를 탐색합니다. 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다. N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능합니다. 백트래킹(Backtracking) 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴본다. 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다. 가지치기 : 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 백준 14888번. 연산자 끼..

조합 서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수 (1) 중복 없이 (2) 고르기 ex) 조합은 순서가 없으므로 [1,2] 와 [2,1]을 같은 것으로 취급한다. 백준 15650번. N과 M(2) 조건 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 풀이 방법 재귀 사용(백트래킹) Scanner + StringBuffer 현재 선택한 원소 이후의 것들을 선택 가능하므로 start 변수를 +1씩 해서 넘겨준다. import java.util.Scanner; public class Main { static int N, M; static int[] out; static boolean[] visited; static StringBuffer sb = new St..

중복 조합 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수 (1) 중복을 허용해서 (a) 고르기 ex) 조합은 순서가 없으므로 [1,2]와 [2,1]은 같은 것으로 취급한다. 백준 15652번. N과 M(4) 조건 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 풀이 방법 재귀 사용(백트래킹) Scanner + StringBuffer 현재 선택한 원소를 포함하여 그 뒤의 것들을 선택 가능하므로 start 변수에 i를 담아 넘겨준다. import java.util.Scanner; public class Main { static int N,M; static i..