본문 바로가기

분류 전체보기102

QuickSort (퀵 정렬) 퀵정렬은 Merge Sort와 마찬가지로 Divide and Quenquer(분할정복) 방식으로 접근해볼 수 있다. 분할 : 배열을 특정 값(= Pivot)을 기준으로 pivot 보다 작은 부분, 큰 부분으로 나눈다. 정복 : 각 부분을 순환적으로 정렬시킨다. 합병 : 퀵정렬은 합칠게 없다. 쉽게 말하자면 1. 어떤 배열이 존재할 때, 배열의 첫번째 값이나 마지막 값을 pivot으로 선택한다. (여기서 pivot을 선택하는 것에 대해서는 뒤에서 더 자세하게 이야기 하겠다) 2. pivot을 기준으로 왼편에는 작은 값들이 위치하게 하고 큰 값은 오른쪽에 위치하게 시킨다 (이 때 각 값들은 정렬될 필요가 없으며, 오름차순,내림차순에 따라 오른쪽,왼쪽은 바뀔 수 있다) -> 이러한 행위를 Partition 이.. 2022. 4. 16.
재귀함수 공부...(feat. Counting Cells in a Blob) 문제는 https://www.youtube.com/watch?v=HHJFlVT1tBw 요기에 있다. 이번에는 그냥 문제만 보고 풀어봤다. 이전 미로문제처럼 비슷하게 풀면되겠거니 생각해서 처음 코드를 짰을 때는 뭔가 base 부분이 이상했다. 어떻게 코드를 시작했냐면 아래와 같이 시작했다. public static boolean recur(int[][] board, int x, int y, boolean prev) { if (x = board.length || y = board.length || board[y][x] == 1) { return false; } else if (board[y][x] == 0) { ... return true; } ..... } 이럴 경우 맨.. 2022. 4. 12.
재귀함수 공부하기.. (feat. 미로찾기) 재귀함수를 공부하는데 유튜브의 권오흠교수님의 강의를 보면서 공부를 했다. 재귀함수를 만들려면 노하우가 암시적 매개변수를 명시적 매개변수로 바꾸라! 라고 하셨다. 이번 미로 찾기 문제는 미로가 주어지고 거기까지의 경로를 구하는 문제였는데, 힌트 한번보고 재밌게 풀었다.. import java.util.Stack; public class Test { public static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public static void main(String[] args) { boolean[][] board = {{true,true,true,true,true,true,true,false},{true,false,false,true,false.. 2022. 4. 12.
Format 함수에서 %02s 시 FormatFlagsConversionMismatchException 발생하는 이유 https://docs.oracle.com/javase/7/docs/api/java/util/Formatter.html Formatter (Java Platform SE 7 ) 'e' '\u0065' Requires the output to be formatted using computerized scientific notation. The localization algorithm is applied. The formatting of the magnitude m depends upon its value. If m is NaN or infinite, the literal strings "NaN" or "Infinity", resp docs.oracle.com 보통 Format함수 쓸 때는 %[flags][.. 2022. 4. 8.
프로그래머스 : 베스트 앨범 이런 문제 너무 재밌다.. 제로베이스 연습문제였는데 이렇게 따로 클래스를 선언해서 풀었다. 따로 클래스에서 처리해줄거 처리해주니 편하게 로직을 작성할 수 있었다. 아래는 그냥 일반 실행용 코드 import java.util.*; class Music { private int id; private int num; public Music(int id, int num) { this.id = id; this.num = num; } public int getId() { return id; } public int getNum() { return num; } } class Genre { private int total = 0; private ArrayList musics = new ArrayList(); privat.. 2022. 4. 7.
자바 8 람다를 이용한 다중 조건 정렬 import java.util.Arrays; import java.util.Comparator; import java.util.List; /** * [ Lambda 의 기본 틀 ] * Predicate : (T -> boolean) -> 주로 필터에 사용 * Supplier : (() -> T) -> 만드는놈(객체 생성) * Consumer : (T -> void) -> 쓰는놈(실행에 사용) * Function : (T -> R) -> From 에서 뭔가를 To 로 만들어 넘김 */ public class Main { public static class Apple { private String color; private Integer weight; public Apple() {} public Apple(.. 2022. 4. 7.
백준 1874번 : 스택 수열 맞게 푼 것 같고 답도 잘나오는데 자꾸 실패가 떴다. import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); ArrayList list = new ArrayList(); for (int i = 0; i < n; i++) { list.add(sc.nextInt()); } solution(n,list); } public static void solution(int n, ArrayList list) { int lCnt = 0; int pCnt = 1; // pop한 회수, 절대 n+1만큼 넘어갈 수 없다. Stack stack =.. 2022. 4. 7.
백준 3190 : 뱀 제로베이스 강의에 연습문제로 있길래 그냥 하드코딩으로 풀었는데 백준에 있는 문제였다.. 시간이 좀 걸렸지만 게임만드는 것 같아서 재밌게 풀었던 것 같다. 그리고 확실히 세세하게 필요한 기능을 나눠서 구현한 후 순서에 맞게 조립하니까 잘 풀어진 것 같다. 문제 설명 --- 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은.. 2022. 4. 7.
MxN 행렬 데이터의 특정 원소의 행,열 모두를 변경하기 정수로 이루어진 M x N 행렬 데이터가 있다고 하자 행렬의 원소 중에 0이 있을 경우 해당 원소가 위치하는 행,열 전체 데이터를 0으로 변경하는 코드를 작성하라. 제로베이스 문제 풀이에서는 다르게 풀었지만 boolean써가면서 푸는게 이해가 잘 안되서 그냥 내 식대로 풀어봤다. import java.util.*; import java.util.stream.IntStream; class Main { public static void main(String[] args) { int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}; solution(matrix); System.out.println(); matrix = new int[][]{{1,1,0},{1,1,1},{0,.. 2022. 4. 6.
해시 테이블 (Hash Table) Hash Table 이란? - key 와 value를 대응시켜 저장하는 데이터 구조 키를 통해서 해당 데이터(value)에 빠르게 접근할 수 있다. - 해싱 키를 특정 계산식(해시 함수)에 넣어 나온 결과를 사용하여 값에 접근하는 과정 구조 - 키 해시 테이블에 접근하기 위한 입력 값 - 해시 함수 키를 해시 값으로 매핑하는 연산 - 해시 값 해시 테이블의 인덱스 - 해시 테이블 key - value를 연관시켜 저장하는 데이터 구조 해시충돌 서로 다른 키인데도 해시함수를 통한 해시 값이 동일한 경우, 이를 해시충돌 이러한 경우 해결방법으로 두가지가 있다. - 개방 주소법 (Open Address) 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장하는 방법 hash와 value가 1:1.. 2022. 4. 6.
데크 (Deque) 데크란? 양쪽에서 삽입과 삭제가 모두 가능한 자료구조를 뜻한다. - Deque : Doubly-ended Queue - Stack + Queue 의 형태 기본 구조 - addFirst(), removeLast() 등 first,last로 메소드가 구분되어 진다. Deque 종류 기본적으로 양쪽 입출력 가능한 Deque에서 부분적으로 제한해 가면서 쓸 수 있다. 입력 제한 데크 ( Scroll ) 한 쪽의 입력을 제한한 데크, 출력은 양쪽으로 가능하다. 출력 제한 데크 ( Shelf ) 한 쪽의 출력을 제한한 데크, 입력은 양쪽으로 가능하다. 예시 import java.util.*; class Main { public static void main(String[] args) { Deque deque = n.. 2022. 4. 6.
선형 자료구조 - 연결 리스트(Linked List) - 정의 데이터를 링크로 연결해서 관리하는 자료구조 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음 - 장점 데이터 공간을 미리 할당할 필요가 없음 -> 리스트의 길이가 가변적이라 데이터 추가/삭제 용이 - 단점 연결구조를 위한 별도 데이터 공간 필요 연결 정보를 찾는 시간이 필요(접근속도가 상대적으로 느림) 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요 - 기본 구조 노드 : 데이터 저장 단위로 , 값과 포인터로 구성 포인터 : 다음 노드나 이전 노드의 연결 정보 노드 하나에 값이나 포인터가 여러 개가 있을 수 있다. - 데이터 추가 데이터 추가위치(head, 중간, tail)에 따른 연결 작업이 필요하다 예시) 데이터를 가장 앞에 추가할 때 추가할 데이터를 담을 노.. 2022. 4. 5.
파스칼의 삼각형 파스칼의 삼각형은 다음과 같이 만들 수 있다. 1. 첫 번째 줄에는 숫자 1을 쓴다. 2. 그 다음 줄은 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다. 입력 출력 1 [[1]] 3 [[1], [1, 1], [1, 2, 1]] 5 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]] 처음으로 완벽하게 풀어서 올려봅니다.. 흑흑 import java.util.ArrayList; public class Practice1 { public static ArrayList solution(int numRows) { ArrayList outer = new ArrayList(); // 파스칼 삼각형 전체 for (int i = 0; i < numRows; i++) { // .. 2022. 4. 1.
점화식과 재귀함수 점화식 (Recurrence) - 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식 (ex. 피보나치 수열) - Stream의 reduce 사용하면 좋을 듯? 재귀함수 - 어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식 반환타입 함수이름(매개 변수){ 종료 조건 ... 함수 이름(...) } 연습 ) 재귀함수로 최대 공약수 구하기 int gcd(int a, int b){ if(a % b == 0){ return = b; } return gcd(b, a % b); } 2022. 4. 1.
조합 (Combination) - 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복X) - 순열은 순서O,중복X였다면 조합은 순서가 X인 경우이다. - 공식 nCr = n! / (n-r)!r! = nPr / r! 중복조합 - 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복O) - 공식 nHr = n+r-1Cr = (n+r-1)! / (n-1)!r! * 공부를 하면서 헷갈리던게 있었다. 순열이든 조합이든 중복O라는게 순서쌍이 중복허용이라는 말인가?였는데 ex) AB,BA는 -> 중복 O? 찾아보니 단일 요소가 중복될 수 있는가 였다. ex) AA,BB -> 중복 O / AB,BA -> 중복X 2022. 4. 1.

티스토리툴바