복습노트 복습노트

문제 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 숫자를 입력받아 삼각형을 만들 수 있으면 그중 가장큰 삼각형 세변의 길이를 출력하고 삼각형을 만들 수 없으면 -1을 출력하는 문제입니다. 삼각형이 이루어질 수 있는 조건은 세변중 가장큰변이 나머지 두변의 합보다 작으면 가능합니다. 코드를 보겠습니다. int n; cin >> n; vectorv(n); for (int i = 0; i > v[i]; } 먼저 변의 개수를 받아줄 n을 입력받고 벡터v에 넣어줍..

문제 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 간단히 버블소트가 몇단계 만에 완성되는지 출력하는 문제입니다. 버블 소트는 한단계 실행 할때마다 배열안의 가장큰수가 맨뒤로 갑니다. 하지만 단순히 문제안에 있는 코드를 배껴서 제출하면 시간초과가 납니다. 버블소트의 시간복잡도는 O(N^2)인데 N이 최대 500만 까지 가능하므로 500만 * 500만 이면 시간이 너무 많이 듭니다. 굳이 정렬을 진행하지 않고 몇단계 만에 정렬이 되는지를 구하는것이 관건입니다. 코드를 보겠습니다. int..

문제 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 간단한 머지소트 응용문제입니다. 그러다가 중간에 조건이 주어지고 그 조건에 들어가면 머지 소트를 멈추고 그대로 출력하는 문제입니다. 코드를 보겠습니다. int arr[1048577]; int tmp[1048577]; int n; int k; int main(){ scanf("%d",&n); for(int i=0;in/k) return; int idx1, idx2, idx3; idx1= idx3 = l; idx2 = m + 1; ..

문제 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 입력받은 숫자가 자리수를 계속 옮기면서 30의 배수가 되면 그 수를 출력하고, 30의 배수가 아니면 -1을 출력하는 문제입니다. 처음에는 아무생각없이 입력받는 수를 int형으로 담으려다가 말이 안되서 문제를 다시 읽었습니다. 알고보니 숫자가 10^5가 아니가 숫자의 개수가 10^5개 입니다. 엄청나게 큰수이므로 가장 큰 자료형을 써도 오버플로우가 날것입니다. 따라서 문자열로 받고 나중에 숫자로 변환해주는 방식을 취해줄것입니다. 두번째 관건은 그 엄청난 수를 계..

알고리즘 이란?? 문제를 해결하기 위한 절차 에를들어 서울 광화문에서 제주도로 가는 방법을 생각해봅니다. 1. 먼저 자신이 광화문 어디에 있는지 위치 파악을 합니다. 2. 위치파악을 끝냈으면 김포공항으로 갈 수 있는 가장 가까운 버스 정류장을 검색하고 갑니다. 3. 버스를 타고 공항에 도착하면 수속 절차를 끝내고 비행기를 타고 제주도로 갑니다. 결국 광화문에서 제주도로 가능 방법의 최종 목표는 '비행기 타기' 입니다. 즉, 우리는 문제가 주어졌을때, 최종목표를 파악하는 것이 중요합니다. 이를 위해 우리는 항상 올바른 답을 내야하고 유한한 시간 안에 종료를 해야합니다. 좋은 알고리즘 이란?? 이해할 수 있어야 하며, 간결해야 합니다. 주어진 자원의 한계를 생각해야 합니다. 알고리즘을 수행하는 데에 걸리는 ..

C언어 char a, b; scanf("%c", &a); scanf("%c", &b); printf("국어 성적은%c\n", a); printf("과학 성적은%c", b); 위의 코드를 살펴봅시다. char형 a와 b를 입력받아 그대로 출력해주는 코드입니다. char a 에 b를 입력하고 char b 에 f를 입력해보겠습니다. 하지만 실행 시켜보면 b를 누르고 엔터키만 눌렀는데 갑자기 다 출력 되고 프로그램이 멈췄습니다. 아직 char b를 입력도 안받았는데 프로그램이 멈췄습니다. 이유가 뭘까요? 바로 '버퍼'입니다. 우리는 여러 입력을 받을 때, 스트림을 사용하여 키보드와 프로그램을 연결시킵니다. 버퍼는 바로 키보드와 프로그램 사이에서 입력한 value를 더욱 효율적으로 연결하기 위해 존재합니다. 따라..

문제 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 전에 풀었던 요세푸스 문제에서 응용한 문제 입니다. 요세푸는 문제는 오직 한방향으로만 원형으로 이동하지만 이 문제는 양쪽 방향으로 다 이동할 수 있습니다. 따라서 양쪽 원소에 접근할 수 있는 덱(deque) 자료구조를 이용하였습니다. int n; cin >> n; dequed; for (int i = 0; i > k; d.push_back({ i + 1,k }); } 풍선의 개수를 변수 n을 통해..

문제 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 문장을 받아서 공백을 기준으로 뒤집어주면 됩니다. int T; cin>>T; cin.ignore(); 먼저 테이스케이스 T를 입력받습니다. 여기서 cin.ignore() 함수를 사용했는데 버퍼를 비워주는 역할을 합니다. 왜 여기서 버퍼가 제대로 안비워졌는지는 정확히는 모르겠습니다만 계속 버퍼가 안비워져서 cin.ignore()를 사용했습니다. 버퍼에 관한건 추가적으로 다시 조사하겠습니다. while (T--) { string st; getline(c..