현정쓰의 공부방

사용 교재 : 이것이 코딩테스트다.(with 파이썬) Ch09. 최단 경로 - 최단 경로 : 가장 짧은 경로를 찾는 알고리즘 - 이미 효율적인 알고리즘이 적립되어 있다. - 한 지점에서 다른 특정 지점까지의 최단 경로 구하기, 모든 지점에서 모든 지점까지의 최단 경로 모두 구하기 - 그래프를 이용해 표현 => 각 지점은 노드, 지점에 연결된 도로는 간선 - 다익스트라 최단 경로 알고리즘 : 그래프에 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘, 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택, 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것 ex. GPS 소프트웨어에 기본알고리즘으로 채택 - 음의 간선(0보다 작은 ..

사용 교재 : 이것이 코딩테스트다.(with 파이썬) CH05. DFS/BFS - DFS 실습 문제 1개 해결 *핵심* - 범위가 넘어가는 위치, 조건 상 움직이지 못하는 위치에 있을 시, 조건 탈출 - 방문한 위치 표시하기 - 상, 하, 좌, 우로 이동 방법 - 조건에 맞는 갯수 세기 public class Ice_Juice_05_10 { public static int N, M; public static int[][] ice = new int[1000][1000]; public static boolean dfs(int x, int y) { if(x = N || y = M) { return false; } if(ice[x][y] == 0) { ice[x][y] = 1; // 방문 처리 // 상, 하, ..

사용 교재 : 이것이 코딩테스트다.(with 파이썬) Ch05. DFS/BFS - 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 >> 삽입(push) : 데이터를 삽입 >> 삭제(pop) : 데이터를 삭제 >> 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생 >> 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행할 때 발생 - 스택(Stack) : 후입선출, 먼저 들어온 데이터가 가장 나중에 나간다. Q. 자바에서 스택 구현하는 방법? - 스택 클래스 사용방법 - 재귀함수 : 자기 자신을 다..

사용 교재 : 이것이 코딩테스트다.(with 파이썬) ch04.구현 - 이론은 앞 전에 공부했으므로 생략 왕실의 나이트 *핵심* - 이론 공부 당시 풀었던 문제와 유사, 다만 결과값을 다른 값을 원한다.(경우의 수) - 배열의 크기가 정해져있고, 움직일 수 있는 경우의 수도 정해져있다. - 움직였을 때 조건에 주어진 배열을 넘어가면 안된다. - 입력시 문자와 숫자가 동시에 입력된다. >> CharAt(); - String으로 입력된 문자열을 char 타입으로 사용하기 위해 한 글자식 쪼개준다. - CharAt(숫자);로 사용하면 쪼갠 문자열에서 특정 글자만 가져올 수 있다. - 사용 방법 : String변수명.CharAt(0); // 첫 번째 글자를 가져온다. - 사용방법 : sc.nextLine().C..

사용 교재 : 이것이 코딩테스트다(with 파이썬) ch04. 구현 - 이론은 앞에서 공부했으므로 패스 - 이론에 대한 이해는 쉬웠으나 문제 풀이가 어려웠던 걸로 기억한다. 시각 *핵심* - 단순하게 00시 00분 00초부터 N시 59분 59초까지 조건에 맞는 세서 출력하면 된다. - 삼중 반복문, 조건은 명확하게 나왔는데 그것을 어떻게 구현할 것인가. public class Time_04_02 { // 시, 분, 초에서 3이 나올 경우 true 반환, 분과 초는 나머지와 몫을 각각 계산해주는 이유는 33분, 3분을 각 계산하기 위해 public static boolean time3(int h, int m, int s) { if(h % 10 == 3 || m / 10 == 3 || m % 10 == 3 ..

사용 교재 : 이것이 코딩테스트다.(with 파이썬) ch06. 다이나믹 프로그래밍 - 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는데, 그에 대한 대표적인 방법이 다이나믹 프로그래밍이다. - 가장 대표적인 예시는 피보나치 수열-> 중복으로 계산되는 부분을 한 번씩만 풀어서 효율적으로 해결 가능 - 메모이제이션(Memoization) : 한번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져온느 기법 = 캐싱(Cashing) - 분할과 정복과는 다른 방법 - 재귀 함수 대신 반복문을 사용해야 더 성능이 좋아진다. - 재귀 방식 : 탑다운 방식(하향식), 반복문 : 보텀업(상향식) => 상향식으로 해결하기를 추천 - 대체로 간단한 형식으로 ..

사용 교재 : 이것이 코딩테스트다(with 파이썬) ch07. 이진 탐색 - 순차 탐색 : 리스트 안에 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 앞 전에 배웠던 내용 대부분이 순차 탐색을 이용 - 구현 간단, 최악의 경우 시간 복잡도 O(N) - 이진 탐색 : 배열 내부가 정렬되어 있어야 사용 가능, 시작점/끝점/중간점이 필요, 중간점 = 목표가 같을 경우 반환 - 퀵 정렬과 비슷 - 한 번 확인할 때마다 원소의 갯수가 절반으로 줄어드므로 시간 복잡도가 O(logN) - 재귀문, 반복문 두 가지로 구현 가능 - 가능하면 외워서 사용하길 권장 - 데이터 갯수가 1,000만개를 넘거나 데이터 범위의 크기가 1,000억 이상일 경우 고려 - 트리 : 이진 탐색과 유사한 ..

사용 교재 : 이것이 코딩테스트다.(with 파이썬) ch06. 정렬 - 이전 학습 내용을 바탕으로 실전문제 1문제 해결해보기. *핵심* - 오름차순으로 정렬하는 문제인데, 문제 자체의 수의 범위가 넓지 않으므로 어떤 정렬을 사용해도 무방 - 가장 첫 번째 나온 선택정렬을 사용했다. public class UpDown_06_10 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N]; for(int i = 0; i < N; i++) { arr[i] = sc.nextInt(); } //선택정렬 사용 for(int i = 0; i < N; i..

사용 교재 : 이것이 코딩테스트다.(with 파이썬) 06. 정렬 - 정렬이란, 데이터를 특정한 기준으로 나열한 것이다. >> 선택정렬 - '가장 작은 데이터를 선택'해 맨 앞 데이터와 바꾸는 것을 반복하는 방법 - 두 데이터의 자리 변경 시, 파이썬은 스와프 이용 / 다른 언어들은 임시 변수를 통해 두 변수 값을 변경 - 2중 반복문의 사용으로 시간 복잡도는 O(N^2) - 매우 비효율적 - 단, 소스코드 형태는 코딩테스트에서 잦으므로 익숙해지는게 좋다. >> 삽입정렬 - 구현 난이도 낮은 편, 실행 시간 측면에서 효율적 => 데이터가 거의 정렬되어 있을 때 효율적 - 특정 데이터를 적절한 위치에 삽입한다는 의미 - 정렬이 이루어진 원소들은 오름차순을 유지 - 자기보다 작은 데이털르 만나면 더 이상 볼..

사용 교재 : 이것이 코딩테스트다(with 파이썬) 04. 구현 - 머리 속의 알고리즘을 소스코드로 바꾸는 과정 = 풀이를 떠올리는 것(구상하는 것)은 쉽지만 소스코드로 옮기기 어려운 문제 - 모든 범위의 코딩 테스트 문제 유형을 포함한느 개념 - 피지컬이 좋다 : 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도가 빠른 사람 - 이 책에서는 구현에는 '완전 탐색'과 '시뮬레이션'을 포함한다. - 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 - 구현 시 유의 사항 ' 메모리 제약 사항' >> 큰 수의 표현 : 파이썬은 ok, 자바나 C/C++의 경우는 long long의 범위를 넘기는 경우 BigInte..