관광이 블로그

이번에 살펴볼 주제는 코딩인터뷰 배열과 문자열파트에 C++ String에 대해 정리해보도록하겠습니다. 책은 자바위주로 되어있지만, 제가 알고리즘 테스트에 사용하는 언어는 C++14이기 때문에 Java의 StringBuilder 대신에 C++ String STL에 대해 다루도록 하겠습니다. # 일단 문자열이 무엇일까요? 예를 들어보겠습니다. "Algorithm" 라는 문자열이 있다고 가정하겠습니다. A l g o r i t h m NULL('\0') 당연히 생각하신데로 나오셨나요? 네, 그렇습니다. C언어나 C++을 사용해보신분들은 알고 계실것이라 생각이 듭니다. 하지만, 모르시는분들이 있으시기 때문에 짚고 넘어가겠습니다. 현재 우리는 "Algorithm"이라는 문자열을 가지고 있습니다. 위의 구조에서 보..

안녕하세요 감자코딩입니다. 코딩인터뷰 완전분석에 대한 정리글을 포스팅을 꾸준히 진행해보려고합니다. 그러면 바로 진행하겠습니다 # 해시테이블 해시테이블은 효율 탐색을 위한 자료구조로서 키(key) 값(value)에 대응된다. 해시테이블을 구현하기 위해서는 연결리스트(Linked list)와 해시코드함수(hash code function)만 있으면 된다. 키(문자열 혹은 다른 어떤 자료형도 가능하다)와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다. # 해시테이블의 과정 1. 키의 해시코드 계산 키의 자료형은 보통 int,long이 된다. 키의 개수는 무한, int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있음. 2, hash(key) % array_length와 같..

감자코딩입니다. 이번에 살펴볼 내용은 C++ STL중 하나인 forward_list 입니다. single linked list(단일 연결 리스트) 자료구조를 이용하여 만든 시퀀스 컨테이너이며, std:list기준으로 작성된 컨테이너다. std::forward_list 특징 std:list는 양방향 std::forward_list 단방향 Flow std::list보다 삽입/삭제 속도가 빠름 std::list 양방향인 std::list에 비해 메모리를 적게 사용 삽입과 삭제는 지정한 요소의 다음 요소만 가능 구현의 복잡성과 성능 문제 때문에 std::list에서 제공하는 insert와 erase를 제공하지 않음. Single Linked List는 STL로 forward_list 로 구현되어있고, C+11 ..

안녕하세요! 관광이 개발블로그의 관광이 입니다이번에 알아볼 STL의 종류중 하나인 VECTOR에 대해서 살펴보겠습니다. 1. Vector Container VectorContainer는 자동으로 메모리가 할당되는 배열이라고 합니다. 대표적인 메소드로는- v.front() - 가장 앞 위치- v.back() - 마지막 위치- v.push_back() - 가장마지막에 원소 push- v.pop_back() - 가장 마지막 원소 pop 맨뒤쪽에서 삽입과 삭제가 가능하다. 2. Vector Container 사용시 필요한 사항#include == vector v; 라고 가정.== 참조 한다는 것은 해당 데이터를 리턴 한다는 뜻입니다. v.assign(5, 2);- 2의 값으로 5개의 원소 할당. v.at(idx..

* 1주차 알고리즘 정리 안녕하세요 감자입니다. 이제 알고리즘정리를 시작하려고 합니다. 오늘알아볼 알고리즘의 종류중 하나인 BFS를 살펴볼것인데요, 많이 쓰이기도하고 중요한 알고리즘인 만큼 정리시작해보겠습니다. 1. BFS(Breadth First Search)는 그래프전체를 탐색하는 알고리즘의 방법중 하나이다.그래프 전체를 탐색하는 방법은 BFS,DFS가 있다.BFS(Breadth First Search)는 그래프 전체를 탐색,인접한 노드들을 차례대로 방문한다.동심원의 형태로 이루어져서 점차 하나씩 모든 노드들을 방문하게 된다. BFS에서 가장 중요한 것은 각 노드에 대해서 최단 경로의 길이를 구할 수 있다는것이다. 이를 구현하기 위해서는 C++ STL Queue 방법을 사용하게 될것이다. 위의 그림대..