부분수열의 합을 구하는 알고리즘 정리 - 완전탐색, 백트래킹, 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

[Pandas] 판다스 데이터프레임 컬럼 전처리, 함수 컬럼 적용 - apply, map

Pandas에서 데이터를 처리할 때, apply와 map 함수를 주로 사용한다.두 함수 모두, 컬럼에 적용하며 연산을 통해 새로운 컬럼을 생성하거나, 기존 컬럼을 전처리 하는 방식으로 사용한다.오늘은 두 함수의 사용법을 간단히 알아보고자 한다.  1. map함수 먼저, map 함수에 대해 알아보자.map은 Pandas Series의 각 요소에 대해 지정된 함수를 적용하는 데 사용된다.이는 주로 단일 열에 대해 연산을 수행할 때 적합하다.예를 들어, 문자열 데이터를 다른 형태로 변환하거나 값을 다른 값으로 치환하는 데 유용하다. 다음 예시는 map 함수를 활용한 간단한 코드이다.import pandas as pddata = {'fruit': ['apple', 'banana', 'cherry']}df = p..

• format_list_bulleted Programming/Python
• · 2024. 11. 24.
• 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