본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 16561번 : 3의 배수 문제링크 : https://www.acmicpc.net/problem/16561 16561번: 3의 배수 윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다. 즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단 분해 www.acmicpc.net 완전탐색 문제였습니다. 시간제한이 0.1초기 때문에 100만번 연산을 초과하면 시간초과가 납니다. 3개의 수를 결정하는..
(C++) - 백준(BOJ) 1039번 : 교환 문제링크 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 메모이제이션을 사용한 DFS 백트래킹 브루트포스 문제였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include #include #include #include using namespace std; int m,k; string n; int ck[1000001]; int cnt ..
(C++) - 백준(BOJ) 1182번 : 부분수열의 합 문제링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 조합으로 뽑았을 때 부분수열들이 중복될 경우도 고려했었는데 그런걸 고려하는 문제가 아닙니다 문제입력 : 4 16 1 7 9 9 output : 2 3번째 9와 2번째 7 뽑는것과 4번째 9와 2번째 7을 뽑는것은 다르다고 보는 것 같습니다. 요거 몰라서 고생했습니다..낄낄 마찬가지의 테스트 케이스입니다. 문제입력 : 2 0 0 0 output : 3..
(C++) - DFS 유형 DFS는 주로 재귀함수를 사용하며 백트래킹, 브루트 포스에 자주 이용하는 탐색 방법입니다. 고려할 점은 다음과 같은 3가지입니다. 1. 조합으로 뽑을 때 2. 같은 부분 집합을 출력하면 안될 때 3. 순열로 뽑을 때 순서 상관없이 막 뽑을 때
(C++) - 백준(BOJ) 2998번 : 8진수 https://www.acmicpc.net/problem/2998 2998번: 8진수 문제 창영이는 여러 가지 진법을 공부하고 있다. 창영이는 어제 2진법을 배웠고, 오늘은 8진법을 배웠다. 이제, 2진법 수를 8진법 수로 변환하려고 한다. 창영이가 사용한 방법은 다음과 같다. 2진수의 길이가 3으로 나누어 떨어질 때 까지 수의 앞에 0을 붙인다. 그 다음, 3자리씩 그룹을 나눈다. 아래의 표를 참고해 8진수로 바꾼다. 2진수가 주어졌을 때, 창영이가 사용한 방법을 이용해 8진수로 바꾸는 프로그램을 작성하시오. 000 0 001 1 010 www.acmicpc.net 간단한 진법 변환 문제였습니다. 12345678910111213141516171819202122232425262728293031323334..
(C++) - 백준(BOJ) 1018번 : 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 구현 문제였습니다. 8X8의 체스판으로 자르고 위 두 가지 경우 중 칠할 칸의 최소 개수를 반환하는 함수를 만들어 해결했습니다. 자른 이후에는 다음 2가지 경우를 비교해야 합니다. 1.WBWB...로 칠할 경우 2.BWBW...로 칠하는 경우 이들중 최소의 개수를 출력하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
(C++) - 백준(BOJ) 16727번 : ICPC https://www.acmicpc.net/problem/16727 16727번: ICPC The first line of the input contains two space-separated integers p1 and s1, where p1 and s1 are the number of goals scored by Persepolis and Esteghlal, respectively, in the first match in which Persepolis is the home team. The second line contains two spa www.acmicpc.net 단순 구현 문제였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #in..
(C++) - 백준(BOJ) 2578번 : 빙고 https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다. www.acmicpc.net 구현문제였습니다. 풀이방법 대각선으로 빙고가 되는 경우를 잘 구현해야하는 문제였습니다. (3,3)일 때는 오른쪽 아래로 향하는 대각선과 오른쪽 위로 향하는 대각선을 둘 다 봐줘야 합니다. 가로 세로 대각선을 체크하는 함수를 각각 구현하여 이들의 합이 3이상이 되었을 때 ..

티스토리툴바