Algorithm
-
🌵 문제🌵 입출력 예시예제 입력 1 3CCPCCPPPC예제 출력 1 3예제 입력 2 4PPPPCYZYCCPYPPCC예제 출력 2 4예제 입력 3 5YCPZYCYZZPCCPPPYCYZCCPPZZ예제 출력 3 4 🌵 문제 풀이 모든 경우의 수를 탐색하여 최적의 결과를 찾는 완전 탐색 기법을 사용했다.접근 방법교환 가능한 모든 경우를 탐색한다.가로로 인접한 두 사탕을 교환세로로 인접한 두 사탕을 교환교환 후, 가장 긴 연속된 사탕의 갯수를 계산한다.가로 탐색 -> 한 행씩 검사해서, 연속된 같은 색상의 사탕 갯수 세기세로 탐색 -> 한 열씩 검사해서, 연속된 같은 색상의 사탕 갯수 세기모든 경우의 결과 중 최댓값을 출력구현 단계search 함수 : 2차원 배열을 입력받아 가로와 세로에서 각각 최대 연속..
[백준 3085] 사탕 게임 - Python🌵 문제🌵 입출력 예시예제 입력 1 3CCPCCPPPC예제 출력 1 3예제 입력 2 4PPPPCYZYCCPYPPCC예제 출력 2 4예제 입력 3 5YCPZYCYZZPCCPPPYCYZCCPPZZ예제 출력 3 4 🌵 문제 풀이 모든 경우의 수를 탐색하여 최적의 결과를 찾는 완전 탐색 기법을 사용했다.접근 방법교환 가능한 모든 경우를 탐색한다.가로로 인접한 두 사탕을 교환세로로 인접한 두 사탕을 교환교환 후, 가장 긴 연속된 사탕의 갯수를 계산한다.가로 탐색 -> 한 행씩 검사해서, 연속된 같은 색상의 사탕 갯수 세기세로 탐색 -> 한 열씩 검사해서, 연속된 같은 색상의 사탕 갯수 세기모든 경우의 결과 중 최댓값을 출력구현 단계search 함수 : 2차원 배열을 입력받아 가로와 세로에서 각각 최대 연속..
2024.11.08 -
백준 '로봇청소기'에서 호되게 당했기 때문에, 유사문제로 풀어봤다.lv0이라 쉬울 줄 알았는데 접근하기 꽤나 어려웠다..이런 유형 왜이렇게 어렵지..💫문제 💫동작 원리상,하,좌,우로 이동하는 케이스에 따라서, 인덱스 i,j가 각각 고정/증가/감소 세 가지 경우의 형태로 움직이기 때문에, 케이스 분류가 꼭 필요했다.그 과정에서 핵심은,경계값을 동적으로 조정하여 위쪽, 아래쪽, 왼쪽, 오른쪽의 경계를 좁혀 나가면서 숫자를 배열에 나선형으로 채우는 것이었다. 경계 설정 (top, bottom, left, right):top: 현재 배열의 위쪽 경계.bottom: 현재 배열의 아래쪽 경계.left: 현재 배열의 왼쪽 경계.right: 현재 배열의 오른쪽 경계. 방향 설정 및 경계 조정 오른쪽 이동 (righ..
[프로그래머스 LV0] 정수를 나선형으로 배치하기백준 '로봇청소기'에서 호되게 당했기 때문에, 유사문제로 풀어봤다.lv0이라 쉬울 줄 알았는데 접근하기 꽤나 어려웠다..이런 유형 왜이렇게 어렵지..💫문제 💫동작 원리상,하,좌,우로 이동하는 케이스에 따라서, 인덱스 i,j가 각각 고정/증가/감소 세 가지 경우의 형태로 움직이기 때문에, 케이스 분류가 꼭 필요했다.그 과정에서 핵심은,경계값을 동적으로 조정하여 위쪽, 아래쪽, 왼쪽, 오른쪽의 경계를 좁혀 나가면서 숫자를 배열에 나선형으로 채우는 것이었다. 경계 설정 (top, bottom, left, right):top: 현재 배열의 위쪽 경계.bottom: 현재 배열의 아래쪽 경계.left: 현재 배열의 왼쪽 경계.right: 현재 배열의 오른쪽 경계. 방향 설정 및 경계 조정 오른쪽 이동 (righ..
2024.10.19 -
🌰문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같..
[백준 1149] RGB거리 (DP)🌰문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같..
2024.09.14 -
🍉문제 🍉문제 해석숙제 마감일과 제출일이 주어졌을 때, 제출일이 마감일에 비해 얼마나 이전인지 또는 이후인지를 판단하고, 결과를 적절히 출력하는 문제이다. ** 제출일에는 연도가 명시되지 않기 때문에, 가장 가까운 연도를 추정하여 비교를 수행하도록 하였다!이 부분이 가장 까다로웠던 부분인 듯 하다. 🍉문제 접근법1. 윤년과 월별 일수 처리 윤년을 고려하여 월별 일수를 정확히 계산해야 했다.2월의 경우, 윤년에 따라 28일 또는 29일을 반환하는 것을 잊지 말자!days_in_month 함수로 구현하였다.thirty_days_month = [4, 6, 9, 11]thirty_one_days_month = [1, 3, 5, 7, 8, 10, 12]def days_in_month(month, year..
[백준 2730] 오늘은 OS 숙제 제출일🍉문제 🍉문제 해석숙제 마감일과 제출일이 주어졌을 때, 제출일이 마감일에 비해 얼마나 이전인지 또는 이후인지를 판단하고, 결과를 적절히 출력하는 문제이다. ** 제출일에는 연도가 명시되지 않기 때문에, 가장 가까운 연도를 추정하여 비교를 수행하도록 하였다!이 부분이 가장 까다로웠던 부분인 듯 하다. 🍉문제 접근법1. 윤년과 월별 일수 처리 윤년을 고려하여 월별 일수를 정확히 계산해야 했다.2월의 경우, 윤년에 따라 28일 또는 29일을 반환하는 것을 잊지 말자!days_in_month 함수로 구현하였다.thirty_days_month = [4, 6, 9, 11]thirty_one_days_month = [1, 3, 5, 7, 8, 10, 12]def days_in_month(month, year..
2024.08.26 -
🌵 문제 🌵문제풀이문제의 목표는 입력(단어 혹은 구(둘 이상의 단어))이 주어졌을 때, 단축키를 지정하는 것이다.단축키를 지정하는 기준은 아래와 같다.1. 단축키는 첫 글자를 우선적으로 검사하여 아직 사용되지 않은 알파벳을 찾아서 지정한다.2. 만약 첫 글자가 모두 사용되었다면, 각 단어의 글자들을 검사하여 단축키를 지정한다. 단축키를 지정하기 위한 로직은 다음과 같이 세웠다.단축키 목록 초기화: 이미 사용된 단축키를 기록할 리스트를 만들기각 입력 처리첫 글자가 이미 사용된 단축키 목록에 없는 경우 => 해당 글자를 단축키로 지정모든 단어의 첫 글자가 이미 사용된 경우=> 각 글자를 검사하여 사용되지 않은 단축키를 찾아서 적용어떤 것도 지정할 수 없는 경우, 해당 옵션을 원래대로 출력 🌵코드N ..
[백준 1283] 단축키 지정(구현,문자열) - Python🌵 문제 🌵문제풀이문제의 목표는 입력(단어 혹은 구(둘 이상의 단어))이 주어졌을 때, 단축키를 지정하는 것이다.단축키를 지정하는 기준은 아래와 같다.1. 단축키는 첫 글자를 우선적으로 검사하여 아직 사용되지 않은 알파벳을 찾아서 지정한다.2. 만약 첫 글자가 모두 사용되었다면, 각 단어의 글자들을 검사하여 단축키를 지정한다. 단축키를 지정하기 위한 로직은 다음과 같이 세웠다.단축키 목록 초기화: 이미 사용된 단축키를 기록할 리스트를 만들기각 입력 처리첫 글자가 이미 사용된 단축키 목록에 없는 경우 => 해당 글자를 단축키로 지정모든 단어의 첫 글자가 이미 사용된 경우=> 각 글자를 검사하여 사용되지 않은 단축키를 찾아서 적용어떤 것도 지정할 수 없는 경우, 해당 옵션을 원래대로 출력 🌵코드N ..
2024.08.25 -
✏️문제 ✏️풀이전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다. 즉, 메모제이션 방법으로 중복해 계산되는 값을 저장해 계산의 효율을 높일 수 있다. DP로 푸는건 알겠는데, 주어진 N -> 1 로 접근했더니 머리가 아팠다...결국 풀지 못하고 풀이를 참고했고, 상향식(bottom-up) 으로 푸는 것을 알게되었다. X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되게 되는데9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며3의 경우에는 3 -> 1의 과정을 거친다.=> 즉, 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다.앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다! 일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조..
[백쥰 1463] 1로 만들기 (DP) - Python✏️문제 ✏️풀이전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다. 즉, 메모제이션 방법으로 중복해 계산되는 값을 저장해 계산의 효율을 높일 수 있다. DP로 푸는건 알겠는데, 주어진 N -> 1 로 접근했더니 머리가 아팠다...결국 풀지 못하고 풀이를 참고했고, 상향식(bottom-up) 으로 푸는 것을 알게되었다. X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되게 되는데9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며3의 경우에는 3 -> 1의 과정을 거친다.=> 즉, 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다.앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다! 일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조..
2024.08.14 -
🥭 그리디 알고리즘그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 즉, 현재의 최적 선택을 번복하지 않는다. (선택한 것을 버리고 다른 것을 취하지 않는다)=> 이는 다이나믹 프로그래밍과 가장 큰 차이점으로, 모든 단계를 끝내고 이전으로 돌아가 다시 생각하는 과정이 없다는 의미일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 함! 🥭 그리디 알고리즘 코딩테스트 유형1. 그리디 알고리즘 문제는 문제 유형을 미리 외우지 않아도 해결할 가능성이 높다고 한다.이는 그..
[Greedy] 그리디 알고리즘🥭 그리디 알고리즘그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 즉, 현재의 최적 선택을 번복하지 않는다. (선택한 것을 버리고 다른 것을 취하지 않는다)=> 이는 다이나믹 프로그래밍과 가장 큰 차이점으로, 모든 단계를 끝내고 이전으로 돌아가 다시 생각하는 과정이 없다는 의미일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 함! 🥭 그리디 알고리즘 코딩테스트 유형1. 그리디 알고리즘 문제는 문제 유형을 미리 외우지 않아도 해결할 가능성이 높다고 한다.이는 그..
2024.07.29 -
🍇 문제 🍇 문제 풀이알고리즘 설계 수업 들을 때 풀었던 문제와 거의 똑같아서, 바로 풀 수 있었다! (비슷한 문제 풀어보고 싶다면 아래 포스팅 참고해주세요!)https://breath-in317.tistory.com/entry/DP-%EC%88%AB%EC%9E%90%ED%8C%90-%EB%86%80%EC%9D%B4 [Dynamic Programming] 숫자판 놀이문제숫자들이 2차원 배열에 있다. 가장 윗 행에서 가장 아래 행까지 내려올때 걸 쳐지는 길에 있는 숫자의 합이 가장 높은것을 찾아보자. 이 때 어느 한 cell에 서 다음 cell로 내려올 경우에는 바breath-in317.tistory.com 풀이방법1. 2차원 배열을 ground로 저장한다.2. 각각의 셀(index (i,j))에 ..
[백준 11048] 이동하기(DP) - Python🍇 문제 🍇 문제 풀이알고리즘 설계 수업 들을 때 풀었던 문제와 거의 똑같아서, 바로 풀 수 있었다! (비슷한 문제 풀어보고 싶다면 아래 포스팅 참고해주세요!)https://breath-in317.tistory.com/entry/DP-%EC%88%AB%EC%9E%90%ED%8C%90-%EB%86%80%EC%9D%B4 [Dynamic Programming] 숫자판 놀이문제숫자들이 2차원 배열에 있다. 가장 윗 행에서 가장 아래 행까지 내려올때 걸 쳐지는 길에 있는 숫자의 합이 가장 높은것을 찾아보자. 이 때 어느 한 cell에 서 다음 cell로 내려올 경우에는 바breath-in317.tistory.com 풀이방법1. 2차원 배열을 ground로 저장한다.2. 각각의 셀(index (i,j))에 ..
2024.07.28