- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 아래 코드가 틀렸다고 나오는데 ll r = 1e18 + 4; 이 부분 코드를 1e9로 바꿔서 제출하기만 하면 맞다고 나옵니다. 상한선을 저번에 풀었던 드래곤 앤 던전 문제처럼 크게 잡았는데 왜 문제가 생겼는지 모르겠습니다. 시간초과가 나온거면 이해가 가는데 왜 틀렸다고 나오는지 이해가 안가네요.. #include <bits/stdc++.h> using namespace std; typedef long long ll; ll x, y, z, mid, ret; bool check(ll mid) { ll new_z = (y + mid) * 100 / (x + mid); // 새로운 승률 return new_z > z; // 기존 승률과 비교 } int main() { cin >> x >> y; ll l = 1; ll r = 1e18 + 4; // 최대 범위를 현실적으로 설정 z = y * 100 / x; // 기존 승률 ret = 0; while (l <= r) { mid = (l + r) / 2; if (check(mid)) { // 승률이 증가하는 경우 ret = mid; r = mid - 1; // 더 작은 mid 값을 탐색 } else { // 승률이 증가하지 않는 경우 l = mid + 1; // 더 큰 mid 값을 탐색 } } if (ret == 0) cout << -1; else cout << ret << "\n"; return 0; }
안녕하세요. 큰돌강사님~ 순열이나 조합을 재귀함수로 구현할 때 변경을 적용한후 DFS진입합니다. DFS를 빠져나오고 나서는 변경사항을 다시 원복시키는 코드 패턴이 보여지는데 (즉, push_back() => dfs => pop_back() ) 이에 대한 알고리즘 용어가 따로 있는지 궁금합니다.
1. 현재 학습 진도 1-10 듣고 있습니다 2. 어려움을 겪는 부분 이 코드에서 for index in range(len(alphabet_occurrence_array)) 는 N이 아니라 상수이기때문에 O(1)라고 말씀해주셨는데 해당 부분이 잘 이해 가지 않습니다.. for문이라도 정해진 숫자의 범위가 돌면 O(n)의 시간 복잡도가 아닌건가요? 만약 이렇게 이해하게 되면 for char in string: 코드에서 string도 배열에 크기에 정해진 숫자만큼만 돌게 되는데.. 헷갈립니다..! 단순히 변수의 for문이면 n 상수의 for문이면 1 이렇게 생각하면 되는건지 궁금합니다!
2022 KAKAO TECH INTERNSHIP 문제 중 코딩테스트 공부 문제에서 실패하는 경우가 있어서 왜 그런지 질문드리려고 합니다. 예시풀이 중 dp풀이랑 비슷하게 풀었는데 다른 점은 저는 dp[alg][cop]을 해당 alg, cop에 도달하기 위해 필요한 최소 비용으로 정의하고 마지막에 최대 alg~+30, co~ +30 중 최소값을 리턴하도록 정의했습니다. 이렇게 하니까 정확성은 다 통과하는데 효율성에서 실패하는 경우가 생기던데 왜그럴까요? def solution(alp, cop, problems): answer = 0 problems += [[0,0,1,0,1], [0,0,0,1,1]] dp = [[1000] * 181 for _ in range(181)] dp[alp][cop] = 0 goal = [alp,cop] for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems: goal[0] = max(goal[0], alp_req) goal[1] = max(goal[1], cop_req) for i in range(alp, 181): for j in range(cop, 181): for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems: if i >= alp_req + alp_rwd and j >= cop_req + cop_rwd: dp[i][j] = min(dp[i][j], dp[i-alp_rwd][j-cop_rwd] + cost) answer = 1000 for row in dp[goal[0]:]: answer = min(answer, min(row[goal[1]:])) return answer
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 312 ->321 입니다. 강의 항상 감사합니다~
안녕하세요 큰돌님! 문풀 강의를 보기전에 구현을 먼저 해보고 강의를 시청했습니다. 나름대로 문제 풀이 방식(sudo code)를 만들어서 문제를 풀고 잘 풀었다고 생각했는데 큰돌님의 풀이를 보고 비교해보니 난잡한 풀이라고 생각하게 되었어요. 알고리즘을 풀 때 어떻게 생각해야 간결하게 정확한 전략을 세울 수 있을까요...? 문제를 풀 때 큰돌님의 생각루틴과 제 코드에 대한 피드백이 궁금합니다! http://boj.kr/833f44e07f3640228c53b006c8bf0ee5
1. 현재 학습 진도 1-5 알고리즘과 친해지기(2) 2. 어려움을 겪는 부분 # def find_max_occurred_alphabet(string): # alphabet = [0] * 26 # for i in string: # if i.isalpha(): # alphabet[ord(i) - ord('a')] += 1 # # max = alphabet[0] # index = 0 # for i in range(len(alphabet)): # if alphabet[i] > max: # max = alphabet[i] # index = i # # return chr(index+ord('a')) from collections import Counter def find_max_occurred_alphabet(string): string = [char for char in string if char.isalpha()] counter = Counter(string) print(counter) return max(counter, key=counter.get) result = find_max_occurred_alphabet print("정답 = i 현재 풀이 값 =", result("hello my name is dingcodingco")) print("정답 = e 현재 풀이 값 =", result("we love algorithm")) print("정답 = b 현재 풀이 값 =", result("best of best youtube")) 3. 시도해보신 내용 안녕하세요. 첨부한 코드 중 주석 처리한 부분은 문제를 보고 사전에 제가 작성한 코드입니다. 결과는 예상과 동일하게 출력됩니다. 그 밑에는 다른 풀이 방법을 찾다가 Counter 클래스를 사용하여 작성한 코드입니다. 본 강의에서는 카운터가 동일한 경우, 기존의 값을 변경하지 않는 방식이라 i가 출력되지만, 해당 방법을 사용하면 입력 순으로 o가 출력됩니다. 이 경우 최빈값을 찾아내는 코드는 맞지만, 값이 동일한 경우에 처리하는 로직이 다르기 때문에 발생한다고 이해하면 될까요? 답변해주신다면 감사하겠습니다.
http://boj.kr/ad36bd7f8ec04337b4e4eb98ed2ecdfc 이 코드는 틀린 코드이고 http://boj.kr/8494f1ca7ca84fbeaa1cd47409006e9f 이 코드는 맞은 코드인데요. 둘의 차이는 combi(0)으로 시작하냐 combi(-1)로 시작하냐입니다. 근데 combi(-1)은 for (int i = start + 1; ...) 로 하고 combi(0)은 for (int i = start; ...) 해서 결국 똑같은 코드 아닌가요? 왜 combi(0)으로 하면 답이 안나오는지 모르겠습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 선생님 이 문제를 재귀를 이용해서 풀어봤는데 인덱스를 포함하는 경우에서 temp_v 배열에 인덱스를 포함해서 보내는 경우는 어떻게 하는건가요?? (요 부분) // 현재 인덱스를 포함하지 않는 경우 go(idx + 1, p, f, s, v, sum, temp_v); // 현재 인덱스를 포함하는 경우 go(idx + 1, p + a[idx].p, f + a[idx].f, s + a[idx].s, v + a[idx].v, sum + a[idx].c, temp_v); #include <bits/stdc++.h> using namespace std; const int INF = 987654321; int n, mp, mf, ms, mv; int ret = INF; map<int, vector<vector<int>>> ret_v; // 비용별 조합 저장 struct A { int p, f, s, v, c; } a[16]; void go(int idx, int p, int f, int s, int v, int sum, vector<int> temp_v) { // 모든 재료를 확인한 경우 if (idx == n) { // 최소 조건 만족하는지 확인 if (p >= mp && f >= mf && s >= ms && v >= mv) { if (ret > sum) { ret = sum; // 최소 비용 갱신 ret_v[ret].clear(); // 이전 조합 제거 ret_v[ret].push_back(temp_v); // 새로운 조합 저장 } else if (ret == sum) { ret_v[ret].push_back(temp_v); // 같은 비용의 다른 조합 저장 } } return; } // 현재 인덱스를 포함하지 않는 경우 go(idx + 1, p, f, s, v, sum, temp_v); // 현재 인덱스를 포함하는 경우 go(idx + 1, p + a[idx].p, f + a[idx].f, s + a[idx].s, v + a[idx].v, sum + a[idx].c, temp_v); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 입력 받기 cin >> n >> mp >> mf >> ms >> mv; for (int i = 0; i < n; i++) { cin >> a[i].p >> a[i].f >> a[i].s >> a[i].v >> a[i].c; } // 탐색 시작 go(0, 0, 0, 0, 0, 0, {}); // 결과 처리 if (ret == INF) { cout << -1 << '\n'; // 조건 만족하지 못하는 경우 } else { sort(ret_v[ret].begin(), ret_v[ret].end()); // 사전순 정렬 cout << ret << '\n'; // 최소 비용 출력 for (int idx : ret_v[ret][0]) { // 첫 번째 조합 출력 cout << idx << " "; } cout << '\n'; } return 0; }
학습하는 분들께 도움이 되고, 더 좋은 답변을 드릴 수 있도록 질문전에 다음을 꼭 확인해주세요. 1. 강의 내용과 관련된 질문을 남겨주세요. 2. 인프런의 질문 게시판과 자주 하는 질문(링크)을 먼저 확인해주세요. (자주 하는 질문 링크: https://bit.ly/3fX6ygx) 3. 질문 잘하기 메뉴얼(링크)을 먼저 읽어주세요. (질문 잘하기 메뉴얼 링크: https://bit.ly/2UfeqCG) 질문 시에는 위 내용은 삭제하고 다음 내용을 남겨주세요. ========================================= [질문 템플릿] 1. 강의 내용과 관련된 질문인가요? (예/아니오) 2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예/아니오) 3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예/아니오) [질문 내용] 안녕하세요. stack 2번째, 문제 풀이 를 보면서 궁금증이 생겨서 질문을 남깁니다. 문제 풀이를 듣던 도중에 영한 님이 history를 만들 때, ArryDeque를 이용해서 만들었던 것을 볼 수 있었습니다. 그러다가 계속 듣다 보니까 갑자기 이런 생각이 들더라고요.(어떤 분이 '자바 성능 비교 표' 올린 영향도 있습니다.) '앞으로만 추가하니 LinkedList가 더 빠르지 않을까?' 라는 생각 이요. 그런데 ArrayDeque를 왜 사용했을까? 생각 해보니 '앞으로만 추가 하지만, 여러 가지 이용할게 더 많아서 ArrayDeque 를 사용 했다.' 인데 이것도 추측이라서 정확하지 않네요. 그래서 LinkedList 대신 ArryDeque를 사용한 이유를 자세히 알고 싶습니다. 답변 부탁 드립니다.
직접 구현하는 Set1 - MyHashSetV1 강의중 public class MyHashSetV1 { static final int DEFAULT_INITIAL_CAPACITY = 16; LinkedList<Integer>[] buckets; private int size = 0; private int capacity = DEFAULT_INITIAL_CAPACITY; public MyHashSetV1() { buckets = new LinkedList[capacity]; for (int i = 0; i < capacity; i++) { buckets[i] = new LinkedList<>(); } } 이렇게 생성자에 객체를 생성하는데 클래스 필드에 객체를 생성하지 않고 생성자 안에서 생성하는 이유가 무엇인지 궁금해서 문의드립니다.
http://boj.kr/5a9e690ac2f24bc3bdd728d4be9a82e9 큰돌님 제가 작성한 코드로는 . (예제 입력1 의 7번 "공백.") 이걸 입력하면 .이 출력 되면서 .이 왜 출력되는지 모르겠고 어디 부분이 잘못된 것인지도 모르겠습니다. 코드가 잘못된 부분 조언 부탁드립니다 !
std::set은 레드블렉 트리로 구현하여 삽입, 삭제, 검색 모두 O(logN)인걸로 알고있습니다. 이분 탐색도 시간 복잡도가 O(logN)인데 왜 std::set을 사용하면 더 느린지 궁금합니다. 아래는 풀이 소스코드입니다. #include <bits/stdc++.h> using namespace std; int32_t t, n, m, tmp; set<int32_t> s; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> t; while (t--) { cin >> n; s.clear(); for (int32_t i = 0; i < n; ++i) { cin >> tmp; s.emplace(tmp); } cin >> m; for (int32_t i = 0; i < m; ++i) { cin >> tmp; if (s.contains(tmp)) { cout << "1\n"; } else { cout << "0\n"; } } } return 0; }
용량(x)이 13이고 병에 들어있는 용량(arr[e])이 13일 때, 즉 arr[e] == x: 일 때 cnt += 1 하고 e 부분만 빼기 1을 해주는 부분에서 이해가 되지 않았습니다. 문제에서 "두 개를 반납해야 새로운 용량을 준다고 했는데" 선생님께서는 최대용량(13)일 때 하나만 반납했기 때문에 이해가 잘안되네요.. 이 부분 한번 설명 해주실 수 있으실까요?
오랜만에 햇갈려서 제네릭 다시볼려고 영한님 찾아왔습니다. 제네릭메서드랑 와일드카드 언제쓸지 구분할때 좀더 명확한 타입이 필요할때 제네릭 타입을 쓰면 될까요 ? 좀 햇갈리네요 이부분이 강의 예시코드를 보면 Dog dog = WildCardEx.printAndReturnGeneric(dogBox); //Dog 타입 Animal animal = WildCardEx.printAndReturnWildcard(dogBox); // 부모 타입 (Animal ) 이렇게 나와서 특별한 형 변환이 필요없을때 와일드 카드를 쓴다고 생각하면 맞는생각일까요 ?
