Hee's Story

Array 배열의 크기는 한 번 정하면 변경할 수 없다. 배열 초기화 시에 메모리에 할당되어 ArrayList보다 속도가 빠르다. 논리적 저장 순서와 물리적 저장 순서가 일치한다. 인덱스를 사용해 특정 원소에 접근이 가능하다. 즉, Random Access(비순차적 접급)가 가능하다. 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다. 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용한다. (연속된 메모리 사용) 배열의 크기를 바꿀 수 없다. 즉, 배열의 크기는 제한적이다. 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 값을 갖는 원소들을 1씩 옮겨줘야 하기 때문에 시간 복잡도는 O(n)이다. 배열의 원소를 삽입할 경우 배열의 크기가 충분할 때는 시간 복잡..

메모리 저장 구조 메모리 할당 * 정적 할당 - 메모리의 크기가 하드 코딩(하드 코딩 : 데이터를 코드 내부에 직접 입력하는 것)되어 실행하는 순간 정적으로 할당 - 프로그램이 실행 될 때 이미 해당 메모리의 크기가 결정됨(컴파일 시) - 프로그램이 종료할 때 알아서 운영체제가 회수 - 장점 : 해제하지 않음으로 인한 메모리 누수문제를 신경쓰지 않아도 됨 - 단점 : 스택에 할당된 메모리이므로 할당 받을 수 있는 최대 메모리에 제약이 있다. * 동적 할당 - 실행 시간 동안 사용할 메모리 공간을 할당하는 것 - 사용 후 운영체제에 반납, 재할당 가능 - 힙 영역에서 할당 - 프로세스가 동작중일 때 명시적으로 해제하거나 또는 GC에 의해 해제됨(그전까지 그대로 유지), C++에는 GC가 없기 때문에 해제해..

Repository(저장소) - 파일이나 디렉토리를 저장하는 장소이다. - local repository : 개인 PC에 존재하는 저장소이다. 다음 3가지로 이루어져 있다. - working directory : 실제소스코드 - Index : stage 역할 (stage : working dir에서 commit하기 전에 commit하려는 파일 올려두는 곳) - head : commit 을 한 소스코드 - remote repository : 원격 저장소이다. 파일이 원격 저장소 전용 서버에서 관리하고 공유가 가능하다. Clone - remote repository의 내용을 통째로 다운로드한다. - 명령어 - git clone Commit - 파일 및 폴더의 추가/변경 사항들을 저장할 때(기록할 때) 사용한..

문제 철수는 마을의 여러 건축물들을 폭파해달라는 요청을 받았다. 이에 건축물들을 하나씩 폭파하려 한다. 일반적으로, 하나의 건물을 폭파하기 위해서는 다이너마이트 하나가 필요하다고 하자. 철수의 마을에 있는 건축물들 사이에는 특별한 단방향 통로가 존재한다. 하나의 건축물을 폭파시킬 경우, 이 단방향 통로로 인하여 상황이 약간 복잡해지는데, 이는 건물 A에서 건물 B로 통로가 이어져 있을 경우, 건물 A를 폭파시키면 건물 B 역시 폭파된다는 것이다. 이유인 즉슨, 단방향 통로가 지하에 매설되어 있기 때문에, 지하의 통로가 무너지면서 건물 B가 함께 무너진다. 철수의 마을에 존재하는 건축물의 개수가 주어지고, 이 건축물들 사이의 단방향 통로가 주어질 때, 최소 몇 개의 다이너마이트가 있어야 모든 건축물을 폭파..

문제 SCC (Strongly Connected Component)란, 방향성 그래프가 주어질 때 정점을 여러 집합으로 나누는 기법으로써, 같은 집합에 속해있는 정점끼리는 서로 왔다갔다 할 수 있어야 한다. 아래 그림은 그래프의 예제와, 이 그래프에서 SCC를 구한 예제이다. 아래 그림처럼, 정점을 {1, 2, 5}, {6, 7}, {3, 4, 8} 의 3개의 집합으로 나누게 되면, 같은 집합에 속한 정점들끼리는 모두 왔다갔다 할 수 있다. 그래프가 주어질 때, SCC를 구하였을 때 얻을 수 있는 정점의 집합의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진..

문제 철수네 마을에는 N개의 집이 있으며, 각 집은 고유한 번호를 부여받는다. 각 번호는 1보다 크거나 같고, N보다 작거나 같다. 철수는 마을 K에 살고 있다. 집과 집 사이에는 단방향 도로가 존재하기 때문에, 이 도로를 통하여 서로 이동할 수 있다. 즉, N개의 마을은 그래프 구조를 이룬다. 편의상 각 집에는 한 사람만이 살고 있다고 가정하자. 크리스마스인 오늘, 철수는 본인의 집에서 파티를 열려고 한다. 따라서 다른 모든 사람들이 철수의 집에 모여 파티를 즐기고, 파티가 끝난 후에는 다시 본인의 집으로 돌아가려 한다. 사람들은 본인의 집에서 철수네 집까지 이동하기 위하여 항상 최단거리로 이동하기를 원하고, 마찬가지로 철수네 집에서 본인의 집에 갈 때도 최단거리로 이동하기를 원한다. 집의 개수와 두 ..