본문 바로가기
반응형

알고리즘/BOJ

2745번 2745번 - 진법 변환 B진법 수 N을 10진법으로 바꾸는 방법. 예를 들면 2진법의 수 1011 => ( 1*2^3 )+( 0*2^2 ) + ( 1*2^1 ) + ( 1*2^0 ) 이런식으로 각 자리의 숫자와 변환할 자릿수의 거듭제곱으로 나타낼 수 있다. string 을 이용해서 맨 앞자리부터 substr 을 이용해서 줄여가면서 문제를 풀 수 있었다. (예를 들어 hello 라는 string 변수를 substr(1)을 하면 ello 라고 변하게 된다는 점을 이용했다.) size는 while 문 밖에서 선언하여 계속해서 줄여가면서 거듭제곱을 구했다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include#incl.. 더보기
11005번 11005번 - 진법 변환2 내가 약간 진법이 약해서 문제를 풀어보았다. 계속 나누고 몫과 나머지를 이용해서 진법을 변환시킨다. 문제에서 숫자와 문자를 모두 표현해야 했기에, char 형 배열에 숫자도 문자화해서 한꺼번에 처리했다. 그리고 stack 을 이용해서 가장 나중에 들어간 값이 가장 처음에 나오도록 해서 정답을 출력했다. 123456789101112131415161718192021222324252627282930313233#include#includeusing namespace std; int main(){ int N, B; char num[36] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I', 'J.. 더보기
9613번 9613번 - GCD 합 최대공약수 응용문제, 아마 유클리드 호제법이 아닌 방법으로 풀면 시간초과가 날 것 같다. 유클리드 호제법을 이용해서 문제를 풀었다. 정답은 int 형 범위를 넘을 수 있으므로 유의! 유클리드 호제법 - A,B 라는 숫자가 있을 때, GCD(A,B)=GCD(B,B%A) (단, B%A가 0 이면 B가 최대공약수가 된다.) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include#include using namespace std; int gcd(int a,int b){ if (b == 0) { return a; } else { return gcd(b, a%b); }}i.. 더보기
1850번 1850번 - 최대공약수 한 1년전에 못 풀었던 문제를 풀어보았다. 처음에도 너무 큰 수라 당황했지만, 잘 살펴보니 쉬운 문제였다. 숫자에 집착을 버리고 문제를 봤더니 답이 보였다고나 할까?ㅋㅋㅋㅋ 아무튼 그냥 주어진 입력에 대해서 최대공약수를 구하는 문제였다, 그리고 그 만큼 1을 출력하면 끝. 쉬운 문제지만, 옛날 문제를 풀면서, 최대 공약수, 최소 공배수에 대해 다시 공부해보았다. 꼭 함수 인자를 무의식적으로 int를 써서 AC를 못받는 실수 고치기.... 최대 공약수 구하는 방법 - 2부터 두수의 미니멈까지 나누기. - 유클리드 호제법 ( 재귀, 비재귀) 최소 공배수 구하는 방법 - 최대공약수로부터 구하기. 12345678910111213141516171819202122232425262728293.. 더보기
2448번 2448번 - 별찍기 - 11 유사한 삼각형이 반복되고 있기 때문에, 분할정복 과 재귀를 이용해서 문제를 풀었다. makeTri 에서는 이 삼각형까지 최소로 찾아내고, makeSmallTri 에서는 이 삼각형을 그려내는 방식으로 문제를 풀었다. 분할을 두번 사용했는데... 사실 이렇게 까지 해서 푸는게 맞는 방식인지는 모르겠다. 내 판단대로 풀었다. 그런데 큰 삼각형 분할해서 재귀를 들어갈 때, 제일 작은 삼각형이랑 큰 삼각형이랑 재귀가 맞지 않다고 생각했다.( 합동이 아니다는 뜻) 왜냐하면 작은 삼각형은 맨 아랫줄은 꽉 차 있지만, 큰 삼각형은 한칸이 비어있기 때문에 재귀로 다시 더 들어갈 수 없다고 생각했다. 그래서 큰 삼각형까지 최대한 줄이고 (n ==6 이 될 때까지, n은 삼각형의 아랫변이 아닌.. 더보기
2447번 2447번 - 별찍기 10 규칙을 찾아서 해결하는 문제. 문제의 조건에서 3의 k 제곱으로 주어진다고 했으므로 뭔가 3이나 9와 연관이 있는 규칙이 있을거라 추측이 가능했다. 그래서 보니 9개로 나누었을 때, 재귀적으로 반복되는 것이 보였다. 따라서 분할정복의 방식으로 분할하고 재귀로 푸는 방법으로 접근했다. * 풀면서 발생했던 문제 - 나는 별을 재귀함수 내에서 곧바로 출력하는 방식으로 문제를 풀려고 했었다. 내가 다른 별찍기 문제를 풀었던 것처럼... 근데 그러다보니 분할 정복인데, 분할 정복이기 때문에 같은 줄에 1사분면과 2사분면을 배치하는 것이 불가능했다... 이를 굉장히 오랜시간 뒤에 깨달았다.. 물론 푸는 도중에 배열을 사용해서 할까 하다가도 스스로의 고집 때문에 계속 같은 방식을 고수했다... 더보기
1517번 1517번 - 버블 소트 #########다시 풀어보기########### 분할 정복을 조금 알아갈 것 같은 느낌... 아직도 어렵다 사실 버블 소트가 일어날 때, swap 되는 횟수를 구하는 문제. 처음에 어 쉽네? 하고 N값을 봤더니 50만, 그냥 이중 for문을 통해서 O(N^2) 으로 구하면 구할 수 없는 시간이었다. 그래서 생각해낸 방법은 분할 정복을 써야할 것 같은데..까지밖에 생각 못 했었다. 오래 고민하다가 다른 분들의 풀이를 보고, 아 그런 방법이 있구나 하고 풀었다. 그냥 병합 정렬을 하면서 숫자를 세는 간단하지만, 생각해내지 못한 방법이었다. 병합 정렬에서 왼쪽그룹, 오른쪽 그룹은 항상 오름차순으로 정렬이 되어있다. 따라서 정렬되어져 있는 왼쪽 그룹 사이 사이로 오른쪽 그룹의 숫자가 .. 더보기
1992번 1992번 - 쿼드 트리 분할 정복 문제. 말 그대로 분할해서 문제를 풀고 합친다. 반복 되는 부분을 재귀로 구현했다. 주어진 영상이 하나의 수로만 표현되어 있지 않다면 !perfect 로 4분할을 하게 된다. 하지만 영상이 하나의 수로 perfect 하다면 그 숫자를 출력하면 된다. string 쓰는 법을 잘 몰라서 그냥 + 로 계속 덧 붙여서 저장하였다. 함수의 인자로는 시작하는 x좌표 sx, 시작하는 y좌표 sy, 맵의 크기 N으로 구성하였다. 재귀는 단순하게 생각하자... 재귀는 단순하게... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include#i.. 더보기
반응형

티스토리툴바