Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. LR Technique[왼쪽 오른쪽 순회 기술] 값을 도출하기 전에 미리 왼쪽을 순회해서 얻은 값, 오른쪽을 순회해서 얻은 값을 구하고 이를 통해서 결과를 도출하여 시간 복잡도를 줄인다. 필요성 : 중복되는 계산을 줄일 수 있다. 보통 미리 만든 배열을 통해서 값을 구한다면 시간복잡도가 줄어든다. 효용성 : 시간 복잡도가 줄어든다. 물론 여기서도 반복되는 행위에 대한 시간 복잡도는 여전하지만, 반복하는 횟수와 입력된 변수 개수의 곱으로 나타나는 시간복잡도와는 달리 LR 테크닉을 사용하면 더하기로 나타나는 시간복잡도로 변하게 되어 좋다. 이걸 언제 써야할지.. 는.. 아직 와닿지 않는다. 문제를 더 풀어봐야할 것 같다..
Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. Grid Compression[좌표 압축] 입력으로 받거나 이미 주어진 수의 범위를 압축하는 것이다. (빈 공간이 없도록 압축) 쉬운 예시로 총 1~ 20의 범위를 갖게 되는 수열 1, 3, 5 ,7 ,13, 20 이 주어져있다. 이것을 압축 시켜서 [1]-1, [2]-3, [3]-5, [4]-7, [5]-13, [6]-20 으로 변환 하여, 1,2,3,4,5,6 으로 압축시키고, 압축시킨 것에서 5번을 선택하면 13의 값을 반환하도록 한다. 필요성 : 예를 들어 원소가 갖는 범위가 1~1,000,000,000 이라고 하자. 다만, 배열에서 있는 것은 1, 2, 7 , 9 , 102, 10000000 이렇게 있다고 ..
Shorten Time Technique 문제 해결 방식의 시간복잡도를 줄이는 기술이다. Prefix Sum[누적합] 누적합 배열을 만들어서 시간복잡도를 줄인다. 특정 배열이 주어졌을 때, 그 배열을 통해서 배열의 값들에 대해 누적된 합을 '누적합 배열'에 저장한다. '누적합 배열'의 인덱스가 올라갈 때마다, 원래 주어진 특정 배열에서 접근하는 값의 인덱스도 올라간다. Ex) 특정한 배열이 주어졌을 때, 단순하게 0번부터 현재 인덱스까지의 합을 누적합 배열에 넣는다고 가정하자. 그렇다면, 특정 배열의 값이 1 3 7 11 23 이렇게 주어진다면, 누적합 배열은 1 4 11 22 45 이렇게 배열이 구성된다. 누적합 배열[0]=특정 배열[0],누적합 배열[1]=특정 배열[0]+특정 배열[1], 누적합 배열..
면접 Technical Interview의 종류. -알고리즘, 데이터 구조. (흔하게 물어본다.) -시스템 디자인 (석-박사는 이런 거 물어본다고 한다.) -domain specific interview. -project interview (간단하게 질문함. 어떤 역할을 했고, 어떤 어려움을 겪고 해결했는지 등등) 이력서를 화려하게 쓰는 것도 좋지만, 이력서 한 줄 한 줄을 모두 자신이 책임질 수 있어야한다. 이력서 내용을 모두 자신이 완벽하게 이해하고, 설명할 수 있어야한다. 중요한 건 깊이 있는 몇 개를 자신의 주요 컨셉으로서 적어야 한다. 너무 많이 쓴다고 좋지 않다. resume(서류 통과) 내용은 짧고 간결하게 강조. 최대한 잘 정렬해야 한다. Education(내가 무엇을 공부했고), Expe..
6회차 목표 : C++ 공부 및 DFS 알고리즘 공부. -C++ 공부 및 DP(다이나믹 프로그래밍) 알고리즘 공부. 일정 : 8/4 16:00~19:00 6회차 공부 내용 : -C++ 공부 TCP School의 내용을 토대로 공부하였다. C++은 C와 마찬가지로 구조체를 만들 수 있는데 C와는 달리 함수까지도 멤버 변수로 가져갈 수 있다! C++의 구조체는 객체 지향 프로그래밍의 Class의 기초가 된다. 클래스는 클래스의 멤버 변수를 프로퍼티(property), 멤버 함수를 메소드(method)라고도 한다. 객체 지향프로그래밍은 모든 데이터를 객체로 보며, 객체가 프로그래밍의 중심이 되게 하는 것이고, 객체를 만들어내기 위한 틀이 바로 클래스이다. 추상화, 캡슐화, 정보은닉, 상속성, 다형성과 같은 특..
DFS DFS는 그래프 자료구조에서 정의 된다. 그래프를 탐색하는 방법으로 Depth First Search의 약자, [깊이 우선 탐색]이라고 한다. 그래프의 원소를 타고 내려가서(깊게) 탐색한 후 끝 지점을 만나면, 다시 이전으로 돌아가서 다시 탐색을 한다. DFS는 재귀함수를 이용해서 구현하며, 이미 방문한 원소(지점이라고 하자.)는 다시 방문하지 않아야 효율이 좋기 때문에, 이전에 방문한 지점은 어떠한 처리를 해서 더는 방문하지 않도록 하자. 어떠한 처리는 visited라는 배열을 만들어서 지점에 해당하는 배열의 원소에 체크를 해두는 것이다. DFS를 이용하게 되는 그래프는 인접 행렬 혹은 인접 리스트로 나타낼 수 있다. DFS를 이용하여 문제를 풀어보자. 코드트리 : https://www.code..
5회차 목표 : C++ 공부 및 DFS 알고리즘 공부. -C++ 공부 및 DFS 알고리즘 공부. 일정 : 7/31 16:00~19:00 5회차 공부 내용 : C++ 공부 C++의 동적할당에 대하여 TCP School에서 공부. C++의 메모리 동적할당 포인터의 가장 큰 목적은 런 타임에 이름 없는 메모리를 할당받아 포인터에 할당하여, 할당받은 메모리에 접근하는 것이다. C언어에서는 malloc(),calloc() 함수 등의 라이브러리 함수로 이런 작업을 했다. (이전 1학기 때 수업에서 배웠던 것들.) 예를 들어, C에서는 배열의 크기를 미리 설정해놔야 해서, scanf로 받을 때 배열의 크기 변수를 malloc() 함수를 통해서 미리 메모리를 따왔다. C++에서도 malloc()과 같은 라이브러리 함수..
[문제] 백준 문제 : https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 : 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 : 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 : 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. [코드 풀이] [실패한 코딩] [성공한 코딩] 더보기 문자열로 입력받고, 문자 배열로 바꾸고, 어차피 정수, char니까 정렬하는데 sort 써버리자. #include using nam..
