본문 바로가기

전체 글192

28일차: 알고리즘 with Math(순열, 조합) ❯ 순열(Permutation)과 조합(Combination) 알고리즘 문제를 풀기 위해서는, 일부 수학적인 개념이 필요하다. 순열이란, 요소 n개 중에서 m개를 선택하여 순서에 상관있게 뽑는 경우의 수를 말한다. 조합이란, 순서에 상관 없이 요소 n개 중에서 m개를 뽑는 경우의 수를 말한다. 순열과 조합은 반복문의 중첩을 통해 구현할 수 있으나 뽑아야하는 경우의 수가 많아지면 반복문을 사용하는것이 비효율적이다. 따라서 재귀함수를 통해서 구현할 수 있다. 다만, 재귀함수를 작성할때는 필요한 매개변수가 어떤것이 있을지 잘 생각해보는것이 중요하다. (재귀함수를 재호출하면서 변수가 초기화 되지 않도록) 순열을 사용해 뽑은 숫자 중 소수 개수 계산하기 import java.util.ArrayList; // n .. 2023. 3. 24.
27일차: 알고리즘(Greedy, Brute-Force, Binary Search) ❯ Greedy 알고리즘 탐욕 알고리즘이라고도 하며, 선택의 순간마다 최적의 선택을 해서 해답에 도달하는 방법을 말한다. 1. 선택 : 현재 상태에서 최적의 해답 선택 2. 적절성 검사 : 선택된 답이 문제 조건을 만족하는지 검사 3. 해답 검사 : 원래 문제가 해결되었는지 검사하고, 해결이 되지 않았으면 다시 선택단계로 돌아가서 반복함 1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후 선택에 영향을 주지 않아야한다. 2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결방법은 부분 문제에 대한 최적 해결방법으로 구성된다. ❯ Brute-Force 알고리즘 (완전 탐색) 모든 값을 대입하여 올바른 값을 찾는 방법. 모든 경우를 시도해.. 2023. 3. 22.
알고리즘 - Blob 크기 구하기(재귀) 특점 지점에서 시작해서 연결되어있는 Blob의 크기가 얼마인지 구하는 메서드 이다. 문제를 작게 쪼개어서 보는것이 중요하다. public class CountCells { public static void main(String[] args) { System.out.println(countCells(1, 1)); } // 결과값은 17 private static int N = 8; private static int[][] grid = { {0, 0, 0, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 1, 1, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 0, 0, 0, 1, 0, .. 2023. 3. 22.
알고리즘 - 미로 출구찾기(재귀) int[][] 로 정의된 미로에서 특정 출발점에서 탈출 경로가 있는지 확인하는 메서드이다. 고려해야할 사항은 해당 경로의 방문여부와 해당 경로의 이웃한 칸들의 탈출 경로 유무이다. (재귀를 통해서 확인) 재귀는 탈출(종료) 조건을 지정해주는것이 중요하다는것을 다시한번 알 수 있는 코드였다. public class MazeCase { public static void main(String[] args) { System.out.println(findPath(0, 0)); } // 탈출할 수 있는 경로가 있으므로 true 리턴. private static int N = 8; private static int[][] maze = { {0, 0, 0, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 1, 1,.. 2023. 3. 22.
26일차: 알고리즘(Algorithm)과 시간복잡도(Time Complexity) ❯ 알고리즘(Algorithm) 알고리즘이란, 문제를 해결하는 최선의 선택을 구하는 것을 의미한다. 이를 위해 문제를 정확하게 이해하고, 어떻게 해결할지 전략을 수립하고, 수립한 전략을 실제 코드로 작성할 수 있어야한다. 알고리즘 문제 풀이를 위해서는 의사코드(PseudoCode)를 잘 작성하는것이 중요하다. 자연어(혹은 프로그램언어)를 사용하여 프로그램 작동 논리를 작성하게된다. 의사코드를 구체적이고 논리적으로 작성해야 코드 작성시 시간이 단축되고 디버깅이 용이해진다. ❯ 시간 복잡도(Time Complexity) 이때까지 문제 풀이 혹은 기능 구현만 신경써서 연산 수행시간은 전혀 고려하지 않았다. 시간 복잡도란, 프로그램 입력값과 연산 수행시간의 상관관계를 나타내는 척도로 입력값의 변화에 따라 연산을.. 2023. 3. 21.
문자열을 요소로 갖는 배열의 가장 긴 글자, 작은 글자 제거하기 문제 자체는 아주 간단했는데, 처음 풀이 방향을 잡을때 놓친 부분때문에 한참을 헤맨 문제이다. String 타입의 요소를 갖는 배열에서 가장 길이가 짧은 문자열과 가장 길이가 긴 문자열을 제거한 배열을 리턴하는 메서드를 작성하는 문제였다. List를 사용한 방법과 arraycopy를 사용한 방법 두가지로 작성했는데, 동일한 부분을 놓쳐서 정답이 맞기도/틀리기도한 결과를 계속 냈다. public static String[] removeExtremes(String[] arr) { // --------------------------- 1안 --------------------------- if (arr.length == 0) return null; int[] lengths = new int[arr.lengt.. 2023. 3. 21.

티스토리툴바