[C] 백준 | 10989번 코드 - 수 정렬하기 3
>문제 > 핵심 - 모든 값을 배열에 저장할 필요가 없다. - "이 수는 10,000보다 작거나 같은 자연수이다" >풀이과정 지금껏 qsort나 합병정렬, 버블정렬같은 학교에서 배운 정렬만 쓰던 나에게 엄청난 깨달음을 주게하는 문제다.. 평소에 하던대로 값을 배열에 모두 입력받은 후에 통으로 정렬을 하게되면 시간초과 혹은 메모리초과가 필연적으로 발생하게 된다. 힌트는 "이 수는 10,000보다 작거나 같은 자연수이다" 에 있다. 10,000보다 작은 자연수. 10,000칸 짜리 int 배열을 만든 후(0으로 모두 초기화), [입력받은 값 - 1]의 인덱스를 찾아 해당 값을 +1 해주는 방식을 떠올렸다. 솔직히 풀긴 풀었지만 힌트 안봤으면 나도 이런 생각을 전혀 못했을 것 같다. 틀에박힌 사고방식을 벗어나..
[C] 백준 | 10814번 코드 - 나이순 정렬
>문제 > 핵심 구조체 정렬 >풀이과정 구조체로 나이, 이름, 인덱스(가입순번)을 묶어 입력받은 다음, qsort를 이용해 정렬했다. 삽입정렬이나 선택정렬으로 짰으면 이중반복문을 돌면서 두가지 조건을 만족하는지 고려하면서 짜야해서 조금 생각이 많이 필요했을 텐데 qsort 함수는 그런게 필요없으니까 너무 쉽고 편하다. 그래도 내장함수만 쓰면 그러니까 선택정렬로 짜봤는데 시간초과가 떴다. 선택정렬은 O(n^2) 의 시간이 걸려서 그런 것 같다. 답은 맞게 나오니 뭐 공부한 셈 치자 >깨달은점 qsort는 빛이다 >코드 #define _CRT_SECURE_NO_WARNINGS #include #include typedef struct { int age; int idx; char name[101]; }memb..
[C] 백준 | 7568번 코드 - 덩치
>문제 > 핵심 반복문 돌면서 일일히 비교하기 >풀이과정 구조체로 몸무게, 키, 등수를 묶어서 값을 입력받고, 이중반복문을 돌면서 나보다 덩치가 큰 사람이 있으면 등수를 +1 한다. 크게 어렵지 않은 문제였다. >깨달은점 이 문제가 초등부 문제라는데에 충격받았다. 초등학생도 푸는걸 대학생이 못풀면 진짜 망신 망신 개망신당할 것 같다.. 공부 열심히하자.. >코드 #define _CRT_SECURE_NO_WARNINGS #include typedef struct { int weight; int height; int rank; }student; int main() { int i, j, n; student list[50]; scanf("%d", &n); for (i = 0; i < n; i++) { scanf..
>문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. [입력] 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. > 핵심 O(nlogn) 정렬방법 사용 / 중복처리 >풀이과정 합병정렬로 풀다가 merge 함수 부분에서 임시로 정렬된 값을 받을 tmp 배열을 calloc으로 할당하고 싶었는데 무슨 문제에선지 컴파일 에러가 자꾸 떴다. 할당 크기를 right가 아니라 (right + 1) 으로 하니 해결되었다. 그리고 qsort 함수 쓰니 정말 편하다. 앞으로도 애용해야겠다. 다만 주의해야 할게 형변환을 할때 int compar..
[C] 백준 | 2609번 코드 - 최대공약수와 최소공배수
>문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. [입력] 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. > 핵심 최대공약수, 최소공배수 개념 알기 최소공배수는 a * b / gcd(a,b) 로 구할 수도 있다. >풀이과정 최대공약수와 최소공배수. 대 1때 코딩 처음 배울때 만들어봤던 기억이 난다. 근데 문제를 보니 이거 중등부, 고등부 문제에 출제된 문제라고 한다. 난 중학생때 코딩이 뭔지도 모르고 C언어, 파이썬은 듣도보도 못했었는데.. 세상에 마상에 아무튼 풀고 나서 다른사람이 한 코드를 봤는데 "유클리드 호제법"이라는 알고리즘을 사용한 사람이 있었다. 나도 얼핏 알고리즘 기본서에서 봤던 ..
>문제 [중략] 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다. 따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다. 숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다. [입력] 첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다. > 핵심 나머지, 나누기 연산 활용하기 >..
[C] 백준 | 1181번 코드 - 단어 정렬
>문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 > 핵심 O(nlogn) 정렬방법을 이용하자(합병정렬, 퀵정렬, 힙정렬) >풀이과정 정렬. 대학교에 처음 들어와서 배우는 버블정렬부터 시작해 알고리즘 시간에 배우는 삽입, 선택정렬, 힙정렬, 합병정렬, 퀵정렬 등등등,, 종류가 참 다양하다. 예전에 수업자료 ppt에 있던거 캡쳐해서 가져왔다. 인터넷에 올려도 되겠지? 정렬도 안해본지 오래되니 다 까먹고 예전에 써뒀던 코드를 보니 너무 낯설었다. 감이 녹슬지 않게 꾸준히 알고리즘을 익혀둬야겠다는 생각이 들었다. 합병정렬은 그나마 뭔가 직관적이고 할만한데 정석적인 퀵정렬을 직접 만드려니 도저히 모르겠어..
>문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 ..