전체 글

자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ]

재귀(Recursion)란 컴퓨터 과학에서 자신을 정의할 때 자기 자신을 재참조하는 방식을 뜻하며 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 1) 순환적 특성이 존재해야 한다. 2) 순환을 종료할 중단 조건이 있어야 한다. // ex 1) public void A(...) { if(중단 조건) { } A(...); } // ex 2) public void A() { if(중단 조건) { } B(); } public void B() { if(중단 조건) { } A(); } // 반복문 public static void evenNumber() { for (int i = 1; i 10) { return; } else if (i % 2 == 0) { System.out...

자료구조 - [ Queue ]

큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장되며, 일반적으론 작업 대기열로 많이 사용된다. 또한 Thread Pool에서 작업을 저장하는데 큐가 사용되며 순차적으로 먼저 들어온 작업을 처리하는 데 사용된다.. 또한 메시지와 관련한 서버 간의 통신을 위해 사용되는 메시지 큐, 그리고 시스템 버퍼에도 사용된다. 큐를 구현하는 방법으로는 크게 배열을 이용한 Circle Queue와 연결 리스트를 이용한 Queue가 있다. 1. Circle Queue (배열) front는 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값으로, 데이터를 꺼낸 후 1씩 증가한다. but 배열의 크기를 넘어서는 값을 가지지는 않는다. * front의 변경 범위 0

자료구조 - [ Stack ]

스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조로 되어 있으며, 데이터를 넣는 것을 Push, 데이터를 꺼내는 것을 Pop이라고 한다. 마지막에 들어간 것이 먼저 나온다는 후입선출(LIFO - Last In First Out)의 특징을 가지고 있다. 1. 배열로 Stack 구현 top은 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값이다. 데이터를 넣을 때 top은 위로 이동하고, 데이터를 꺼낼 때는 top이 아래로 이동하며, 최솟값으로 -1을 가지고 최댓값으로 배열의 마지막 index를 가진다. * top의 변경 범위 -1

자료구조 - [ 이중 연결 리스트 ]

1. 이중 연결 리스트 이중 연결 리스트의 노드는 데이터와 좌측 노드의 참조값을 저장하는 변수, 우측 노드의 참조값을 저장하는 변수가 있다. 구성은 크게 head, tail 그리고 노드가 있다. head : 첫 번째 노드를 가리키는 노드 또는 변수 tail : 마지막 노드를 가리키는 노드 또는 변수 노드 : 데이터, 좌/우측 노드로 접근할 수 있는 참조값을 가지고 있음 1) 장점 - 데이터의 크기가 예측 불가능할 때 사용할 수 있다. - 필요한 만큼만 메모리 공간을 사용 -> 배열보다 상대적으로 메모리 절약 가능 - 단일 연결 리스트와 다르게 양방향 연결을 지향하므로 뒤 쪽에 있는 노드 접근 시 tail을 이용하면 더 빠르게 접근 가능 ex) 노드의 개수가 10000개일때 9821번째 노드에 접근하려면 ..

자료구조 - [ 단일 연결 리스트 ]

1. 단일 연결 리스트 - 각 노드가 하나의 연결만을 가지고 다음 노드에 대한 참조값만 저장하여 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 구조 - 순차적으로 접근해야함 - 노드는 저장되는 데이터와 다음 노드에 접근할 수 있는 참조값을 가지고 있음 - head : 첫 번째 노드를 가리키는 노드 또는 변수. - pointer : 노드를 탐색하기 위해 해당 노드의 참조값을 일시적으로 저장하고 있는 변수 1) 장점 - 저장되는 데이터의 개수가 예측 불가능할 때 사용 가능 - 데이터를 삽입할 때 노드를 생성하기 때문에 필요한 만큼만 메모리 공간을 사용 -> 상대적으로 메모리 절약 가능 - 데이터의 삽입/삭제가 배열보다 더 간단하고 빠름. 배열은 중간 데이터가 삭제됐을 경우 데이터의 양과 삭제하는 데이터의..

백준 - [ 2477번: 참외밭 ]

참외밭 문제 시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다. 1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다. 예를 ..