본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘-PS] 1초의 시간동안 CPU가 연산할 수 있는 크기.(알고리즘 문제 풀이에 시간 복잡도 계산하는 방법) PS를 하다 보면 입력 N에 대한 크기와 시간 복잡도의 관계를 적절하게 잘 파악해야 해당 문제에 어떤 알고리즘이 적합할지를 알 수 있다. 오늘은 시간 복잡도의 세세한 내용보다는 실전 PS 파트 이므로 PS에서 시간 복잡도가 어떻게 계산 되는지 정리를 해 보겠다. 위는 백준의 문제중 일부를 발췌 했는데, 위의 문제 시에 어떤 방식으로 시간 복잡도가 계산 되는지 말 해보겠다. CPU의 1초간 연산 속도 Cpu는 1초간 약 1억의 수를 연산할 수 있다고 가정하고 문제를 접근하는 것이 좋다. 그리고 입력 N에 대해서 시간 복잡도가 O(n) 이라면 입력 N은 0 2020. 3. 20.

[알고리즘-이론]그래프의 검색 알고리즘 - DFS(Stack)와 BFS(Queue) 그래프 자료구조에서 노드의 Data를 검색하는 방법에는 여러 방법이 있겠지만 대표적인 DFS, BFS를 학습해보자. 그래프 그래프란? 위와 같은 모습으로 노드들 간의 관계를 간선으로 연결 혹은 비연결 되어있는 자료구조 이다. 지금은 자료구조에 대한 설명을 하는 시간이 아니므로 넘어가서 바로 그래프의 검색 알고리즘을 알아보자. Depth-First-Search(DFS) 깊이 우선 검색인 DFS는 Inorder Preorder* Postorder 과 같은 것들이 포함되며 시작 노드에서부터 해당 노드의 자식 노드로 끝까지 내려가며 검색하는 방식을 뜻한다. Breath-First-Search(BFS) 넓이 우선 검색인 BFS는 시작 노드에서 자신의 형제노드 (Level) 단위로 검색하는 방법을 뜻한다. DFS와.. 2020. 3. 1.

[알고리즘-백준(DP)] 백준 2748(DP), 10870(Recursive) 피보나치의 수 차이 이번 포스팅에서 동적 프로그래밍(DP, 동적 계획법, 메모이제이션 풀이) 에 대한 간단한 정의와 문제 풀이를 해볼 것이다 동적 계획법에 대한 깊은 이해와 이론적 설명은 추후에 알고리즘 이론 에서 다루기로 하겠다. 동적 계획법이란? 피보나치 수열을 동적 계획법에 표현을 하곤 한다. 동적 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하려는 문재 해결 전략이다. 이는 분할 정복과 특정 문제의 재귀 호출 비슷한 개념이지만 가장 큰 차이점은 메모이제이션(Memoization) 을 하느냐 안 하느냐에 따라 달렸다고 한다. Memoization 메모제이션이란, DP에서 작은 문제들이 해결될 때 해당 결과를 저장하여 다른 부분의 동일한 계산에, 저장된 결과를 사용하는 것을 뜻한다. 메모이제이션을 효과적으로 설명하기 .. 2020. 3. 1.

[알고리즘-백준(정렬)] 백준 11650번 좌표 정렬하기 자바 문제풀이.(Comparable을 이용한 객체 비교, 2차원 배열 정렬) 문제 입력 및 출력 예시 문제 이해 이 문제가 우리를 통해 확인하고자 하는 개념은 두 가지의 필드를 묶어서 비교를 할 수 있느냐 이다. 이 문제는 두개의 해결 방법으로 가능하다. 2차원 배열로써의 풀이 객체를 이용하여 comparable을 이용한 풀이. 문제 해결 접근 객체를 이용해서 정렬 객체를 생성해서 객체의 정렬 방식을 재정의 하는 방식으로 문제를 해결 할 수 있을것 같다. 소스 코드 package algorithm.class04_Sort; import java.util.*; public class Prob08_CoordinationSort { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n .. 2020. 2. 24.

[알고리즘-백준(정렬)] 자바 1181번 단어 정렬 문제풀이. (Comparator을 이용하여 정렬 기준 변경) 문제 입력 및 출력 예제 문제 이해 문제에 바로 조건에 따라 정렬하는 프로그램을 작성하시오 라는 말이 있기 때문에 이 문제는 정렬 문제로 분류하여 푼다. 하지만 정렬 기준이 두 가지로 나뉜다. 길이가 짧은 것 부터 길이가 같으면 사전순으로 중복 제거 지금까지 우리가 정렬을 할 때 int의 오름차순 혹은 내림차순 정렬을 했지만 이 문제는 특이하게 문자의 길이를 요구하므로 해당 요구조건을 만족시키기 위해서는 Comparator 인터페이스를 이용해서 해결해야 한다. comparator comparator의 알고리즘 문제풀이 사용법 을 통해서 사용법을 숙지하시고 오는것도 방법이에요 :) 문제 해결 접근 길이가 짧은 순으로 정렬 을 수행할 때는 str.length() 를 이용하여 수행 길이가 같으면 사전순 정렬 .. 2020. 2. 24.

[알고리즘 문제 풀이 스킬] 자바 에서 Comparator, Comparable 로 정렬 기준 바꾸기 (람다를 이용해서 깔끔하게 재정의하기) Java에서 comparable로 정렬 기준 바꾸기 [Java 심화] Java 에서 Comparable로 정렬 기준 바꾸기. Java에서 comparator로 정렬 기준 바꾸기 자바로 알고리즘 문제풀이를 하다 보면 특정 조건에 의한 정렬을 수행할 때가 있다. 기본적으로 자바에서는 정렬을 위해서 Arrays.sort() 의 static 메서드나 , Col wonit.tistory.com 자바로 알고리즘 문제풀이를 하다 보면 특정 조건에 의한 정렬을 수행할 때가 있다. 기본적으로 자바에서는 정렬을 위해서 Arrays.sort() 의 static 메서드나 ,Collections.sort()의 static 메서드를 제공하지만, 이는 기본 정렬인 오름차순 정렬을 제공하기 때문에 특정 조건에 의한 정렬(다차원 배열.. 2020. 2. 24.

이전 1 ··· 19 20 21 22 23 24 25 다음

티스토리툴바