본문 바로가기

전체 글

백준 15684 사다리 조작 좀 신박한 문제같아서 골랐다. 처음엔 이 섞는거 조건을 찾아야 하나... 하며 조건을 일일히 찾아보려 했다. 하지만 그렇게 푸는게 아니었다. 고민을 해보다가 좀 검색해봤다... 예상보다 간단했다. 가로 선을 그을 수 있는 경우의 수 공간을 탐색하는 방향으로 문제를 풀면 되었다. DFS를 사용해서, 가로선을 긋는 경우의 수 공간을 탐색한다. 만약 가로선이 4개 이상 그어진 상태면 종료한다. -> 3개 초과일 경우 -1을 출력하므로 각 상태에서 game_check()을 통해 모든 세로선이 자기 자신으로 돌아오는지 확인한다. -> 돌아오는것을 확인하면, 그 값을 answer와 비교해 최소값으로 갱신한다. 로직을 글로 써보니 되게 간단한데, 처음 아이디어 떠오르기가 너무 어려운것 같다. #include #inc.. 더보기
백준 1339 단어 수학 초등학교때 많이 보던 문제를 컴퓨터를 가지고 해결해보는 문제이다. 최대 10종류의 알파벳 대문자로 이루어진 단어를 숫자로 생각하고, 그 숫자들의 합이 최대가 될 때의 값을 구한다. 처음 접근했을때는, DFS 검색으로 조합들을 검색했다. 단어들을 구성하는 문자가 7개라면, 7!의 경우의 수 공간을 탐색하면서 최대값을 찾았다. -> 답은 나왔지만 시간초과가 떴다. 두번째 접근은, 그리디로 접근했다. 각 문자별로 자리수의 합을 구해서 높은 자리수에 많이 있는 숫자부터 높은 수를 할당해줬다. ABC + ACB = 2*A*100 + B*10 + C*10 + C + B이므로, A의 자리수 합은 200이 된다. 이렇게 각 문자의 자리수 합을 구한 뒤, 높은것부터 높은 수를 할당해서 계산해보니 답이 딱 나왔다. 중간에.. 더보기
백준 13908 비밀번호 브루트 포스 문제이다. 근데 진짜 빼박 브루트 포스로 전체 탐색을 돈다... n자리 수 공간을 탐색하면서 꼭 들어가야 하는 숫자가 없으면 출력하지 않고 들어간다면 가능성 있는 비밀번호이므로 출력한다. 비교는 단순하게 string으로 바꿔 각 자리수를 비교했다. 숫자가 커진다면 스트링으로 확인할때 메모리 문제나 속도에 문제가 있을 수 있을것 같다. 속도가 문제라면 숫자 변수형이 아닌, 다른 자료구조를 사용해(배열이라던가...) 숫자가 사용되는지 여부를 확인할 수 있을 것 같다. 하지만 이 문제는 7자리가 끝이다. 허허... 빡 탐색으로 구현했다. #include #include #include int main() { int n, m, cnt = 0; std::vector knowing; std::cin >.. 더보기
백준 1747 소수&팰린드롬 특정 수를 입력받고, 그 수보다 크면서 팰린드롬인 수를 출력한다. 간단하게 구현했다. 팰린드롬인지 확인하는 함수와, 소수인지 확인하는 함수를 짜서, 입력받은 N 이후 하나씩 늘려가며 확인했다. 팰린드롬인지 확인하는 함수는 해당 숫자를 스트링으로 만들어 뒤집은 다음 뒤집은것과 뒤집지 않은 것이 같은지 확인했다. 소수인지 확인하는 함수는 그냥 간단하게 숫자 n 을 2부터 n/2까지 나눠가며 나눠지는지 확인했다. 이 두 함수를 가지고 숫자를 늘려가며 확인했다. 간단하다. #include #include #include #include bool check_prime(int num) { if (num == 2) return true; if (num % 2 == 0 || num < 2) return false; i.. 더보기
백준 1107 리모컨 브루트 포스 문제이다. 몇 버튼이 고장난 리모콘을 가지고 특정 숫자를 만들건데, 그것이 최소가 되는 경우를 구해라! 이다. 우리가 어떤 채널에 접근할 때는 크게 두 가지 방법이 있다. 현재 채널에서부터 노가다로 하나씩 올리거나 내리는 방법, 그 채널 숫자를 직접 눌러 접근하는 방법. 근데 숫자 버튼 몇개가 고장나면 해당 채널 숫자를 직접 누를 수 없을 가능성이 생긴다. 이 때는, 현재 쓸 수 있는 버튼으로 접근 가능한 가장 가까운 채널로 이동한 뒤 가고싶은 채널로 한 채널씩 이동한다. 이 두가지 방법으로 이동 횟수를 구한 뒤, 낮은 횟수를 구하면 된다. 노가다로 이동하는 방법은 그냥 abs(가고싶은 채널 - 100) 을 하면 된다. 가고싶은 채널에 인접하면서 현재 리모콘으로 갈 수 있는 채널은 가고싶은 .. 더보기
백준 1759 암호 만들기 브루트포스 알고리즘을 사용하는 문제를 찾아서 풀어보았다. 순서대로 조건에 맞는 문자열의 모든 경우의 수를 출력하면 된다. 다른 코테에서 풀어본 적 있는 문제라 유사하게 풀어봤다. 사용 가능한 문자들을 입력받은 뒤, 알파벳 순으로 정렬한다. 그 배열을 사용해 DFS로 한 글자씩 붙여가며 탐색을 한다. 길이를 확인해 우리가 원하는 길이가 되면, 조건을 확인한다. 여기서 조건은 모음과 자음의 개수이다. 조건이 맞으면 출력한다. 알파벳순으로 문자들을 정렬했기에 조건에 맞을때마다 출력하면 된다. #include #include #include #include int l, c; std::vector alpha; bool checkVowel(std::string cur) { int Vowel = 0; int Cons.. 더보기
백준 1300 K번째 수 이진 탐색 문제 중, 조금 특이해 보여서 풀어보았다. 처음에 그냥 행렬만들고 정렬해서 하면 되겠지 하다가 골드 3인거 보고 아 안되겠구나 했다. 이거 문제를 어떻게 접근해야하나 고민하다가 답이 안나와서 좀 찾아봤는데, 조금 머리를 써야되는 풀이였다. 만약 이 배열 B에서 11번째, 즉 B[11]을 찾고 싶다고 가정하자. B[11]의 숫자가 x라고 하면, 전체 숫자 중에서 x보다 작거나 같은 숫자의 수가 11보다 작으면 안된다. 만약 작다면, x가 더 커져야 한다. 이 (전체 숫자에서 x보다 작거나 같은 숫자의 수)를 가지고 이진 탐색을 한다. 그렇다면 이 (전체 숫자에서 x보다 작거나 같은 숫자의 수) 는 어떻게 구하느냐 하면, 각 행별로 계산을 접근해본다. 각 행은 i*1, i*2, i*3.... 의 .. 더보기
백준 1981 배열에서 이동 이진탐색 좀 여려워 보이는 문제를 잡았다. 단순히 배열의 값에서 탐색해서 값을 찾는것이 아닌, 뭔가 2D 맵을 탐색하는 문제이다. 2차원 배열의 0,0에서 우하단 자리인 n, n까지 이동할때, 전체 경로의 최대값과 최소값 차이의 최소를 찾는 문제이다. 문제 풀이는 어떻게 되냐하면, 경로상 최소-최대 값 차이가 정해졌을때, 이 경로로 갈 수 있는지 탐색하는 bfs 함수를 만든다. 이 함수를 이용해 diff값을 이진탐색을 하며 찾는다. 처음 diff값은 (start=0, end=(맵 max - 맵 min))이고, mid값은 start와 end값의 중간이다. 만약 mid값으로 탐색이 가능하다면, 우리는 더 낮은 diff값으로 탐색을 해야한다. 여기서 end = mid - 1로 갱신하여 또 탐색을 한다. -> .. 더보기

티스토리툴바