알고리즘
[백준] 10942번 - 팰린드롬?
이번 문제는 팰린드롬이라는 생소한 단어가 나왔는데, 문제에서 팰린드롬의 정의를 해주지 않아 인터넷에 팰린드롬이라는 단어를 찾아봤습니다. 위키백과에서는 palindrome을 회문이라 했으며, 회문이란 숫자나 문자를 정방향으로 읽어도, 거꾸로 읽어도 같은 숫자나 문자를 말합니다. 처음에 이 문제를 해결하기 위해서 각 위치에 맞는 짝을 찾아 비교하기 위해 규칙을 찾아보았는데, 따로 규칙을 찾을 필요없이 우리가 S, E를 선택했기 때문에 (S+i) = (E-i) 라는 규칙을 쉽게 생각 할 수 있었습니다. 그리고 이 문제 조건에서 시간 제한을 0.5초를 두었기 때문에 Dynamic programming을 이용해야 함을 알 수 있었습니다. int palin(int s, int e) { if (s >= e) { re..
[c++] 입력은 여러 개의 테스트 케이스로 이루어져 있다.
문제의 조건에 이런 까다로운 것이 있을 때, c++에서는 어떻게 해결하면 될까? ● 보통 c++을 사용하는 개발자들이라면 scanf 대신 cin을 많이 사용 할 것이다. cin에는 EOF라는 모듈이 있는데, eof 기능을 사용하면 쉽게 해결된다. int a, b; while (true) { cin >> a; if (cin.eof() == true) { break; } //여기에 결과 값 입력! } 여기서 주목해야할 점은 cin.eof인데 ctrl+x를 입력할 때 프로그램에 끝냄 명령을 주는데, 이때 cin에 입력받은 값이 없을 때 신호를 주면, cin.eof는 true값을 반환을 하여 while문을 빠져나오게 된다. 따라서, 쉽게 저 조건을 해결 할 수 있게된다. 궁금하신 것이 있으시다면 언제든지 댓글로..
[백준] 1725번 히스토그램 & [프알문] 울타리 잘라내기
이번 문제는 1725번 히스토그램인데, 프알문의 울타리 잘라내기 문제와 풀이 방식이 똑같아 포스팅하였습니다. 울타리 잘라내기와 마찬가지로 이 문제를 브루트포스로 접근하게 되면 시간복잡도가 너무 높으므로 분할 정복으로 접근하였습니다. 지금부터 울타리를 반으로 쪼개며, 확장을 하면서 분할 정복을 할 것입니다. 먼저 기저사례를 기본적인 분할 정복에서의 기저사례와 같은 left==right일시 기본 높이 값을 반환해주며, 그 후 left~mid, mid+1~right로 나누어 계산을 할 것입니다. 먼저 반으로 쪼개가며 확장을 시키면 모든 케이스를 확인 할 수 있습니다. 그렇기 때문에 반으로 쪼개가는 것이고, 확장을 시킬 때 왼쪽으로 갈지 오른쪽으로 갈지는 더 높은 케이스를 찾아가도록 설정을 해주었습니다. #in..
[백준] 1780번 종이의 개수
3의 제곱만큼 늘어나는 종이에서 같은 숫자를 가진 3^n 의 종이의 개수 -1,0,1를 각각 찾는 문제이다. 처음에 브루트포스를 접근을 하려 했지만, 시간이 어마어마하게 나올 것 같아서 분할 정복을 도입해봤다. 다행히 문제에 3^N 으로 늘어나며, 종이를 자를때도 3^N이라는 규칙에 맞게 자르기 때문에 쉽게 규칙을 찾을 수 있었다. 우선 findPaper 함수를 만들어 NXN의 크기부터 검사를 하도록 하고, 같은 숫자로 다 이루어지지 않을 시에 (N/3)X(N/3)으로 N개만큼 분할해서 다시 구하도록 재귀 함수를 구현해주었다. firstx와 firsty를 이용해 규칙에 맞게 그 종이를 구성하는 첫번째 인자만 가져올 수 있도록 해주었다. 또한 구성된 숫자를 검사할때는 checkNum 함수를 이용해서 쉽게 ..
[백준] 1012번 유기농 배추
유기농 배추에 배추흰지렁이의 마리 수를 구하는 문제이다. 이 문제를 풀기위해서 완전탐색을 이용했는데, 먼저 ground 2차원 배열을 생성해서 배추의 위치를 1로 표현을 해주었다. 그 다음으로 groundN 함수를 사용해 groundN함수를 호출 했을 때 ground[x][y]의 위치가 1이면 배추가 있는 곳이므로 다시 탐색을 시도했을 때 탐색을 하지 않게 하기위해 1에서 0으로 바꿔주었다. 또한 이어져있는 배추를 확인하기 위해 [0,1] [1,0] [-1,0] [0,-1]. 동서남북으로 다시 탐색을 해줘, 그곳에도 배추가 있으면 또 탐색을 못하도록 1에서 0으로 값을 계속 바꾸어주었다. 이렇게 하면 나중에 ground배열에서 배추가 있는 위치를 찾을 때 또 다시 찾을 수 없도록 해줄 수 있기 때문이다...
[백준] 2503번 숫자 야구
숫자 야구라는 타이틀만 보고 우리가 종종 해오던 쉬운 게임이라 생각하고 문제를 읽었더니, 알고리즘으로 짜기에는 복잡해보였다. 먼저 1~9의 숫자 중에서 선택을 해야했기 때문에 3자리 숫자 중 각 숫자에 맞게 겹치는 숫자들이 없어야하며, 0도 포함해서는 안됐었다. 먼저 각 숫자를 뽑아내기 위해 10의 제곱으로 나눠 각 자리의 수를 뽑는 방식을 택했었다. 그리고 배열에 넣고, 다른 숫자들과 비교하는 식으로 하였다. Strike는 각 자리에 맞아야하며, 두 숫자가 동일해야하고, Ball은 각 자리가 틀려야하며 두 숫자가 동일해야하므로 그에 맞게 조건문을 맞혀주었다. 개선해야할 점 : 각 숫자를 추출해내기 위해서 노가다 방식으로 일일히 다 뽑아내었는데 to_String을 사용하여 쉽게 뽑아낼 수 있다는 사실. ..