[ 완전탐색 문제풀이 ] 진법 변환 2 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 256 MB 19697 9940 8354 50.821% 문제 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다. 출력 첫째 줄에 10진법 수 N을 B진법으로 출력한다. 더보기 import java.util.Scanner; public class Main { ..

Chapter 4 완전 탐색 - 시뮬레이션/ Brute Force 어떻게든 답을 구한다 완전 탐색 모든 경우의 수를 시도한다. 문제해결의 가장 기본적인 방법 별도의 최적화 없이, 효율성을 고려하지 않는 풀이방법 예) 9 명의 난쟁이의 키가 주어질 때, 키의 합이 100이 되는 일곱 난쟁이를 찾아라. 9 난쟁이의 합을 구한 뒤, 두 명의 난쟁이의 키를 빼서 100이 되는 경우를 찾으면 됨 모든 경우의 수를 체계적으로 검사할 수 있도록 설계해야 한다. - 문제가 요구하는 바를 이해하고, 정확히 구현할 수 있어야 한다. 가장 쉽고 간단한 접근 효율을 생각하지 않기 대문에 문제의 크기가 작으면 유용하다. 문제의 크기가 클수록 시간/공간복잡도가 늘어나 적용이 어려울 수 있다. 완전한 정답이 되지 못하더라도 문제를..

정렬하고자 하는 값의 범위를 미리 알고있을 때 그 범위 내에서 각 값을 몇 개씩 가지고 있는지 세어서 그 정보를 기반으로 정렬을 수행하는 알고리즘 설계 정렬할 배열 : arr 정렬된 배열 : sorted_arr arr의 max 값을 구한다. max+1 길이의 배열 value_count 를 하나 선언한다. value_count 안에는 arr의 값을 index로 하는 곳에 값의 수 만큼 증가시킨다 예) arr 안에 값 3이 5개가 들어있다면 value_count[3] = 5 라는 뜻 value_count 를 for문 돌려 누적 합을 저장한다. value_count = [1,0,3,5,1] 이라면 value_count = [1,1,4,9,10] 이 된다. 여기까지 하고 이해를 돕기위해 예시를 통해 구해진 배열..

다익스트라 알고리즘이란? 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 경로를 찾는 방법으로 변형할 수 있다. 방법 1 (P[A][B]는 A와 B 사이의 거리라고 가정한다) 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A]..

함수의 점근적 분석법 : 문제의 크기(주어진 숫자)가 매우 클 때 내가 만든 알고리즘이 얼마만큼의 계산량을 요구하는가를 분석하는 것 Linear Search와 Binary Search의 비교를 예로 들면 Linear Search :어떤 값을 찾으려고 할 때 앞에서부터 순차적으로 체크하는 것 Binary Search :Array가 sorting 되어있을 때만 사용 가능. 중간값과 찾고자하는 값을 비교해서 중간값보다 찾고자하는 값이 작으면 중간값을 기준으로 왼쪽부분만 검색하면 됨 ⇒n이 증가함에따라 Linear Search 계산량도 증가하지만 Binary Search는 크게 증가하지 않는것으로 보아 이 경우에는 Binary Search가 더 효율적인 알고리즘이라고 볼 수 있다. 알고리즘 분석 알고리즘이 주어..

그래프 데이터사이에 인접한 정보를 저장하는 자료구조 노드와 노드 사이를 연결하는 엣지로 이루어진 자료 구조 방향이 있는 그래프와 방향이 없는 그래프로 구분 1. 방향이 없는 그래프(Undirected Graph) 차수 : 자신의 이웃 개수 서브그래프 : 오리지널 그래프에서 일부 edge와 노드를 구분해서 가져온 것 경로 : 두 개 이상의 노드가 서로 연결된 엣지들의 집합. 간선의 방향이 없으므로 각 노드는 양 방향으로 연결 trivial path : 노드 자신만으로 이루어진 경로 (경로가 0) 단순 경로 (simple path) : 처음과 끝을 제외하고 중복이 없는 경로 사이클 (cycle) : 시작 노드와 끝 노드가 같은 경로 단순 사이클 (simple cycle) : simple path를 만족하고 ..