개발하는 개구리

🐸 문제 정보 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 14.41m 📝 풀이 처음에 순열로 풀어야하는 문제라고 생각해서... 도대체 어떻게 풀어야하지?! 고민했는데 다시 천천히 생각해보니 그냥 Counter 써서 뒤에 뭐올지 백트래킹해도 될 것 같다고 느꼈다. 이유는 문자열 길이가 10까지밖에 안돼서... 이미 예제에 나와있는 경우가 최악의 경우였다. 🧑‍💻 나의 답 # pypy3 import sys from collections import Counter input =..

🐸 문제 정보 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 24.36m 📝 풀이 간단한 백트래킹 문제인데도, 재귀 내부 로직이 잘 안떠올라서 정답을 참고했다ㅠㅠ 임의의 수열을 만드는 재귀 함수인데, 다 풀고나니 그냥 permutation 써도 됐겠다는 생각이 들었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) nums = list(map(int, input().rstrip().spli..

🐸 문제 정보 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 12.43m 📝 풀이 시간복잡도 무조건 터질거라고 생각했는데 바로 성공해서 읭 한 문제였다. 문제 수가 15개 밖에 안되니까, 문제 내용대로 직관적인 백트래킹 함수를 작성했다. (현재 인덱스, 현재까지의 합, 최소, 최대)를 인자로 전달하는 백트래킹 함수 합이 L과 R 사이이고, 최대 - 최소가 X보다 크거나 같다면 res 갱신 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, l, r, x = list(map(int, input().rstrip().split())) a ..

🐸 문제 정보 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 32.00m 📝 풀이 처음에 2차원 리스트 보이자마자 BFS로 풀었다가 메모리 터지고... 백트래킹으로 풀어야한다는 것을 알게됐다. 이런 2차원 리스트 주어졌을 때 그냥 생각 안하고 BFS로 푸는 습관좀 고쳐야겠다. 백트래킹으로 푸는 경우 풀이는 아래와 같다. 집의 인덱스와, 민트초코 우유가 있는 인덱스 모두를 찾기 집의 인덱스부터 시작해서, 민트초코 우유의 인덱스로 하나씩 이동해보기 이때, ..

🐸 문제 정보 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 28.16m 📝 풀이 백트래킹으로 풀면 되는 문제였다. 새로운 배열을 복사해서 전달해주는 방식보다는, 기존 배열 하나에서 재귀 시킨 후 다시 원상 복구 해주는 방식으로 진행했다. 아래 조건만 잊지 않으면 어렵지 않게 풀 수 있는 문제였다. 계란을 첫 인덱스부터 탐색하지만, 이미 깨져있는 경우나 본인인 경우는 패스해주는 것 깰 계란이 없으면 그냥 넘겨줄 것 본인이 이미 깨져있으면 그냥 넘겨줄 것 🧑‍..

🐸 문제 정보 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 20.06m 📝 풀이 이 문제의 핵심은 S -> T가 아닌, T -> S로 가야한다는 점이었다. 처음에 S -> T로 가는 백트래킹 코드로 시간초과가 났지만, 같은 로직의 T -> S로 가는 함수를 작성하여 통과할 수 있었다. S -> T의 경우, 두 문자열을 비교한다고는 하지만 T로 가며 무한으로 발산되는 형태임에 반해 T -> S의 경우, 문자을 하나씩 지우기 때문에 ..

🐸 문제 정보 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 예전에 한 번 풀었던 문제인데도 기억을 못해서 오래걸렸다.. 알파벳 26개에 대해, 가르쳤는지 여부를 알 수 있는 26개의 요소 리스트를 선언한다. 각 알파벳에 대해서 True(가르침)을 넣어보고 학생이 총 알 수 있는 단어의 개수를 파악한 뒤, 해당 알파벳을 False(가르치지 않음)으로 바꿔보면서 백트래킹을 실시한다. 🧑‍💻 나의 답 # pypy3 import sys input = ..

🐸 문제 정보 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 백트래킹을 오랜만에 풀어서 그런가 생각보다 어렵게 느껴지는 문제였다. 임시 배열을 두고, 가장 마지막 숫자와 비교하여 넣을 수 있는 수 들을 하나씩 채워나가면 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) temps = [] def bt(): if temps: res..

🐸 문제 정보 3165번: 5 N과 K가 주어졌을 때, N보다 크면서 5가 적어도 K번 포함되는 가장 작은 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🤖 알고리즘 그리디 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 사실 완벽하게 풀이하지 못한 문제이다. 질문이 엄청 깔끔하고, 이해하기 쉬운 반면... 정말 엄청나게 틀렸다. 사실 아직까지 틀린 이유를 모르겠다. 기존에 풀이 방식은 아래와 같았다. (num은 n + 1을 리스트로 바꾼 변수, idx는 -1) 백트래킹 함수 내에서 5가 k개 이상이면 멈추도록 함 num[idx]가 5라면 백트래킹 함수를 재귀하는데, idx 값을 -1 해줌 자리수를 넘겨주기 위해서 num[idx]가 5보다 작은 경우, 5로 만들고 idx 값을 -1 하여 재귀..