분류 전체보기

스택은 배열 또는 연결리스트로 구현할 수 있다. 연결리스트로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다. 코드 부분설명▼ void StackInit(Stack* pstack) { pstack->head = NULL; } 스택 초기화 부분 (포인터 변수 head는 NULL 로 초기화한다.) int SIsEmpty(Stack* pstack) { if (pstack->head == NULL) return TRUE; else return FALSE; } 스택이 비어있는지 확인하는 함수 (head가 NULL 이면 True 반환 아니면 False 반환) void SPush(Stack* pstack, Data data) { Node* newNode = (Node*)malloc(sizeo..

스택이란 가장 먼저 들어간 것이 나중에 나오는 특성을 가진 자료구조를 말한다. 다음 그림처럼 가장 나중에 들어간 Data 가 나올 때는 가장 먼저 나온다. 이러한 구조를 Last In First Out(LIFO) 또는 First In Last Out(FILO) 라 한다. 스택의 ADT는 다음과 같은 연산들을 정의한다. - 자료를 삽입하는 push - 가장 마지막에 삽입된 자료를 꺼내는 pop - 가장 마지막에 삽입된 자료를 조회하는 peek - 스택이 비어 있는지 확인하는 empty - 스택 내 자료의 수를 확인하는 size 여기서 스택은 배열 또는 연결리스트로 구현할 수 있다. 먼저 배열로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다. 코드 부분설명▼ void StackIn..

앞서 우리가 구현한 연결 리스트의 마지막 노드는 NULL 을 가리켰다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 원형 연결리스트가 된다. 위 사진처럼 노드를 머리에 추가하나 꼬리에 추가하나 두 연결리스트 모두 8→1→2 형태로 가리키기 때문에 원형 연결리스트에서는 머리와 꼬리의 구분이 없다고도 볼 수 있다. 위의 그림상에서 꼬리에 노드를 추가하려면 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야만 한다. 하지만 여기서 tail 이라는 포인터 변수를 노드 끝을 가리키도록 하면 새로운 노드를 추가하기에 어려움이 없다. tail 이라는 포인터 변수는 꼬리를 가리키고 tail → next 는 리스트에서 머리를 가리키게 된다. 다음 그림의 왼쪽 편은 새로운 노드가 생성되었지만 아..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 계단 수는 0으로 시작하면 안되며 인접한 숫자마다 1의 차이를 가져야한다. 따라서 아래 그림과 같이 경우의 수를 나열해볼 수 있다. 여기서 N=3 일 때 뒤 2자리는 N=2 인 경우에서 가져온다는 규칙을 알 수 있다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다음 문제는 확통에서 배운 nCr 을 사용하면 풀린다. 여기서 nCr = n-1Cr + n-1Cr-1 법칙을 사용하면 다음 코드로 풀린다. 여기서 nCr = n-1Cr + n-1Cr-1 법칙을 사용하면 다음 코드로 풀린다. 코드 import java.io.*; import java.util.*; public class Main { static int[][] dp = new int[30][30]; ..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 다음 문제는 피보나치 수열을 이용하여 풀 수 있었다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long dp[] = new long[101]; long arr..

이는 0 이하의 값이 입력될 때까지 입력이 계속되는 간단한 예제이다. 다음과 같은 형태로 자연수를 입력으로 받고 0이하의 값이 입력되면 while 문을 빠져나와 배열을 출력한다. 하지만 이처럼 배열은 메모리의 특성이 정적이여서 메모리의 길이를 변경하는 것이 불가능하다. 위 예제를 실행한 후 0 이하의 값을 입력하지 않고 계속 입력하면 할당된 배열의 크기인 10을 넘어가는 문제가 발생한다. 이 문제를 해결하기 위해 정적인 배열이 아닌 동적으로 메모리를 구성하여 다음과 같은 연결리스트를 구성할 수 있다. ▼코드 설명 1. 노드 형태 구현 여기서 data는 데이터를 담을 공간이며 struct _node *next 는 아래 그림처럼 노드의 연결을 위한 포인터이다. head는 연결 리스트에서 머리를 가리키는 포인..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 위의 예제를 바탕으로 풀어보면 다음과 같다. 맨 처음 dp[0] 값은 1로 설정하고 arr[1] 의 값이 arr[0] 보다 크면 dp[1] 의 값은 dp[0] 에 1을 더한 2로 설정한다. arr[2] 의 값이 arr[0] , arr[1] 보다 크지 않기 때문에 dp[2] 의 값은 1로 설정한다. arr[3] 의 값이 ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다음 문제는 경우의 수를 모두 작성하여 규칙을 본 결과 피보나치 배열과 같다는 걸 알게 되었다. N자리 이친수의 개수는 다음과 같다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n..

리스트는 구현방법에 따라 순차 리스트, 연결 리스트로 나눌 수 있다. ▶순차리스트 - 배열을 기반으로 구현된 리스트 ▶연결리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트 또한 리스트 자료구조는 데이터를 나란히 저장하며 중복된 데이터의 저장을 막지 않는다. 그리하여 리스트를 활용하는 예를 코드로 살펴보면 다음과 같다. 코드 부분 설명 ▼ 다음 코드에서는 먼저 리스트를 생성 및 초기화한 후 11, 11, 22, 22, 33 라는 값을 저장한다. 그리고 LCount 함수를 통해 현재 리스트 안에 있는 데이터의 수를 출력하고 LFirst 함수로 첫 번째 데이터를 조회한 후 while 문을 통해 다음으로 넘어가면서 데이터를 출력한다. LFirst 함수를 통해 첫 번째 데이터부터 조회하는데 22 라는 값을 ..