개발을 위한 하루 개발을 위한 하루

백준 algorithm

• 백준 1463 - 1로 만들기

  백준 algorithm 2020. 4. 6. 00:34

  => DP 문제이다. => 내가 구해야 하는 것을 우선적으로 문자로 써본다. 내가 구하고자 하는 것 : N 을 1로 만드는데 필요한 최소 연산 횟수 가능한 경우의 수 : 1. i 가 3으로 나누어 떨어질 때 - arr[ i/3 ] + 1 2. i 가 2로 나누어 떨어질 때 - arr[ i/2 ] + 1 3. i 에서 1을 뺄 때 - arr[ i - 1 ] + 1 => 위의 경우 세 가지가 있는 것을 알 수 있다. => DP에는 Top-down 방식과 Bottom-up 방식이 있다. => 본인은 Bottom-up 방식을 선호한다. (Top-down은 재귀를 쓰는데, 재귀를 쓰다 보면 헷갈린다....) *** 둘 중 어느것이 좋다는 것은 없다. 본인이 원하는 방식으로 사용하면 된다. #include #inc..

  Read More
• 백준 11653 - 소인수분해

  백준 algorithm 2020. 4. 5. 23:27

  => 소인수분해를 프로그래밍으로 구현하는 문제이다. => 오름차순은 for문이 2부터 n까지 올라가기 때문에 따로 신경쓰지 않아도 된다. ***소인수분해 알고리즘 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for(int i=2; i*i

  Read More
• 백준 11576 - Base Conversion

  백준 algorithm 2020. 4. 5. 23:15

  => 해당 문제는 원래의 A진법의 수를 10진법으로 바꾼 후, 정이가 사용하는 B진법으로 바꾸는 문제이다. => A진법을 10진법으로 바꾸기 위해서 아래의 문제를 확인하면 된다. https://codingham.tistory.com/117 백준 2745 - 진법 변환 => 진법 변환 2와 달리 B 진법으로 표시되어 있는 수를 10진법으로 변환하면 되는 문제이다. *** 참고 : https://codingham.tistory.com/116 백준 11005 - 진법 변환 2 => 간단한 진법 변환 문제이다. => 진법 변.. codingham.tistory.com =>10진법을 어떠한 n 진법으로 바꾸기 위해서 아래의 문제를 확인하면 된다. https://codingham.tistory.com/116 백준 ..

  Read More
• 백준 2745 - 진법 변환

  백준 algorithm 2020. 4. 1. 01:40

  => 진법 변환 2와 달리 B 진법으로 표시되어 있는 수를 10진법으로 변환하면 되는 문제이다. *** 참고 : https://codingham.tistory.com/116 백준 11005 - 진법 변환 2 => 간단한 진법 변환 문제이다. => 진법 변환의 알고리즘을 알아야한다. ex) 11 을 3진법으로 나타내고자 한다. 11 / 3 = 3 ... 2(나머지) 3 / 3 = 1 ... 0 1/3 = 0 ... 1 =>의 결과로 102(3) 의 결과를 얻을 수.. codingham.tistory.com => 알고리즘 B 진법 수 N 을 10진법으로 나타내기 102 (3) = (1 *3^2) + (0* 3^1) + (2* 3^0) 위의 식처럼 각 수에 따라 승수는 줄어들게 되고 각 자리에 해당되는 수를 ..

  Read More
• 백준 11005 - 진법 변환 2

  백준 algorithm 2020. 4. 1. 01:05

  => 간단한 진법 변환 문제이다. => 진법 변환의 알고리즘을 알아야한다. ex) 11 을 3진법으로 나타내고자 한다. 11 / 3 = 3 ... 2(나머지) 3 / 3 = 1 ... 0 1/3 = 0 ... 1 =>의 결과로 102(3) 의 결과를 얻을 수 있다. => 위와 같은 알고리즘을 실행하기 위해서는 stack을 사용하면 손쉽게 해결할 수 있다. => stack 은 두개의 다른 자료형을 넣을 수 없다. => 10이 넘는 숫자는 A .... Z로 표현할 수 있다. => 아스키코드를 이용하여 해당 숫자를 표현하였다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(..

  Read More
• 백준 1157 - 단어공부

  백준 algorithm 2020. 3. 29. 12:03

  => arr : 알파벳을 하나씩 담을수 있는 26 크기의 배열이 필요하다 => 각 index를 탐색하며 해당 알파벳이 나올때, 해당하는 arr 의 값을 올려준다. A B C ... Z 0 1 2 ... 25 => 위의 배열은 각각의 알파벳을 지칭하고 원소값을 string에 나온 알파벳의 개수를 세어준다. => arr을 완성시킨 뒤, index 순서대로 올라가면 최대 크기를 가지고 있는 index 를 찾는다. => 이 경우 최대 크기를 가지고 있는 inde가 다수일 경우를 위해 rep 이라는 bool 변수를 사용했다. => 다수일 경우, ?를 출력한다. => 다수가 아닐 경우 해당하는 알파벳을 출력한다. *** 이 코드는 보기엔 간단하지만, 효율성이 좋지 않다. 다른 사람들의 코드를 보면 0ms도 나온다...

  Read More
• 백준 2675 - 문자열 반복

  백준 algorithm 2020. 3. 26. 21:44

  #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; string S; while(N>0) { int rep; cin >>rep; cin >> S; int len= S.length(); for(int i=0; i

  Read More
• 백준 10809 - 알파벳 찾기

  백준 algorithm 2020. 3. 26. 21:24

  => 배열을 사용해서 간단히 풀 수 있는 문제이다. => 배열 index를 접근하기 위해 해당 값에 'a'를 빼줘야 하는 것을 알아야한다. ***컴파일에러 본인은 아래의 함수를 이용하여 배열 초기화를 했었는데 해당 함수는 GCC 컴파일러에서만 작동한다. int arr[26]={[0 ... 25]=-1}; visual studio에서는 아래 함수를 통해서 배열 전체를 초기화 할 수 있다. int arr[26]; fill_n(arr, 26, -1); #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //int arr[26]=..

  Read More