궤도

문제 풀이 이 문제에서 가장 중요한건 두가지이다. 하나는 중복을 제거하는 것이고 남은 하나는 c가 가장 긴 변이 되도록 하는 것이다. i와 j를 이용해 a와 b변의 길이를 정하고 총 길이 n에서 이 둘을 뺀 값이 c가 되도록 한다. 반복문을 보면 알겠지만 i

문제 풀이 그리디 알고리즘의 대표적인 문제이다. 해당 문제가 그리디 알고리즘으로 풀릴 수 있는 조건은 잔돈이 서로 배수관계여야 한다는 것이다. 예를 들어 잔돈이 10원, 7원, 1원이고 거스름돈이 14원이라면 7원 2개가 optimal choice지만, 그리디 알고리즘은 10원 1개, 1원 4개 총 5개를 지불해야 한다는 결과를 내놓는다. 다시 문제로 돌아가면, 해당 잔돈들을 coins 배열에 저장하고 가장 큰 잔돈부터 대입해보며 동전의 수를 더해나간다. 더이상 지불해야 할 거스름돈이 없는 경우에도 의미없이 반복문이 돌아가는 경우를 막고자 조건을 하나 더 추가했다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include int main() { int coins[6] = { 50..

문제 풀이 입력이 숫자니까 int로 받아야한다는 생각에서 벗어나면 금방 풀린다. 숫자를 문자열로 받고 각 자릿수에 접근하기 쉽다는 문자열의 특성을 이용해 양끝에서부터 비교하면 된다. 홀짝을 나눌 필요는 없다. 코드를 보면 알겠지만 가운데 숫자라면 자기자신과 비교하게 된다. 일치하지 않는 부분을 발견하는 순간 isPal을 false로 바꿔주고 반복문을 빠져나오면 된다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include int main() { char num[101]; bool isPal = true; scanf("%s", &num); int length = strlen(num); for (int i = 0; i < length / 2; i++..

문제 풀이 이번에 정답일 경우 얻게될 점수를 저장하는 tmp_score와 얻은 점수의 총합을 저장할 sum 변수가 필요하다. tmp_score는 처음에 0으로 초기화하고 O라면 하나 증가하고 X라면 0으로 다시 초기화 한다. O일 경우 tmp_score를 증가함과 동시에 그 결과를 sum에 바로 더해준다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include int main() { char score[1001]; int tmp_score = 0, sum = 0; scanf("%s", &score); for (int i = 0; i < strlen(score); i++) { if (score[i] == 'O') { //O면 현재 스코어를 증가하고 sum에 합침 ..

문제 풀이 a, b를 입력받고 둘 사이의 최대 공약수를 구하는 문제이다. 원래는 유클리드 호제법을 사용하는게 정석이겠지만...난 너무 귀찮았다. a b) { //a가 더 작도록 int tmp = a; a = b; b = tmp; } if (b % a == 0) //a가 최대공약수인지 확인해보고 printf("%d\n", a); else { for (int i = a / 2; i >= 1; i--) { //a 나누기 2 부터 검사 if (b % i == 0 && a % i == 0) { printf("%d\n", i); break; } } } }

문제 풀이 재귀함수를 배울 때 꼭 나오는 하노이탑이다. 자매품으로는 피보나치 수열이 있다. 보통은 이동 횟수를 계산하게 하는 경우가 많은데 이건 어떤 원판이 어떻게 이동했는지까지 출력해야 한다. 귀찮아보이지만 어려운 일은 아니다. 하노이탑에 대한 설명은 널리고 널렸지만 굳이 내가 또 적어보겠다...n개의 원판을 A에서 C로 옮기고 싶다면 먼저 위에 쌓인 (n-1)개의 원판을 A에서 B로 옮긴다. 그리고 n번째 원판을 A에서 C로 옮기고 남은 (n-1)개의 원판을 B에서 C로 옮기면 된다. 상황에 따라 source, tmp, dest 인자를 서로 옮겨가며 재귀함수를 호출하고 출력하면 된다. 아무리 생각해도 나보다 친절하게 설명한 다른 블로그가 많을 것 같다. 소스코드 #define _CRT_SECURE_N..

문제 풀이 백트래킹 문제다. 도대체 어디에 백트래킹이 들어가냐고 물어본다면 팀 나눌 때 들어간다. 백준에서 비슷한 문제를 풀 때는 친절하게 인원은 모두 짝수라고 했었는데, 여긴 홀수도 있다. 뭐...그렇게 크게 달라진 부분은 없다. promising한 노드만 적었다. promising의 조건은 상위 노드보다 큰 index여야 한다는 것이다. 왜냐면 (0,1)/(2)랑 (1,0)/(2)는 차이가 없기 때문이다. 이런 방법으로 중복을 제거하면 조합같이 보인다. 이를 구현하기 위해 make_team 함수의 인자가 2개인 것이다. now는 상위 노드의 인덱스값을 알기 위해 사용하고, cnt는 그래서 지금 팀에 몇 명이 모였는지 알기 위해서 사용한다. 그러니 메인에서의 호출도 make_team(0, 0)인 것이다..

문제 풀이 스택을 처음 배울 때 한번쯤 보았을 후위표기법이다. 개념은 어렵지 않았으나, c에서 char 변수를 받을 때 주의해야 할 점을 까먹어서 좀 고생했다. 입력 예를 보면 알겠지만 중간중간 공백이 있다. character 단위로 입력을 받을 때는 공백도 입력으로 처리하기 때문에 입력을 처리할 input 변수와 더불어 공백을 처리할 empty 변수도 필요하다. m을 입력한 뒤 입력한 엔터도 char에 들어가니 저것도 empty 변수로 빼줘야 한다. 아무튼 첫번째 입력은 무조건 숫자일테니 char로 받은 숫자를 int로 바꿔서 num1 변수에 저장한다. 그 다음부터 반복문을 돌며 계산한다. 새로운 숫자가 입력된다면 int로 바꿔서 num2 변수에 저장한다. 그 이후에 연산자가 등장하면 해당 연산자에 따..