본문 바로가기

전체 글

 (14)
[백준] 2750 수정렬하기 (합병정렬, 퀵정렬로 풀기) 퀵정렬 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 퀵정렬로 풀기 #include using namespace std; # define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) ) #define MAX_SIZE 1000 int sorted[MAX_SIZE]; // 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다. // 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다. /* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...rig..
[백준] 2204 (Java) 도비의 난독증 테스트 1. 문제 이해 단어의 개수를 먼저 입력을 받고, 0을 입력하면 종료한다. 단어의 개수를 입력받은 후에 사전상 가장 앞서는 단어를 출력하는 것이다. 문제 이해는 굉장히 쉬운것 같다. 2. 문제 풀이 나는 자바가 익숙하지 않기 때문에 푸는데 조금 오래 걸렸던것 같다.. 먼저 배열을 이용해야겠다는 생각을 하였다. String 배열 2개(arr, arr2) 를 만들어주고, arr 배열에 입력을 받는다. 이 배열안에 든 값끼리 대소문자를 구분해주지 않기 위해 toUpperCase 함수를 이용하여 모두 대문자로 변환을 하였다. 대문자로 변환을 한것을 arr2에 복사를 해주었다. 그리고, arr2에 있는 값들을 사전상 가장 앞서는 순서대로 정렬을 하기 위해 sort 함수를 사용한다. 마지막으로, arr2[0]번째를..
[백준] 2839 (Java) 설탕배달 1. 문제 이해 설탕의 봉지는 3kg, 5kg 만 있다. 예를들어, 설탕 18kg을 배달해야하려면, 5kg * 3 + 3kg * 1 = (총 4개) 또는 3kg * 6개로 배달할 수 있다. 하지만, 봉지의 최소개수를 출력해야하기 때문에 4개를 출력해야한다. 정확하게 킬로그램을 만들 수 없다면 -1을 출력해야한다. 2. 문제 풀이 먼저, 해당 문제를 c++, java 언어로 풀어보았을때, 크게 다르지 않다. 배달할 설탕(target)의 kg을 입력받고, bag 변수를 만든다. while루프로 돌려서 먼저, 봉지의 최소개수를 구하려면 3보다 큰수인 5로 나누어 떨어지면 봉지의 최소개수를 구할 수 있다. 따라서, 5로 나누어떨어질때마다 bag의 갯수를 증가시킨다. 하지만, 5로 나누어 떨어지지 않을 경우, 무..
[백준]1991 (C++) 트리문제 트리 (Tree) : 계층적인 자료를 표현하는데 적합한 자료구조 이진 트리의 표현 배열을 이용하는 방법 포인터를 이용하는 방법 전위 순회 : 루트 → 왼쪽자식 → 오른쪽자식 중위순회: 왼쪽자식 → 루트 → 오른쪽자식 후위순회: 왼쪽자식 → 오른쪽자식 → 루트 #include using namespace std; int arr[50][2]; //전위순회 void preorder(int n) { if (n == -1) return; cout > a >> b >> c; a = a - 'A'; if (b == '.') { arr[a][0] = -1; } else { arr[a][0] = b - 'A'; } if (c == '.') { arr[a][1] = -1; } else { arr[a][1] = c - 'A..
[백준] 5567 결혼식 (C++) 그래프 문제 그래프 1. 정의, 용어 그래프: 정점(V)와 간선(E)을 하나로 모아 놓은 자료구조 경로 : 정점인 시작점에서 다른 정점인 도착점으로 가는 간선이 연속되게 연결된것 순환 : 경로의 시작점과 도착점이 동일 인접과 부속 : 정점 u와 v가 연결되어, 간선 (u,v)가 있을때 정점 u와 v는 인접한다. 간선(u,v)은 정점u와 v에 부속된다 라고 표현 2. 종류 방향/무방향 그래프 가중치 그래프 3. 그래프 구현 방법 인접 행렬 인접 리스트 4. 탐색방법 DFS(깊이 우선 탐색) 시작정점에서 시작해 다음 분기점으로 넘어가기 전, 해당 분기를 모두 탐색하는 방법 BFS(너비 우선 탐색) 시작정점을 방문한 후, 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법 너비 우선 탐색 (BFS) : 0-1-2-3-4..
[백준]10828, 10845 (C++) 스택과 큐의 기본문제 [10828] 이 문제는 스택의 구현원리를 묻는것 같다. 스택이란, 후입선출(LIFO) 특성을 가지고 있다. 가장 먼저들어간 정보가 마지막에 나오고, 반대로 가장 나중에 들어간 정보가 가장 처음에 나오게 된다. #include #include #include using namespace std; int main() { stack s; //스택 int n; //횟수 cin >> n; string cmd; //명령어 int result = 0; //각 명령어의 결과값 for (int i = 0; i > cmd; //1. push if (cmd == "push") { int num; cin >> num; s.push(num); } //2. pop ( size 가 0이면 -1,0이..

티스토리툴바