알고리즘 문제 풀이: 파이썬/BOJ211

• 

  [BOJ_1912] 연속합 📌 문제 링크: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✅ 내 풀이(Success) : ✅ 참고용 풀이(Sucess) : 🧐 Review: 평소처럼 문제의 유형을 확인하고 해당 유형에 맞게 풀이를 고민해봤지만 어떻게 이 문제를 dp로 풀어야 할지 감이 오지 않았다. dp 문제를 이제 막 10문제를 풀어본 상태라서 기존에 내가 풀었던 방법인 입력값으로 주어진 수열에서 규칙성을 찾아 점화식을 도출하는 방법은 이 문제에 적용할 수 없기 때문에 점화식을.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 11.

• 

  [BOJ_11724] 연결 요소의 개수 📌 문제 링크: https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 연결된 요소의 개수를 세기 위해서 DFS(깊이 우선 탐색)을 이용했다. 하나의 정점에서 DFS를 진행하면 연결된 정점들을 모두 방문할 것이고, 방문한 정점들은 배열을 이용해 방문 정보를 기록해둔다. for 반복문을 이용하여 방문하지 않은 정점들은 DFS를 이용해 탐색을 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 24.

• 

  [BOJ_1012] 유기농 배추 📌 문제 링크: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - BFS를 이용한 완전 탐색으로 배추 밭에 필요한 배추 흰 지렁이의 개수를 체크한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 23.

• 

  [BOJ_2535] 아시아 정보올림피아드 📌 문제 링크: https://www.acmicpc.net/problem/2535 2535번: 아시아 정보올림피아드 첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 1. 입력 받은 데이터를 성적순으로 내림차순 정렬한다. 2. 가장 성적이 좋은 두 명을 answer 배열에 담는다. 3. for 반복문을 이용해서 answer 배열에 담긴 두 원소들과 같은 국가가 아니면서 그 중에서 점수가 가장 큰 원소를 answer 배열에 담고, break로 반복문을 종료한다. 4. 두 번째 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 12.

• 

  [BOJ_10867] 중복 빼고 정렬하기 📌 문제 링크: https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 입력 받은 수들을 집합을 이용해서 중복을 제거한다. - 중복을 제거한 수들을 오름차순으로 정렬하고, 한 줄로 출력한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 11.

• 

  [BOJ_1235] 학생 번호 📌 문제 링크: https://www.acmicpc.net/problem/1235 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 코테에 이런 쉬운 문자열 문제만 나오면 좋을 텐데... 🚩 Idea: - 모든 학생 번호에서 뒤에서부터 k개의 문자열을 가져와서 집합에 넣는다. - 집합의 원소가 학생의 수인 N과 같으면 while 반복문을 종료하고 k를 출력한다. - 위의 if 조건문에서 반복문이 종료되지 않았다면 k를 하나 증가시키고 같은 과정을 반복한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 10.

• 

  [BOJ_2839] 설탕 배달 📌 문제 링크: https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 그리디 알고리즘에 해당하는 유형의 문제지만, 설탕을 포장할 수 있는 경우를 모두 구하는 방법으로 풀이했다. 🚩 Idea: 1. 3kg의 봉지만 사용해서 포장할 수 있는 경우 2. 5kg의 봉지만 사용해서 포장할 수 있는 경우 3. 5kg의 봉지를 몇 개 사용하고, 나머지를 3kg의 봉지로 포장할 수 있는 경우 4. 3kg의 봉지를 몇 개 사용.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 10.

• 

  [BOJ_1051] 숫자 정사각형 📌 문제 링크: https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 두 번째 for문에서 len(rectangle[i])을 m으로 변경하는 것이 좀 더 깔끔한 코드가 될 것 같다. 🚩 Idea: - n과 m의 길이가 50이하의 수로 완전 탐색을 이용해 모든 경우의 수를 확인해도 시간 초과가 발생하지 않을 것 같다. - 정사각형의 최소 크기(넓이)는 1이므로 area에 해당 값을 넣고 시작한다. - .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 9.

• 

  [BOJ_4796] 캠핑 📌 문제 링크: https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - L, P, V의 값의 나눗셈을 통해 휴가 기간인 V에서 며칠 동안 캠핑장을 이용할 수 있는지 확인한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 8.

• 

  [BOJ_9655] 돌 게임 📌 문제 링크: https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 문제 분류에 DP가 있어서 풀어본 문제인데, 위 코드를 보면 이게 과연 실버 난이도의 문제인지 의심이 들 정도이다.(아마도 추후에 브론즈로 내려갈 가능성이 있지 않을까?) 하지만 돌의 개수인 n에 따라서 누가 이기는지 구하기 위해 모든 경우의 수를 나열하면서 규칙성을 찾는 과정이 결코 단순한 과정은 아니었다. SK와 CY가 자신이 승리하기 위해 본인의 경우의 수 뿐만 아니라 상대방의 경우의 수도 같이 고려해야 되는 과정이 필요했기 때문이다. 문제를 풀고.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 8.