알고리즘/백준(328)
-
2004 조합 0의 개수
끝자리에 있는 연속된 0의 개수를 찾는 문제다. 0이 나온다는 것은 10이 곱해졌는 얘기고, 10을 소인수분해하면 2, 5의 인수가 나오기 때문에 2, 5 중 최소 개수를 찾으면 된다 N 제한이 20억이기 때문에 20억을 모두 탐색하면서 나머지 연산을 할 수는 없다 빠르게 2, 5의 개수를 찾는 방법 [참고] https://ksj14.tistory.com/entry/BackJoon1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98 따라서 조합은 nCr = n! / ((n-r)!*r!) 이므로 각 값에 해당하는 2, 5의 개수를 각각 배열에 담아서 저장해서 마지막에 계산하면 된다. 분자와 분모는 -관계이기 때문에 빼주면서 최소값을..
2019.11.15 -
17299 오등큰수
오른쪽에 있는 수 중 가장 왼쪽에 있는 큰 수를 확인하는 것이기 때문에 오른쪽부터 탐색을 하면서 왼쪽이 우선이 되어야하므로 스택이라는 자료구조를 사용해야 한다 다만 횟수, 숫자 총 두 가지 정보를 확인해야므로 pair로 stack의 기본 자료형을 정한다 스택에서 뺀다는 의미는 결국, 자신의 왼쪽에 있는 수 기준으로도 자신이 들어갈 것이기 때문에 가장 큰 수라는 것을 알 수 있다 문제: https://www.acmicpc.net/problem/17299 깃허브주소: https://github.com/surinoel/boj/blob/master/17299.cpp
2019.11.15 -
스택 연결리스트로 구현하기
struct node *top으로 스택의 top으로 지정해서 malloc, free로 노드를 생성하고 삭제할 수 있다 [참고] https://www.tutorialspoint.com/cplusplus-program-to-implement-stack-using-linked-list
2019.11.15 -
17837 새로운 게임 2
새로운 게임 1에서 가장 밑에 있는 말 말고도 전체적인 말이 움직일 수 있는 기회가 주어지게 된다. 따라서 조건이 달라지게 되는데, 새로운 게임 1에서는 턴을 다 돌고나서 마지막에만 점검했는데 이 문제는 턴 과정에서도 4개 이상의 말이 쌓이면 답이 된다. 만일 이 조건에 대해서 검사하지 않았다면 마지막 예제에 대해서 7이라는 값이 도출될 것이다 다음 좌표가 범위를 벗어난다면 { 파란색 타일 } 아니라면 { if(흰 타일) else if(빨간 타일) else if(파란 타일) } 로 로직을 구분해서 구성했다 문제: https://www.acmicpc.net/problem/17837 깃허브주소: https://github.com/surinoel/boj/blob/master/17837.cpp
2019.11.14 -
17836 공주님을 구해라!
bfs문제로 검을 얻었을 때와 얻지 않았을 때의 최소거리를 구분해줘서 마지막 답에서 비교해서 최소값만 구하면 된다 문제: https://www.acmicpc.net/problem/17836 깃허브주소: https://github.com/surinoel/boj/blob/master/17836.cpp
2019.11.13 -
[삼성] 17825 주사위 윷놀이
시뮬레이션 문제로, 나한테는 삼성 기출 중에 상당히 까다로운 문제인 것 같다 시간복잡도 계산 시, 브루트 포스로 말의 순서를 정하면 2^20 * 10번의 주사위 * 최대 5번 = 약 5천만으로 1억 안에 해결할 수 있다. map으로 다음 위치로 하나씩 움직이는 점과 모든 말의 순서를 탐색한다는 점이 시간을 오래 걸리게 했다. 계속 틀렸던 이유는 dfs가 아닌 브루트포스로 접근했는데, 말이 움직이지도 못한 채 다음 턴으로 넘어가도 이 부분에서 쌓여진 합이 답의 일부분이 되었다. 그리고 브루트포스로 하니 확실히 0.3초가 걸리는, 효율적이지 못한 시간복잡도를 보였다 문제: https://www.acmicpc.net/problem/17825 깃허브주소: https://github.com/surinoel/boj..
2019.11.05