1. 겪었던 문제LeetCode 문제를 풀며, 로직이 맞는 것 같은데도, 제출 시 계속 답이 틀리게 나와서, Debuging을 해보았습니다.제가 풀었던 문제는 이것입니다.문제를 안 푸셔도 알 수 있게 간단히 말씀드리면,target에 있는 값을 key = target[i], value = i 로 해서 map에 집어넣으려고 했습니다. target의 값은 다음과 같았습니다.target = [5,10,8,11,3,15,9,20,18,13]근데 System.out.println()으로 찍어보니 다음과 같이 나왔습니다!{1=3, 2=5, 3=4, 4=1, 5=0, 6=0, 8=2, 9=6, 10=1, 11=3, 13=9, 15=5, 18=8, 20=7}target에 없는 1이나 2 같은 값이 들어있던 것입니다. m..

1. 이분 탐색 (binary-search)란 무엇인가요?이분 탐색(binary-search)이란, 정렬된 상태의 일련의 데이터 중 현 기점에서 답 후보가 될 수 없는 절반을 삭제해가며 답을 찾아내는 탐색 알고리즘 이다. 다음과 같이 정렬된 10개의 정수가 배열 형태로 주어져 있다고 하자. 우리는 여기서 23이란 수를 찾고자 한다.(1) 먼저 목표값과 비교할 기준을 구해야 한다. 기준은 항상 값을 구해야 하는 구간의 중앙값이다. (짝수면은 중앙의 두 개의 값 중 앞 쪽 값이다.)(2) 16을 23과 비교해보니, 작다. 이 말은 즉 '16의 앞쪽 원소들도 목표 값보다 작다.' 는 말이 된다. 왜냐하면 이미 오름차순으로 정렬된 상태에서 탐색을 시작했기 때문이다. 따라서 16과 그 앞 쪽의 수들은 전부 날린다..

(0) 그래프란?a. 정의값을 담고 있는 정점(Vertex)와 그 정점들을 잇는 간선(Edge)으로 이루어져 있는 자료구조b. 그래프 관련 용어용어뜻정점(Vertex or Node)데이터를 저장하는 곳간선(Edge)정점과 정점을 잇는 선인접하다.정점 A와 B가 간선으로 이어져 있으면, 정점 A와 B는 서로 인접하다.라고 한다. 인접 정점: 하나의 정점 A와 간선으로 이어져 있는 정점들을 인접정점이라고 한다. 위의 예시에서 B는 A의 인접정점이다.차수하나의 정점 A와 연결된 간선의 개수이다. a의 예시에서 정점2의 차수는 3이고 정점4의 차수는 4이다. 진입 차수: 방향이 있는 그래프에서 외부로부터 들어오는 간선의 개수를 말한다. 진출 차수: 방향이 있는 그래프에서 외부로 뻗어나가는 간선의..

1. 하나의 숫자에 대한 소수 판별(1) 방법만약 소수인지 판별해야할 숫자를 N이라고 한다면, 다음과 같은 방법으로 N이 소수인지 여부를 판별할 수 있다.int N = Integer.parseInt(br.readLine());for(int i = 2; i(2) 왜 √N까지만 확인하면 되나요?'N에게 약수가 존재한다면, 약수는 곱해서 N을 만들 수 있는 각자의 짝이 존재한다. 짝이 되는 약수의 쌍을 (A,B)라 할 때, A가 √N보다 작다면, B는 √N보다 크다.'위의 성질을 이용해서, √N의 이하만 확인한다. 만약 √N 이하인 부분에서 1을 제외한 어떠한 수도 N을 나눌 수 없다면, √N 이상의 반대편에서도 N 자신을 제외한 어떤 수도 N을 나눌 수 없음이 증명된다. 따라서 N은 소수임이 판명된다.예시 ..

1. 시간 복잡도 란?(1) 개념시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.(2) 표기 방법의 종류시간 복잡도를 표기하는 방법에는 다음의 3 가지가 있다.이름설명빅-오메가 표기법문제를 풀기 위해 주어진 상황이 최선의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-세타 표기법문제를 풀기 위해 주어진 상황이 보통의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-오 표기법문제를 풀기 위해 주어진 상황이 최악의 상황일 때 필요한 연산 횟수를 나타내는 표기법예를 들어 설명1~100의 숫자가 랜덤한 순서로 저장된 배열이 주어졌을 때, 해당 배열에서 56의 INDEX를 찾아서 출력하라 라는 문제를 풀어야 한다고 하자.이때 내가 선택한 방법은 배열의 첫 번째 인덱스부터 일일히 조회이다.빅-오..

1. LIS란?LIS란 Longest Increasing Subsequence의 약자로 가장 긴 증가하는 부분 수열을 뜻한다. LIS 알고리즘 문제는 전체 수열을 주어지고, 그 안에서 가장 길고, 증가하는 부분 수열을 구해야 하는 문제들을 총칭이다. 난 부분 수열이 무엇인지부터 헷갈렸다. 따라서 먼저 수학적 배경지식을 공부하고, 마저 설명하겠다.1-1. 부분 수열이란 무엇인가? 수열은 수가 하나의 열로 나열된 형태를 뜻한다. (행군하는 군인을 떠올려보라!) 여기서 부분수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열 을 뜻한다. 만약 전체 수열 S 가 {1,2,3,4,5,6,7,8,9,10}이라면 {1}, {2,4,6,8,10}, {2,4,6}, {8,9,10} 모두 S의 부분..