Algorithms (5) 썸네일형 리스트형 [문제풀이] 백준 11653번 문제 소인수분해 오랜만에 알고리즘을 풀려고하니 생각대로 되지 않았다. (짧은 코드였지만 꽤나 오래걸렸다는 후문...) 1. 문제 목표 Case를 전달 받은 후 소인수분해하고, 소수들을 오름차순 정렬하여 출력할 것 2. 접근 방법 나누는 값을 2 부터 Case까지 증가시켜가면서, 나머지가 0으로 떨어지는 경우 리스트에 값 삽입 오름차순으로 정렬한 후 출력한다 case = int(input()) sqrt = int(str(math.sqrt(case)).split(".")[0]) resultList = list() while case != 1: for i in range(2, case + 1): if case % i == 0: case = case // i resultList.append(i) break resultList... [알고리즘] 위상정렬(Topological Sort) Concept 1) 개념 "순서가 정해져 있는 작업들의 순서를 정해주기 위해 사용하는 알고리즘." 방향 그래프(유향 그래프, Directed Graph)의 꼭짓점(Vertex)들을 방향에 거스르지 않도록 나열하는 것을 의미한다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. (시작점을 찾을 수 없기 때문) ex) 선수과목(prerequisite) 구조, 업무 일정 배치(PERT - 일정관리 평가 분석) 2) 수행 과정 ① 자기 자신을 가리키는 변이 없는 버텍스(노드)를 찾는다. ② 찾은 버텍스를 출력하고, 출력한 버텍스와 그 버텍스에서 출발하는 간선(edge)을 삭제 ③ 아직 그래프에 버텍스가 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다. 3) 시간복잡도 O(.. [알고리즘 공부] 동적계획법(Dynamic Programming) [ 컨셉 ] 1. 문제에 대한 접근 방식을 일컫는다 2. 큰 문제를 작은 문제로 나누어 해결해 나가는 것 Q. 분할정복 기법 또한 부분 문제로 나눠 해결하는 과정인데 무엇이 다르지? 부분 문제의 중복이 핵심. 부분 문제의 중복이 많이 일어나는 문제의 경우, 분할 정복은 해결에 어려움이 있을 수 있다. [ 동적계획법의 종류 ] 1. 하향식 방법 (Top-down) 재귀함수를 통해 하위 문제들을 해결해 나가는 방식 많은 중복이 발생하는 경우, 재귀적인 풀이는 효율성에 문제가 발생할 수 있다. "Memoization"을 통해 해결 된 하위 문제들을 캐싱(Caching)하여 중복을 해결하여 오버헤드를 줄일 수 있음. 2. 상향식 방법 (Bottom-up) 가장 하위의 문제부터 시작하여 순차적으로 해결해 나가는 .. [문제풀이] Python- 백준 9020문제 (골드바흐의 추측) www.acmicpc.net/problem/9020 (TMI - 너무 고통스러웠던 문제였다) 수학자 골드바흐가 제시한 추측한 유명한 미해결 문제로, 모든 짝수는 두 소수의 합으로 만들어 질 수 있다는 내용이다. 수 많은 시행착오.. (런타임 에러, 시간초과 등등)을 거쳐 해결한 방식은 아래와 같다. 더보기 [풀이 방식] 1. Size = 10000의 배열을 만든 뒤, 각 숫자가 소수인 경우와 아닌 경우를 True / False로 입력하여 구별 (소수는 에라토스테네스의 체를 활용하여 구한다) 2. 출력 될 2개의 수는 오름차순이므로, 앞자리 수가 작아야하며, 주어진 값의 절반 값에서 부터 시작하며 배열을 이용하여 점점 작은 소수를 탐색한다. (ex 10,000이라면 5,000 이하의 소수) 3. 주어진 값.. [문제풀이] JAVA - 정수 값 아스키(ASCII)코드 표의 10진수로 출력 코딩 문제를 하나씩 풀어보겠다는 결심과 동시에 기초 문제도 어려워 하는 슬픈 상황이 발생했다.... 그래서 정수 값과 아스키코드의 상호 변환 및 출력에 대해서 메모하기로 한다. 1. 정수 값(아스키 코드표의 10진수) 에서 문자로 출력 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int input = sc.nextInt(); sc.close(); String ascii = Character.toString((char)input); System.out.print(ascii); } 2. 영문자/특수문자에서 아스키 코드표의 10진수로 변환 public static void main(String[] args) { Sc.. 이전 1 다음
