분류 전체보기

큐란 가장 먼저 들어간 것이 가장 먼저 나오는 특성을 가진 자료구조를 말한다. 다음 그림처럼 먼저 들어간 Data는 나올 때 가장 먼저 나온다. 이러한 구조를 First In First Out(FIFO) 또는 Last In Last Out(LILO) 라 한다. 큐의 ADT는 다음과 같은 연산들을 정의한다. - 큐에 데이터를 넣는 연산 enqueue - 큐에서 데이터를 꺼내는 연산 dequeue ● enqueue 연산 방식 다음 그림은 길이가 4인 배열 대상의 enqueue 연산을 보이며 여기서 F는 Front 를 의미하고 R은 Rear 를 의미하는데 새 데이터는 Rear 부분에 저장되고 R은 그 다음 칸을 가리키게 된다. ● 일반적이지 않은 dequeue 방식 위 그림에서 보이는 방식은 dequeue 연..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 다음 문제는 K 라는 가격을 동전의 가치로 만들어야 하는데 그 중에서 동전의 개수가 최소값이 되는 개수를 출력해야한다. 만약 K가 4200원일 때 (1000원 x 4개) + (100원 x 2개) 해서 6이 출력되어야 한다. 만약 K가 4790원일 때 (1000원 x 4개) + (500원 x 1개) + (100원 x 2개) + (50원..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 다음 문제는 인출하는데 필요한 시간의 최솟값을 구하는 프로그램이다. 줄 순서대로 앞에서부터 뒤까지 시간을 더하여 최소가 되려면 앞에 오는 숫자가 작아야 한다. 따라서 사람의 수 N 값을 입력받고 배열의 공간을 N만큼 선언하여 값을 삽입한 다음 오름차순 정렬한 뒤 한 변수에 += 연산을 하면 최솟값이 나온다. 코드 import java.io.*; import java.util.*; public class Main { public..

전위 표기법(PreFix) : +AB 중위 표기법(InFix) : A+B 후위 표기법(PostFix) : AB+ 다음과 같이 Infix 로 표기된 수식을 Prefix 로 변환하시오. X = A / B * ( C + D ) + E 항상 식에서 우선순위의 계산 먼저 시작한다. (괄호 > 곱셈,나눗셈 > 덧셈,뺄셈 순으로) 다음과 같이 Infix 로 표기된 수식을 Postfix 로 변환하시오. X = A / B * ( C + D ) + E 다음과 같이 Postfix 로 표기된 수식을 Infix 로 변환하시오. A B C - / D E F + * + 후위 표기법을 중위 표기법으로 변환할 때는 (피연산자 피연산자 연산자) 인지 확인 후 정리해야한다. 다음과 같이 Prefix 로 표기된 수식을 Infix 로 변환하..

스택은 배열 또는 연결리스트로 구현할 수 있다. 연결리스트로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다. 코드 부분설명▼ 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..