Sa-gom Blog

No bottom

[Datastructure] 재귀의 동작

재귀의 동작원리는 무엇일까?? 재귀함수의 동작원리를 이해하기 위해서는 메모리 주소와 변수 이름들이 어떻게 결합되는지를 알 필요가 있다. 바인딩 메모리 주소와 변수 이름간의 결합을 바인딩(binding)라 한다. 그리고 컴파일/실행사이클 동안 바인딩이 발생한 시점을 바인딩시간이라 하는데 이때 바인딩 시점에 따라 정적 기억장소 할당, 동적기억장소 할당으...

Posted by Sa-gom Blog on May 7, 2018

[Algorithm] 백준 1912 연속합

백준 온라인 저지 1912 연속합 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답...

Posted by Sa-gom Blog on May 7, 2018

[Algorithm] 백준 2193 이친수

백준 온라인 저지 2193 이친수 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. ...

Posted by Sa-gom Blog on May 3, 2018

[Algorithm] 백준 1992 쿼드트리

백준 온라인 저지 2579번 계단 오르기 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 위 그림에서 왼쪽의 영상...

Posted by Sa-gom Blog on May 3, 2018

[Algorithm] 백준 1780 종이의 개수

백준 온라인 저지 1780번 종이의 개수 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이 때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종...

Posted by Sa-gom Blog on May 3, 2018

[Algorithm] 백준 2579 계단오르기

백준 온라인 저지 2579번 계단 오르기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임...

Posted by Sa-gom Blog on April 30, 2018

[Algorithm] 백준 2579 계단오르기

백준 온라인 저지 2579번 계단 오르기 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번...

Posted by Sa-gom Blog on April 28, 2018

[Datastructure] 연결구조체 PLUS

연결 구조체 PLUS 전에 살펴봤던 연결리스트는 한가지 문제가 있다. 뒤따르는 노드의 액세스는 가능하지만 그에 앞서는 노드는 접근할 수 없다는게 그것이다. 그러나 선형리스트를 약간 바꾸면(마지막 노드의 next멤버에 있는 포인터가 NULL을 가지는대신 첫 번째 노드로 되돌아 가리키도록 하는 것) 단점을 해결할 수 있다. 이를 원형연결리스트라 칭한다....

Posted by Sa-gom Blog on April 20, 2018

[Datastructure] 연결구조체

연결 구조체 하나의 배열에서 스택을 구현하기는 간단하지만 중대한 결점이있다. 스택 객체를 선얼할 때 스택의 크기를 결정해야하는것이다. 이는 상당한 메모리낭비를 야기시킨다. 하지만 요소를 한번에 하나씩 동적할당을 하면 위의 단점을 보완할 수 있다. new연산자는 type값을 수용할 정도크기의 메모리블록을 할당하고 그 블록의 주소를 리턴시킨다. 이를 ...

Posted by Sa-gom Blog on April 20, 2018

[Algorithm] 백준 2156번 포도주 시식

백준 온라인 저지 2156번 포도주 시식 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 ...

Posted by Sa-gom Blog on April 19, 2018