개발기술/알고리즘, 자료구조, PS (6) 썸네일형 리스트형 코딩테스트 탐색문제 (DFS,BFS,DP) 그래프이론으로 정의되는 문제그래프 탐색문제 : 그래프를 노드간 관계(함수 혹은 adj list 관계 등)로 표현하고 각 노드를 탐색한 후 특정한 동작/함수를 실행함.노드를 특정한 경우의 수로 생각할 수 있으며 코드로는 객체의 특정한 상태(state) 로 표현함, 각 노드는 객체의 attribute 값이 다른 상태.그래프 탐색 문제 풀이의 관건은 노드/경우의 수를 어떻게 객체와 개체의 attribute로 표현할 것인지. 그리고 노드간 의 관계인 엣지는 어떤 Method 관계(객체의 attribute를 바꾸는 함수)로 표현할 것인지. 그리고 더 나아가 시간복잡도 최적화를 위해서 엣지 커트를 어떻게 구현할 것인지에 대한 문제이다.DFS와 For/if문 차이경우의 수 관점에서는 컴퓨터의 모든 동작은 tree로 .. 그래프이론 알고리즘/자료구조 그래프 이론의 필요성 높은 수준의 프로그래밍을 하기 위해서는 그래프이론에 대한 탄탄한 이해가 필수적이다. 프로그래밍의 발전은 결국 정보의 연결성의 증대에 의한, 연결성 증대를 위한 방향으로 발전하고 있기 때문이다. 예를 들어, FaceBook과 같은 연결형 SNS, Google과 같은 검색엔진, Netflix와 같은 추천서비스, Amazon과 같은 동선최적화, OpenAI와 같은 자연어처리 등 모두 내가 선택한 Node로부터 주변 Node를 탐색하는 문제이기때문이다. 고등수학에서 잘 다루지 않아서 익숙하지 않은 것이지 어려운 것은 아니라고 생각한다. 높은 수준의 프로그래머가 되기 위해서는 결국엔 선형대수학을 어느정도는 이해해야 할 것이고 그것의 근본이 그래프 이론이니 지금부터 피할 수 없는 기초를 .. 알고리즘 정렬의 종류Selection Sortrepeatedly selecting the smallest (or largest, depending on the sorting order) element from the unsorted portion of the array and moving it to the beginning of the sorted portion. O(n^2)Bubble Sortrepeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which .. 코딩테스트 문제후기 제로베이스 코딩테스트 연습문제 1-2. 2번 문제- 문제분석 : '.' '!' '?' ' '를 구분자로 사용하여 string에서 숫자와 문자로된 단어들을 추출하고 뒤집은 후 string 배열을 출력하라- 나의접근 : 1. 문자를 뒤집기위해서 기능을 직접구현함; string을 chararray로 변환후 순회하여 순서를 뒤집음 2. string을 chararray로 변환한 후 하나씩 조회하여 구분자가 아닌 것을 만나면 string temp에 +하였고 구분자를 만나면 temp를 arraylist에 append한 후 초기화함. 그 후 array list- 대안풀이 : 1. stringbuilder에서 reverse method사용하여 순서 변환 2. 구분자들을 하나의 string으로 합치고 string을 c.. 코딩테스트 일반유형 문제풀이 코딩테스트 학습법1. 수학공부하듯이 공식을 이해와 암기를 병행해야한다.2. 유형을 암기해야한다코딩테스트 풀이법0. 문제를 완전히 이해한 후에 풀이를 시작할 것1. 주어진 예시를 귀납적으로 접근해서 일반화할 것2. 풀이의 시간복잡도를 따져볼것3. 손코드딩이 완료된 후에 실제로 코드를 작성에 들어갈 것 코딩테스트 제출전1. 제출전 로그를 남겨서 코드의 흐름을 확인할 것2. 주어진 케이스 외에도 엣지 케이스를 3개정도 만들어서 생각해볼것 문제접근방식 1. 연역적 탐구방식 : 수학적 논리관계를 통해서 답을 도출해낼 수 있을때2. case by case 분석 : 어떤 solution으로 도달할 수 있는 방법들을 MECE하게 나열하고, 하나씩 고려해서 불가능하면 소거하는 방식3. 시행착오법(trial and err.. Data Structure 데이터구조 학습과 선택의 접근관점1. 데이터 구조 선택에 있어서 고려할 것들. 데이터 간의 순서관계가 유의미한가? Hash table과 Dynamic Array데이터 간의 대소관계가 유의미한가? Sorting으로 자원 절약이 가능한지메모리 inplace로 구현해야하는가? Dynamic Programming 혹은 Stack과 Queue 구조를 사용하면 좋을지데이터의 조회가 주목적인가, 데이터의 보관이 주목적인가? Hashtable/Dynamic Array 혹은 Stack/Queue데이터 의미 단위가 전체 데이터의 맥락과 별개로, 개별 데이터에 있는가 혹은 전체 데이터 맥락을 고려해야하는가? Hashtable/Dynamic Array 혹은 Stack/Queue2. 사용시의 장점과 단점3. 실제 활용되는 분.. 이전 1 다음
