수정요청 test

Q. Array는 어떤 자료구조 인가요? STR

[핵심 답변]

Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 입니다.

[면접

💡 Array에 관한 질문을 할 때에는 매우 높은 확률로 Linked List에 대한 질문도 나오게 됩니다. 따라서 Array의 다양한 특징 중에서 Linked List와 비교가 되는 특성들을 위주로 대답을 하게 되면 편하게 풀어나갈 수 있습니다!
Array와 Linked List의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 operation의 연산 속도(time complexity) 입니다. 이를 유념해서 공부해 가시면 좋은 답변을 하실 수 있습니다.

Array의 특징

고정된 저장 공간(fixed-size)
순차적인 데이터 저장(order)

Array의 장점은 lookup과 append가 빠르다는 것입니다. 따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 씁니다.

Array의 단점은 fixed-size 특성상 선언시에 Array의 크기를 미리 정해야 된다는 것입니다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있습니다.

시간복잡도

	Array
access	$O(1)$
append	$O(1)$
마지막 원소delete	$O(1)$
insertion	$O(n)$
deletion	$O(n)$
search	$O(n)$

[꼬꼬무 문답]

Q) 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을까요?

**[핵심 답변]**


 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당합니다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제하면 됩니다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 합니다.


 또 다른 방법으로는, size를 예측하기 쉽지 않다면 Array대신 Linked list를 사용함으로써 데이터가 추가될 때마다 메모리공간을 할당받는 방식을 사용하면 됩니다.

Q. Dynamic Array는 어떤 자료구조 인가요?

[핵심 답변]

Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다.

[면접

💡 Array의 특징중에 fixed-size의 한계점을 보완하고자 고안된 자료구조인 Dynamic Array에 대해서 면접을 위해 깊게 공부하실 내용은 크게 두 가지 입니다.

resize를 하는 방식

데이터 추가(append)할 때의 시간복잡도

Dynamic Array

Dynamic_Array.001.jpeg

Dynamic Array는 size를 자동적으로 resizing을 하는 Array입니다. 기존에 고정된 size를 가진 Static Array의 한계점을 보안하고자 고안되었습니다. Dynamic Array는 data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면, size를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 됩니다. 이를 resize라고 합니다. 이로써 새로운 data를 저장할 수 있게 됩니다. 따라서 Dynamic Array는 size를 미리 고민할 필요없다는 장점이 있습니다.

resizing 을 하는 방법은 여러 가지가 있는데, 대표적으로 기존 Array size의 2배 size를 할당하는 doubling이 있습니다.

Doubling

resize의 대표적인 방법으로는 Doubling이 있습니다. 데이터를 추가(append $O(1)$ ) 하다가 메모리를 초과하게 되면 기존 배열의size보다 두배 큰 배열을 선언하고 데이터를 일일이 옮기는(n개의 데이터를 일일이 옮겨야 하므로 $O(n)$ ) 방법입니다.

Dynamic_Array_시간복잡도.001.jpeg

분할상환 시간복잡도 Amortized time complexity

Dynamic array에 데이터를 추가할 때마다 $O(1)$ 의 시간이 걸리게 됩니다. → 추가를 하다가 미리 선언된 size를 넘어서는 순간에 resize를 하게 됩니다. → 이 때는 일일이 데이터를 모두 옮겨야 되기 때문에 이 때만큼은 $O(n)$ 의 시간이 걸리게 됩니다.

그렇다면 결과적으로 append의 시간복잡도는 $O(1)$ 일까요 아니면 $O(n)$ 일까요?

append의 총 과정을 살펴보면 데이터를 마지막 인덱스에 추가하는( $O(1)$ )작업이 대다수이고, size를 넘어설 때는 size를 두 배 늘리고 데이터를 일일이 옮기는 과정 (resize $O(n)$ )이 아주 가끔 발생합니다. 결론부터 말하자면 append의 전체적인 시간복잡도는 $O(1)$ 입니다. 좀 더 정확히 말하면 amortized $O(1)$ 이라고 부릅니다.

쉽게 설명하자면 가끔 발생하는 O(n)의 resize하는 시간을, 자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로써 전체적으로 O(1)의 시간이 걸린다고 생각하시면 됩니다.

[꼬꼬무 문답]

Q) Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.

**[핵심 답변]**


Linked List와 비교했을 때, Dynamic Array의 장점은

- 데이터 접근과 할당이 $O(1)$로 굉장히 빠릅니다. 이는 index 접근하는 방법이 산술적인 연산 [배열 첫 data의 주소값] + [offset]으로 이루어져 있긴 때문입니다. (randam access)
- Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠릅니다.($O(1)$)

Linked List와 비교했을 때, Dynamic Array의 단점은

- Dynamic Array의 맨 끝이 아닌 곳에 data를 insert or remove할 때, 느린 편입니다($O(n)$).  느린 이유는 메모리상에서 연속적으로 데이터들이 저장되어 있기 때문에, 데이터를 추가 삭제할 때 뒤에 있는 data들을 모두 한칸씩 shift 해야되기 때문입니다.
- resize를 해야할 때, 예상치 못하게 현저히 낮은 performance가 발생합니다.
- resize에 시간이 많이 걸리므로 필요한 것 이상 memory공간을 할당받습니다. 따라서 사용하지 않고 있는 낭비되는 메모리공간이 발생합니다.

lim_{n \to \infty} \int_{-N}^{N} e^x\, dx + \oint_{C} x^3\, dx + 4y^2\, dy

{n}\mathrm{P}{k} ,{n}\mathrm{C}{k} , {n}\mathrm{\Pi}{k},{n}\mathrm{H}{k}, P(n,k), S(n,k),\mathrm{P}_{k}^{n}

\begin{matrix} f(n+1) &=& (n+1)^2 \\ &=& n^2 + 2n + 1 \end{matrix}

코드블럭

# python code
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
odd_numbers = [num for num in numbers if num % 2 != 0]
string = 'hello, world!'
uppercase_string = string.upper()
print(uppercase_string)

// java code
if (!"".equals(accessToken) && accessToken != null) {
    try {
        String githubRequestURL = "https://api.github.com/users/" + member.getGithubId() + "/repos";
        RestTemplate rt = new RestTemplate();
        HttpHeaders headers = new HttpHeaders();
        headers.add("Accept", "application/vnd.github+json");

// SQL
SELECT * FROM db;
SELECT COUNT(*) AS 주문수
FROM 주문
WHERE 주문일자 BETWEEN '2022-01-01' AND '2022-12-31';
SELECT COUNT(*) AS 고객수
FROM 고객
WHERE 지역 = '서울';

자료조사

(1). Notion 및 블로그를 함께 사용하는 사용자 비율 통계를 구할 수 있는지 조사(다니엘) 1). 자료가 없다면, 각 플랫폼별 블로그 사용자 비율 통계라도 구할 수 있는지 조사

국내 웹사이트 접속자 랭킹 (5위 티스토리)
- 구글이나 다음카카오의 점유율을 합쳐도 네이버의 점유율에는 한참 못미친다(네이버가 70%이상을 점유).
- 따라서 다음카카오에서 운영하는 티스토리 블로그 보다는 네이버에서 운영하는 네이버 블로그를 운영하는것이 조회수 측면에서 훨씬 유리하다. 네이버는 자체 블로그인 네이버 블로그를 우선적으로 상위에 노출시키기 때문이다. 국내시장 점유율을 바탕으로 네이버는 막강한 파워를 갖고 있으며 그 파워는 네이버 블로그에도 그대로 이어진다.
세계 최대 오픈소스 공유 플랫폼 깃허브의 활상 사용자 수 9천만명
사람들이 노션과 블로그를 동시에 사용하는 이유 → 노가리 필요성
- 노션
  - 장점
    - 효율적으로 문서 기반 콘텐츠 작성 가능
    - 코딩 없이 웹에 콘텐츠 작성, 배포 가능
    - 콘텐츠 작성 후 링크를 통해 빠르게 공유 가능
    - 블럭 단위의 데이터 관리
      - 하나의 블럭은 하나의 텍스트일 수도 있고 이미지, 파일, 칸반보드 등등 다양한 포맷을 지원
    - 매우 다양하고 화려한 Templates
      - 분야별로 다양하게 제공
  - 단점
    - 공식적인 커스텀 도메인 미지원
    - 페이지에 대한 데이터 트래킹 어려움
    - 커스텀UI, 비로그인 사용자 댓글, 버튼 등 미지원
    - 노션의 웹공유는 웹만을 위해서 만들어지지 않는 부가기능에 불과함. 그러다보니 못생긴 URL 이나 느린 페이지 로딩 같은 단점을 가지고 있습니다.
- 노션은 블로그가 아니다. 단순히 개인 기록용이며, 다른 사용자들에게 공유를 할 수는 있지만, 그 공유한 것이 구글에 검색되지는 않는다. 그래서 블로그를 통한 에드센스 수익화 기능도 활용할 수 없다.
- Notion 플랫폼으로 글을 작성하고, 이 글 포맷을 그대로 블로그화 해서 사업하는 업체들도 많다. 외국 업체들도 있고, 한국에는 “우피” 라는 업체가 이러한 작업을 수행한다. 하지만 우피 플랫폼 역시 어느정도 정해져있는 템플릿과 제대로 사용하려면 월 요금(최소 월 5,900원)을 내는게 필요하다.
  
  bookmark

(2). 기존 N2T 사용자들의 불편함을 나타내는 자료들(댓글등) 조사(다니엘)

티스토리뿐만 아니라 백업 등의 목적으로 다른 플랫폼에 대한 필요성
- 깃허브에 바로 private repository에 자동으로 backup하는것도 만들 수있을까요?
문제 발생시 원인을 알 수 없음 (콘솔에 나오는 명확하지 않은 모호한 에러 메세지)
- 프로그램 실행중에 [진행중] Selenium으로 티스토리(카카오) 로그인 완료! list index out of range [완료] 프로그램 종료. 라고 콘솔에 뜨고, 포스팅이 안되는 증상을 발견했습니다. 혹시 어디가 문제일까요 ???
- ㅠㅠㅠ 여러번이나 정보를 확인했는데도 list index out of range 이슈가 해결되지 않네요...!!! 다음에 다시 도전해봐야 할 듯합니다 ㅠㅠ 귀중한 시간 내어주셔서 정말 감사드립니다!
- config파일의 TABLE_PAGE_URL 란에 템플릿 url이 잘 들어갔는지 다시 확인해보시겠어요?
- ValueError: [Error] 다운로드 폴더 경로를 비우고 다시 실행해주세요. Download Folder:[/Users/oyj/.n2t] 이러한 오류가 발생하는데 어디를 수정해야 할까요? ㅜㅜ
티스토리 토큰 발급시 사용자가 직접 서비스 URL과 callback url을 설정해여하는 번거로움과 사용자 에러 발생 가능성 증가
- 티스토리 Open API 등록 할 때, 서비스 URL과 CallBack 입력 란에 블로그 주소를 같게 적었는지 확인해보시고, http://가 아닌 https://로 되어있는지 확인해주시겠어요?
- 여기 분들도 많이 올리신 authorize_code를 발급 못받는 문제 였습니다. 토큰을 못받는건 다들 달아주신 BLOG_NAME, SECRET_KEY, CLIENT_ID, REDIRECT_URI 문제라고 해서 5번정도 OPEN API를 만들었다 지우고 했는데도 동일했습니다.
N2T 새로운 버전으로 업데이트시 재설치 해야하는 번거로움
- notion-py의 버전 문제일수도 있을 것 같은데 notion-py 패키지가 원래 버전은 에러가 있어 수정된 버전으로 설치해야 합니다. (requirements.txt 참고)
파이썬 버전 관련 에러 발생

kwangyonglee

CS 정리 (1)