본문 바로가기

Algorithm

 (57)
[백준] 1011번: Fly me to the Alpha Centauri 문제링크 : https://www.acmicpc.net/problem/1011 문제풀이 y지점에 도달하기 전 마지막 이동은 항상 1이어야 한다. 따라서 이동거리는 1 2 2 1, 1 2 3 2 1, 이런 식으로 점차 늘어났다가 줄어드는 형식이다. 찾은 규칙 1 경우의 수를 모두 나열해 보면 총 이동거리의 제곱근이 정수인 경우, 앞 뒤로 일정한 규칙이 보인다. 4의 제곱근은 2로, 정수이다. 따라서 이동거리는 위와 같이 대칭이 되는 구조이며 4를 포함하여 앞으로 두 경우는 장치 작동 횟수가 2 + 1 (제곱근 + (제곱근 - 1)) 4를 포함하지 않고, 뒤로 두 경우는 장치 작동 횟수가 2 + 2 (제곱근 * 2) 이다. 처음에는 이렇게 복잡하게 생각하여 문제를 풀었는데, 문제를 다시 보니 단순히 더해서 ..
[백준] 1193번: 분수찾기 문제링크 : https://www.acmicpc.net/problem/1193 문제풀이 찾을 수 있는 규칙 1. 위의 표는 분자와 분모 합이 같은 것끼리 한 줄에 나열한 것이다. 2. 최대 분모는 순차적으로 늘어난다.3. 최대 분모가 짝수일 때와 홀수일 때 분자 분모가 증가하는 모양이 서로 반대이다.4. 분자와 분모가 1씩 증가, 감소한다. 그러면 우선, 입력받은 숫자의 최대 분모가 몇인지부터 알아야 한다. 각 줄의 제일 큰 수 (1, 3, 5, 10, 15 ...)로 비교를 하면 되겠다.while (sum < N) { sum += ++max_denominator; }순차적으로 더하면서 입력받은 숫자의 최대 분모(max_denominator)가 몇인지, 그 줄의 제일 큰 수(sum)는 몇인지 알아낸다. ..
[백준] 2292번: 벌집 문제링크 : https://www.acmicpc.net/problem/2292 문제풀이벌집 모양을 보면,1은 1번,2부터 7은 2번,8부터 19까지는 3번을 지난다. 1번1 2번 1 + 1 ... 1 + 6 3번 1 + 1 + 6 ... 1 + 6 + 6 + 6 4번1 + 1 + 6 + 6 + 6 ... 1 + 6 + 6 + 6 + 6 + 6 + 6 위와 같이, 6이 점차 늘어나는 등비수열의 규칙을 이루는 것을 볼 수 있다.(이전의 합 + 6 * ++count) 소스코드 /* * 백준 2292번: 벌집 */ #include using namespace std; int main() { int N; cin >> N; int sum = 1; int count = 0; while (true) { if (N
[백준] 2438번: 별 찍기 - 1 문제링크 : https://www.acmicpc.net/problem/2438 문제풀이 i = 0 --- 별 한 개 출력(j = 0), 엔터 i = 1 --- 별 두 개 출력(j = 0, 1), 엔터 i = 2 --- 별 세 개 출력(j = 0, 1, 2), 엔터 ... for문을 두 번 사용하여, 줄에 해당하는 별 개수만큼 출력한 후 엔터를 출력한다. 소스코드/* * 백준 2438번: 별 찍기 - 1 */ #include using namespace std; int main() { int N; cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j
[백준] 1152번: 단어의 개수 문제링크 : https://www.acmicpc.net/problem/1152 문제풀이입력한 문장의 모든 띄어쓰기 개수를 센 다음, 문장의 맨앞, 맨 뒤에 공백이 오는 경우를 고려해 카운트 다운한다. 소스코드 /* * 백준 1152번: 단어의 개수 */ #include #include int main() { std::string str; getline(std::cin, str); int words = 0; for (int i = 0; i < str.length(); i++) { if (str[i] == ' ') words++; } if (str[0] == ' ') words--; if (str[str.length() - 1] == ' ') words--; std::cout
[백준] 2839번: 설탕 배달 문제링크 : https://www.acmicpc.net/problem/2839 문제풀이경우의 수를 크게 아래와 같이 두 가지로 나눌 수 있다. 1. 5킬로그램 봉지로 다 채워지는 경우 (5로 나눈 나머지가 0인 경우)2. 5킬로그램 봉지에 모두 담아지지 않는 경우 (5로 나눈 나머지가 0이 아닌 경우) 5로 나눠지는 15와 같은 경우는, 그 몫을 출력하면 된다. 하지만 2번의 경우 몇가지 예를 들면, 18킬로그램① 5킬로그램 봉지 3개 --- 3킬로그램 남음② 3킬로그램 봉지 1개 9킬로그램방법1① 5킬로그램 봉지 1개 --- 4킬로그램 남음② 3킬로그램 봉지 1개 --- 1킬로그램 남음 방법2① 3킬로그램 봉지 3개 위 작업 순서를 간단히 적어보면 아래와 같다.① 5킬로그램 봉지에 넣어본 후, 남은 설..
[백준] 1000번: A+B 문제링크 : https://www.acmicpc.net/problem/1000 문제풀이단순 입출력 문제 소스코드 #include using namespace std; int main() { int a, b; cin >> a >> b; cout
[Algorithm] Breadth-first search (너비 우선 탐색) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. 출처 : 위키백과https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89 예) ① 1을 방문하며 큐에 넣는다. ② 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드들을 차례로 방문하며 큐에 넣는다.(1을 빼며, 1과 인접한 2, 3을 차례로 큐에 넣는다.) ③ 큐에..

티스토리툴바