알고리즘/Baekjoon

[C++] 백준 15649번 N과 M (1)

백트래킹의 기본적인 문제. 백트래킹 알고리즘을 알고있다면 쉽게 접근할 수 있는 문제이다. 백트래킹이란? 기본적으로 백트래킹은 '가능한 모든 방법을 탐색'한다는 데 그 기본 아이디어가 있습니다. 이 아이디어의 구현은 DFS, BFS 둘 다 가능한 방법입니다. 다만, 백트래킹은 보통 '불가능한 방법'임을 인지한다면 이전 상태로 돌아오는 작업이 필요한데 이는 큐를 사용하는 BFS보다는 스택(혹은 재귀)을 사용하는 DFS가 더 편하기 때문에 일반적으론 DFS를 사용합니다. 출처 : https://www.acmicpc.net/board/view/15738 - simm4256님 댓글 참고 쉽게 말해서 내가 길을 가다가 이 길이 아닌거 같으면 돌아가서 다른 길로 가는 것을 뜻한다. 물론 경우의 수가 상당히 많으로 시..

[C++] 백준 1011번 Fly me to the Alpha Centauri

처음 문제를 접근 했을 때 백트래킹으로 풀려고 시도했다. 재귀함수로 모든 경우를 돌면서 최소로 접근할 수 있는 것으로 계속해서 갱신하려고 했다. 구현은 했는데, 메모리 초과가 나면서 풀지 못했다. 단계별로 풀어보기에서 발견한 문제였는데, 분야가 수학이였다. 결국 조금 도움을 얻고자 게시판을 조금 검색해서 규칙성이 있다는 것을 얼핏 보았다. 그래서 이 규칙성을 가지고 어떻게 구현을 해야할까 고민했지만 결국 해답을 얻지 못했다. 글 읽기 - 풀이 정리해 보았습니다 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 그러다가 게시판을 찾던 중 이런 글을 발견했고, step마다 갈 수 있는 거리가 정해져 있다는 것이였다. 이동 횟수 과정 이동 거리 1 1 1 2 1 1 2 3 1 2 1 4 4 1..

[C++] 백준 1436번 영화감독 숌

처음에 이 문제를 봤을 때 문제를 처음 봤을 때 666, 1666, 2666 ... 이런식으로 흘러가는 건 이해를 했다. 근데 너무 쉬워서 그냥 N - 1 출력하면 되는 게 아닌가 생각했는데 아무리 생각해도 너무 쉬워서 문제를 계속 읽었다. 함정은 6이 연속으로 3번 들어가면 그게 영화의 번째수가 된다는 것. 7번째는 따라서 6666이 아니라 6660이 된다는 것이다. 접근한 방식 처음에는 모든 경우의 수를 나누려고 했다. 맨 처음에는 모든 경우의 수를 다 생각하려고 했다. 그러다 보니 문제가 고려할 부분도 상당히 많아졌고, 맞았다고 생각해도 틀렸습니다 가 나왔다. 결국 이 방법으로 1, 2시간 고민하다가 이건 아닌 것 같아서 다 지우고 새롭게 생각했다. 1000씩 더하는 게 아니라 1씩 더해봐서 6이 ..

[C++] 백준 1920번 수 찾기

이런 문제를 보면 바로 이분탐색부터 떠올려야 한다. big-O 표기법에 따르면 탐색 알고리즘에서 가장 시간소요가 적은 것이 O(NlogN)인데 쉽게 접근할 수 있는게 이분탐색이다. STL 제약이 없기 때문에 vector에 값들을 넣은 후 algorithm STL을 사용해서 sort와 binary_search 메서드를 사용했다. 이렇게 풀면 정말 가볍게 풀 수 있지만 이분 탐색 정도는 구현을 하라는 목적인 것 같았다. head와 tail (보통 left와 right로 표현하는 것 같다.) 그리고 mid를 정해놓고 남은 살펴볼 개수를 절반씩 줄여나가는 방식이다. 물론 STL을 사용할 수 있다면 그냥 algorithm STL을 사용해서 만들면 된다. (사실 STL 없이 sort하라고 하면 정말 답없을 것 같다..

[C++] 백준 1018번 체스판 다시 칠하기

오랜만에 풀어보는 알고리즘 문제였다. 어려운 문제는 아니고 손풀기 목적으로 골라본 문제였다. 처음 이 문제를 봤을 때 내가 접근했던 방식은 백트래킹을 생각했었다. 그리고 큐를 사용해서 후위표기식 느낌으로 모든 줄마다 push해서 pop했을 때 같은 색깔이 두 번 나오면 바꿔야되는 색을 하나씩 늘리는 것을 생각했다. 그런데 이렇게 할 경우 고려해야하는 예외의 경우가 너무 많아져서 포기했다. 후에 접근한 방식 문제를 다시 한번 잘 읽어보니, 체스판을 색칠하는 경우가 두 가지 뿐이라고 나와있었다. 즉, 내가 고려해야 하는 경우의 수는 두 개 뿐인 것이다. 좌상단이 검은색으로 시작하거나, 흰색으로 시작하거나이다. 이렇게 하면 모든 경우의 수를 다 고려할 수 있다. 보드를 나타내는 변수, n과 m을 나타내는 변수..