본문 바로가기

BOJ

Baekjoon 5568 카드 놓기 2019. 8. 19. Link https://www.acmicpc.net/problem/5568 소스결과 2364 KB / 64 ms 출처 Baekjoon 언어 C++ 17 분류 브루트포스, 이분탐색 설명 n 개의 카드중 k를 사용하여 만들 수 있는 정수의 모든 경우를 출력해주자. 딱봐도 모든 경우에 대해서 전수조사후 Map이나 Set에 모두 넣으면 되는 문제다. 알면서도 다르게 귀찮게 풀어보는게 이번 문제의 재미인거 같다. 새로운 값을 발견 할 때마다 이분탐색을 통해 해당 값이 존재하는지 확인 후, 존재하지 않으면 vector에 넣은 후 정렬을 반복하는 방식을 선택했다. 알고리즘 1. n개의 카드를 입력받는다. 2. n개중 k개를 선택하는 순열을 반복한다. 3. 기존 값 * 이번에 선택하는 카드의 자리수 + 이번 카드를 다..
Baekjoon 5557 1학년 2019. 8. 19. Link https://www.acmicpc.net/submit/5557/14656614 소스결과 2004 KB / 0 ms 출처 Baekjoon 언어 C++ 71 분류 다이나믹프로그래밍 설명 0 ~ 20밖에 모르는 상근이의 엄청난 도전을 응원하며 몇개의 올바른 등식을 만들 수 있는지 확인하자 브루트포스로 당연히 안되는걸 알면서 도전은 해보았다. 결과적으로 바로 시간초과가 나오긴한다. 최대 범위가 20이라 다행이다. 모든 경우에 대해서 n번째 위치에서 올바른 값으로 등록이 되는지를 더해주면된다. 알고리즘 1. 첫항 - 0번을 1로 초기화한다. 2. 두번째 항 - 1번을 기준으로 + - 를 진행하여 각 경우에 대해서 이전 항 - 이전 시도 를 더해준다. 3. 모든 항에 대해서 반복 후 마지막 항 - n번 ..
Baekjoon 5573 산책 2019. 8. 19. Link https://www.acmicpc.net/problem/5573 소스결과 9816 KB / 68 ms 언어 C++ 17 출처 Baekjoon 분류 다이나믹 프로그래밍, 조합론 설명 시뮬레이션으로 돌려도 될꺼 같지만 실제로 돌리면 안되는 문제 0,0에서 출발하여 오른쪽/아래 로 움직일 때 k 번 산책때 어디서 끝나는지 출력하여라. 처음에는 1천만번이면 될 줄 알고 돌렸지만 그럴리가 없었다. keyPoint는 처음 상태를 기준으로 홀수 / 짝수번 접근 후를 예측하는 것이다. 특정 위치에 k 번 접근 후에 아래/오른쪽으로 움직이는 경우의 수가 특정해진다. 알고리즘 1. 초기 상태를 입력 받는다. 2. 0,0 위치는 n번 접근한다. dp[0][0]을 n으로 초기화 해주낟. 3. i, j위치를 기준으로..
Baekjoon 17249 태보태보 총난타 2019. 6. 3. Link https://www.acmicpc.net/problem/17249 소스 결과 1988 KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 문자열 처리 설명 @==(^0^)@ 안녕하세요~~~~~!!!!!!! 태보는 지금 전세계적으로 선풍적인 인기를 끌고 있는데요 태보란, 우리나라의 태권도와 복싱을 접목한 운동입니다~ 두달동안 태보를 했더니 조혜련이 이렇게 완벽한 몸매가 되었습니다. (와!!) 태보를 하루에 25분만 투자한다면 런닝머신 한 시간! 여러분도 하루에 25분만! 태보의 세계로 들어가봅시다! (와!!) JAB JAB JAB PUNCH HOOK! JAB JAB JAB PUNCH HOOK! JAB JAB JAB PUNCH HOOK! 따라만 하세요! 따라만 하세요! JAP JAP J..
Baekjoon 17173 배수들의 합 2019. 6. 3. Link https://www.acmicpc.net/problem/17173 소스결과 1988KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 수학, 에라토스테네스의 체 설명 자연수 K개 각각의 배수 중 N 이하의 합을 구하여라. 단 중복은 한번만 더한다. 에라토스테네스의 체와 유사한 방식으로 해결한다. 소스코드 #include using namespace std; const int MAX = 1000; bool checkBoard[MAX + 1]; int main() { int n, m; cin >> n >> m; int start = -1; while (m--) { int k; cin >> k; if (start == -1) start = k; for (int i = 1; i * k
Baekjoon 6064 카잉 달력 2019. 6. 3. Link https://www.acmicpc.net/problem/6064 소스 결과 1988 KB / 52 ms 언어 C++ 17 출처 Baekjoon, ACM-ICPC 2013 분류 수학 설명 카잉 달력의 M, N 이 주어질 때 x : y 년이 몇 번째 해인지 계산하자 일전에 비슷한 문제로 현재 문제의 입력과 출력이 반대였던 문제를 푼 적이 있는 것 같다. 이번 문제를 풀기 위해서는 먼저 최소 공배수가 필요하다. 최소 공배수를 구하기 위해서는 최대 공약수가 필요하다. 유클리드 호제법을 이용해 최대 공약수를 구한 뒤, 최소 공배수를 구하면 된다. 처음에 이 문제의 최대 연월이 4만인 줄 알고, 최소 공배수가 4만이 넘어가는 경우 4만까지만 루프를 돌려 일일이 구하는 문제인 줄 알았으나 아니었다. 최대 ..
Baekjoon 1005 ACM Craft 2019. 6. 3. Link https://www.acmicpc.net/problem/1005 소스 결과 3440 KB / 304 ms 언어 C++ 17 출처 Baekjoon 분류 위상정렬, BFS 설명 최백준이 승리를 하여 여자친구 데이트를 할 수 있도록 도와주자 위상정렬에 관한 문제다. 위상 정렬을 하는 방법으로는 여러 방법이 있지만 Queue를 활용한 BFS와 유사한 방식으로 위상정렬을 진행한다. 알고리즘 1. 입력 받은 각 지점의 값을 기준으로 희소 인접 행렬을 구성한다. 2. 자신으로 들어오는 지점이 없는 점을 시작지점으로 판단하여 Queue에 push 한다. 3. Queue에 원소가 없을 때 까지 반복한다. 3-1. 현재 지점으로 들어가는 노드가 있는지 판별한다. 3-2. 현재 탐색하는 원소와 연결된 지점을 방문..
Baekjoon 1620 나는야 포켓몬 마스터 이다솜 2019. 6. 2. Link https://www.acmicpc.net/problem/1620 소스결과 5064 KB / 84 ms 언어 C++ 17 출처 Baekjoon 분류 문자열 처리, 이진 탐색 설명 포켓몬 마스터 다솜이가 오박사가 주려는 도감을 탈 수 있도록 도와주자. 처음 문제를 봤을 때는 트라이를 이용해 문제를 해결 할 방법을 떠올렸다. 구성해서 돌려본 결과는 메모리초과, 각각의 경우마다 자식노드가 26가지 가능하고, 최대 깊이가 20이기에 어느정도 예상은 했지만, 결과는 예상대로였다. 문제에 있어 딱히 어려운 알고리즘은 없다. 입력된 포켓몬을 정렬한 후, 포켓몬 이름이 들어왔을 때, 번호를 출력해주면 된다. 다만, 포켓몬을 정렬하는 과정에서 입력된 번호가 바뀌기 때문에, 기존 번호를 저장하고 있는 구조체를 만..

티스토리툴바