백준 1182 부분수열의 합 - Python

문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 문제풀이부분수열의 합을 구하는 문제이다.입력의 개수를 보아, 어떤 알고리즘을 사용해도 쉽게 해결할 수 있을 것으로 보인다. 본 문제를 백트래킹 방식으로 접근했다.특정 조건을 만족하거나, 그렇지 못하는 경우 더이상 뻗어나가지 않고 재귀나 탐색을 종료하는 방법이다. 일단..

• format_list_bulleted CodingTest/BOJ
• · 2024. 11. 28.
• textsms

부분수열의 합을 구하는 알고리즘 정리 - 완전탐색, 백트래킹, DP, 비트마스크 비교 (Python)

부분수열의 합을 구하는 알고리즘: 다양한 접근 방법부분수열의 합을 구하는 문제는 기본적인 문제 중 하나이다.주어진 배열에서 가능한 모든 부분수열의 합을 구하거나, 특정 목표 합을 만족하는 부분수열을 찾는 것이 주 목적이다.이를 해결하기 위해 다양한 알고리즘들이 존재하며, 각각의 장단점이 있다. 이번 글에서는 부분수열의 합을 구하는 네 가지 대표적인 알고리즘- 완전 탐색, 백트래킹, 동적 계획법, 비트마스킹 - 을 정리해 보겠다.문제 정의우리가 풀고자 하는 문제는 다음과 같다. 정수 배열 arr이 주어졌을 때, 가능한 모든 부분수열의 합을 계산하거나 특정 조건을 만족하는 부분수열의 합을 찾는 것이다. 예를 들어, 배열 [1, 2, 3]이 주어진다면 가능한 부분수열의 합은 {0, 1, 2, 3, 4, 5, ..

• format_list_bulleted CodingTest/algorithm
• · 2024. 11. 27.
• textsms

백준 24509 - 상품의 주인은? (Python)

문제혜민이네 반은 총 N$N$명의 학생으로 이루어져 있으며 학생마다 번호가 다르게 배정되어 있다.이번 시험은 국어, 영어, 수학, 과학 총 4과목으로 진행되며,학생들이 공부를 열심히 할 수 있게 과목별 1등에게 상품을 주기로 했다. 수상은 국어, 영어, 수학, 과학 순서로 하며 최대한 많은 학생에게 상품을 주고 싶기 때문에 학생마다 상품은 한 번만 받을 수 있다. 예를 들어 국어 과목에서 1등 한 사람이 수학 과목에서 또 1등을 한다면국어 과목에서 상품을 받았기 때문에 이 학생은 다른 과목에서 상품을 더 받을 수 없다. 따라서 수학 과목은 상품을 받지 않은 학생 중에 점수가 가장 높은 학생이 상품을 받는다.단, 동점이 있으면 번호가 빠른 사람이 상품을 받는다. 과목별 상 받을 사람의 번호를 출력하시오.입..

• format_list_bulleted CodingTest/BOJ
• · 2024. 11. 26.
• textsms

[백준] 1012번 유기농배추 - Python

문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다.농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에,한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다.이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다.특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어,그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다.배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로서로 인접해있는 배추들이 몇 군데에 퍼져있는지..

• format_list_bulleted CodingTest/BOJ
• · 2024. 11. 25.
• textsms

브루트포스 알고리즘 살펴보기 (Brute Force)

브루트포스 알고리즘이란 무엇인가?브루트포스(Brute Force) 알고리즘은 말 그대로 "무차별 대입 방식"으로 문제를 해결하는 접근 방법이다.이는 가능한 모든 경우의 수를 하나씩 탐색하여 정답을 찾는 방식으로, 가장 직관적이고 기초적인 해결 방법이다.모든 가능한 해를 전부 시도하기 때문에 구현은 간단하지만, 효율성이 떨어질 수 있다는 단점이 있다. 예를 들어, 비밀번호를 찾는 문제를 생각해보자.브루트포스 알고리즘은 가능한 모든 비밀번호 조합을 하나씩 시도해보는 방식으로 정답을 찾아낸다.이는 당연히 시간이 오래 걸릴 수 있지만, 올바른 비밀번호를 반드시 찾아낸다는 장점이 있다.따라서 문제의 크기가 작거나 가능한 해의 수가 많지 않을 때는 이 방법이 매우 효과적일 수 있다. 앞서 설명된 내용과 같이, 말이..

• format_list_bulleted CodingTest/algorithm
• · 2024. 11. 23.
• textsms

백준 1430번 - 영화감독 숌 (Python)

문제666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666,..

• format_list_bulleted CodingTest/BOJ
• · 2024. 11. 22.
• textsms