전체 글
-
JAVA 자료구조 (배열) - 주식을 사고팔기 가장 좋은 시점개발언어/JAVA 2023. 12. 22. 11:40
주식을 사고팔기 가장 좋은 시점 풀이1 - 브루트 포스로 계산 이 문제는 저점에서 사서 고점에 팔아, 낼 수 있는 최대 이익을 찾는 흥미로운 문제다. 가장 먼저 접근할 풀이법은 당연히 브루트 포스다. 처음부터O(n²)으로 사고팔고를 반복하면, 최대 이익을 산출할 수 있다. public int solution(int [] prices) { int maxProfit = 0; //구매 시점 순회 처음부터 끝까지 차례대로 반복한다. for(int i = 0; i < prices.length; i++){ //판맨 시점 순회,구매 부터 끝까지 차례대로 반복한다. for(int j = i+1; j < prices.length; j++){ // 판매 시점 가격에서 구매 시점 가격을 뺄 때 가장 높은 금액 찾기 maxP..
-
JAVA 자료구조 (배열) - 배열 파티션 ⅰCS지식/자료구조 2023. 12. 21. 15:25
배열 파티션 ⅰ 오름차순 풀이 페어의 min()을 합산했을 때 최대가 되려면 결국 각각의 min() 조합이 가급적 머야 한다는 뜻이다. 실제로 그림 7-10에서 하나씩 조합해보면 동일한 결과를 얻을 수 있다. 오름 차순으로 정렬된 상태에서 인접 엘리먼트 페어(Adjacent Elements Pair)를 만들면 가장 큰 a₁과 a₂ 페어들을 만들 수 있고 이 페어들의 min()의 합이 곧 만들 수 있는 최대 합이 된다. Pair의 min을 합하는 코드 public int solution(int [] nums) { Arrays.sort(nums); List pair = new ArrayList(); int sum =0; for(int n: nums){ pair.add(n); //페어 변수에 값이 2개 채워지..
-
JAVA 자료구조 (배열) - 세수의 합(💡투 포인터)카테고리 없음 2023. 12. 21. 14:23
세수의 합 풀이1 - 투 포인터로 합 계산 정렬한 다음에 i를 축으로 하고, 중복된 값을 건너뛰게 한 부분은 다음과 같이 풀이 #1과 동일하다. if(i > 0 && nums[i] == nums[i -1]) countinue; 중복된 값이 있을 경우 continue로 건너뛴다. left = i + 1; right = nums.length -1; while (left 0) right -=1 else{ results.add(Array..
-
JAVA 자료구조 (배열) 2 - 빗물 트래핑CS지식/자료구조 2023. 12. 21. 11:50
빗물 트래핑 풀이 1- 투 포인터를 최대로 이동 이 문제는 높이와 너비 모든 공간을 차례대로 살펴 보면 O(n²)에 풀이가 가능하다. 그러나 시간 복잡도가 너무 높기 때문에 좀 더 효율적인 풀이를 찾아야 한다. 투 포인터나 스택으로 O(n) 풀이가 가능할 것 같다. 그림 7-5에서 가장 높이가 높은 막대를 한번 살펴보자 위 그림에서는 최대 높이는 3인 곳이 가장 높은 막대이지만 최대 높이가 100이어도 관계는 없다. 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다. volume += leftMax - height[left]; ... volume += rightMax - height[rigth] 전체 중에 최대 높이 3을 기점으로 왼쪽 막대 ..
-
JAVA 자료구조 (배열) 1 - 덧셈 하여 타깃을 만들 수 있는 배열의 두 숫자CS지식/자료구조 2023. 12. 20. 15:55
풀이1 - 블루트 포스로 계산 위 문제에 대한 풀이를 한번 생각해 보자. 배열을 두 번 반복하면서 모든 조합을 더해서 일일이 확이해보는 무차별 대입 방식인 브루트 포스(Brute-Force)로 그림 7-3과 같은 방식을 떠올릴 수 있다. 이 그림에서는 정답을 찾기 위해 2부터 시작해 다른 엘리먼트들인 6,11,15를 차례대로 모두 비교한다. 즉 2 + 6, 2+ 11, 2+ 15와 같은 식으로 마지막 엘리먼트까지 모두 차례대로 더한 값을 비교해가며 정답을 찾을 때 까지 계속 진행한다. 이 방식이 바로 무차별 대입 방식인 브루트 포스로, 앞으로 문제를 풀 때 비효율적인 풀이법에서 꼭 한 번씩 첫 번째 풀이로 등장할 것이다. public int [] solution(int [] nums ,int target..
-
Java 자료 구조 - 배열CS지식/자료구조 2023. 12. 20. 12:49
배열 자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나누니다. 배열은 이 중 연속 방식의 가장 기본이 되는 자료형이다. 배열의 값은 집합으로 구성되며, 하나 이상의 인덱스 또는 키로 식별한다. 추상 자료형(Abstrac Data Type, 이하 ADT)의 실제 구현은 대 부분 배열 또는 연결 리스트를 기반으로 한다. 스택은 연결리스트로 구현하고 큐는 배열로 구현하는 식이다. 물론 반대의 경우도 충분히 가능하다. C언어를 기준으로(C는 자료구조의 가장 기본적인 형태를 소개하기에 가장 적합한 언어이다.)배열 설명을 보면, 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, ..
-
시간의 복잡도 - 빅오 (Big-O)2CS지식/자료구조 2023. 12. 19. 12:23
빅오 (Big-O) 빅오를 계산하는 실용적인 방법 한눈에 빅오를 계산할 수 있으면 가장 좋지만 사실 웬만큼 알고리즘에 익숙하더라도 헷갈릴 때가 많다. 팩토리얼(n!) 계산 같은 게 그런 예다. 다음은 팩토리얼을 재귀로 구현한 코드이다. public int factorial(int n){ if( n>= 1){ return n * factorial(n-1); }else{ return 1; } } 얼핏 봐서는 팩토리얼 계산이고 재귀도 있고 하니 시간 복잡도는 O(n!) 쯤 될거 같다. 하지만 자세히 살펴보면 재귀는 n, n-1, n - 2, ... 순으로 한 번씩만 구하면 되기 때문에 시간의 복잡도는 O(n)에 불과하다. 자칫 헷갈리기 쉬운 부분이다. 그렇다면 어떻게 하면 정확하게 계산할 수 있을까? 다음과 ..
-
시간의 복잡도-빅오(Big-O)1CS지식/자료구조 2023. 12. 19. 09:47
빅오 (Big-O)1 알고리즘은 궁극적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있기 때문이다. 파일 크기에 따른 소요시간 간단한 예를 들어보자. 디스크에 저장된 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자 여기서 교통비 드 물리적인 비용은 전혀 고려하지 않고 단순히 시간만 따진다고 해보자. 이때 파일 크기가 작다면, 즉 n이 작다면 O(n)의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다. ..