시간복잡도 강의에서 n이 100만일 때를 가정해서 설명해주셨고, 상수는 무시한다라는 걸 확인했습니다. 만약, 0부터 n까지 도는 for문 하나가 100만개 있다고 가정하면, 이것 또한 상수를 무시해서 Big-O 표기법으로 O(N)이 되나요? 아니면 N * N이 되므로 O(N^2)이 되나요?

function solution(s, arr){ let answer = 0; let delivery = [] let prods = [] let max = arr[0][0] for(let i=0; i<arr.length;i++){ prods.push(arr[i][0]) delivery.push(arr[i][arr[i].length-1]) for(let j=0; j<arr[i].length;j++){ if(max <= arr[i][j]){ max = arr[i][j] } } } const res = prods.map((x,idx)=>{ if(x== max){ x = x/2 } return x+delivery[idx] } ).sort((a,b)=> a-b) res.reduce((acc,cur)=>{ if(acc<= s){ answer ++ } return acc+cur },res[0]) return answer } let arr=[[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]]; solution(28, arr)할인을 위 코드 처럼 가장 가격이 큰 상품에 다가 적용했는데 이런 경우 예외 케이스가 발생할까요?  

강사님 안녕하세요!코드를 보다가 궁금한 점이 있어 질문드립니다.저는 아래와 같이 최소 값을 따로 배열로 걸러내서 Math.min을 사용해서 구했습니다.강사님 방식과 비교해보니 저는 배열을 하나 더 썼고 Math.min을 사용했기 때문에 제 코드가 조금 더 비효율적으로 보이는데, 저와 비슷하게 코드를 짠 분의 답글에 괜찮은 코드라고 하시더라구요!두 코드 사이의 속도나 효율성면에서는 큰 차이가 없는 것인가요? function solution(arr){ let answer = []; let sum = 0, min = 0; arr.forEach((num) => { if (num % 2 !== 0) { sum += num; // 합산하기 answer.push(num); // 홀수 걸러내기 } }) min = Math.min(...answer); answer = [sum, min]; return answer; } 

안녕하세요 교수님, 질문이있어서 글 남깁니다.교수님과 살짝 다른풀이로 풀었는데, 채점하는 사이트에서 계속 첫번째 케이스에서 runtime error가 나서요ㅠㅠ다른 테스트케이스들은 잘돌아가는데 첫번째만 안돌아갑니다ㅜㅜ자바 이클립스에서도 문제없이 예제테스트케이스 (첫번째 테스트케이스) 돌아갑니다.... // 서로소 집합 (유니온파인드) import java.util.*;  class Main { static int n,m=0; //n:학생수, m:순서쌍개수static int[] parent; public static int find(int x) {if(x==parent[x]) return x;elsereturn parent[x]=find(parent[x]); //최상위 부모 누구인지  }  public static void main(String[] args) {Main tree=new Main();Scanner scanner=new Scanner(System.in);n=scanner.nextInt();m=scanner.nextInt();parent=new int[n+1]; //배열 초기화 해야됨 - 자기자신이 부모가 되도록 초기화for(int i=1; i<=n; i++) {parent[i]=i;}  //입력받아서 배열만들기for(int i=1; i<=m; i++) {int par=scanner.nextInt();int son=scanner.nextInt();parent[son]=par;} int a=scanner.nextInt();int b=scanner.nextInt();   if( (tree.find(a)) != (tree.find(b)) ){ System.out.print("NO"); } else System.out.print("YES"); } }

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.완전탐색부터는 강의가 없는데 해당 강의는 업데이트가 되는건가요? 아니면 추가로 결제를 해야할까요??

안녕하세요 선생님! 강의 항상 잘 보고 있습니다. 저는 이 문제 예외처리를 합해서 생각한 게 아니라 나눠서 비교해도 될 것 같아서 그렇게 로직을 짰는데, 실패했고 '내 코드보기'를 하면 Error를 뱉고 있더라고요 혹시 어떤 문제일까요?강의 보고 합한 걸로 처리하니까 통과 됐고, 합해서 하는 게 더 좋은 거라는 생각은 했는데, 나눠서 생각한 게 왜 틀린지를 잘 모르겠습니다. 33~36 line 입니다. 링크 첨부합니다~https://www.acmicpc.net/source/57441252

안녕하세요 큰돌님! 다름이 아니라 1-K를 이런 식으로 풀어봤습니다. 하지만 자꾸 틀리는데 반례를 못찾겠어서 질문 드려봅니다. <코드 설명>저 같은 경우 map을 이용해 <한 문자, 문자 개수>를 만들어 개수가 홀수인 문자가 2개 이상이면 "I' m sorry Hansoo"를 출력하며 종료하고 그 외에는 팰린드롬을 만듭니다. 팰린드롬은 다시 문자의 개수가 홀수인 문자가 존재하는 경우와 아닌 경우로 나뉘는데, 존재하는 경우 tmp에 잠시 저장해놓고 나머지는 ret에 철자순으로 저장합니다그리고 tmp를 ret에 붙인 다음에 substr로 해당 문자열을 복사한 뒤 temp에 저장합니다. 마지막으로 temp를 reverse로 역순배치를 하여 ret에 이어붙입니다.최종적으로 이를 출력하는 로직입니다.(문자의 개수가 모두 짝수인 경우는 tmp를 ret에 붙이는 과정만 없고 나머진 동일합니다)정말 열심히 생각해서 풀었는데 왜 틀렸는지 조차 몰라서 매우 속상합니다...반례나 틀린 부분이 어디인지 알려주신다면 정말 정말 감사하겠습니다...!  #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); map<char, int> mp; string word, ret; bool isOdd = false; int cnt = 0; char tmp; cin >> word; for(int i = 0; i < word.size(); i++) { mp[word[i]]++; } for(auto it : mp) { if((it).second % 2 == 1) { cnt++; if(cnt > 1) { cout << "I'm Sorry Hansoo"; break; } tmp = (it).first; isOdd = true; for(int i = 0; i < (it).second / 2; i++){ ret += (it).first; } } else { for(int i = 0; i < (it).second / 2; i++){ ret += (it).first; } } } string word2 = ret; if(isOdd) { word2 += tmp; string temp = ret.substr(0, temp.size() - 1); reverse(temp.begin(), temp.end()); word2 += temp; } else { string temp = ret.substr(0, temp.size()); reverse(temp.begin(), temp.end()); word2 += temp; } if(cnt < 2) cout << word2; return 0; }

알고리즘 교안 33pa.find("love") 부분에 대한 이해가 맞는지 질문드립니다.it = a.find("love") 에서 it 값이 love가 있다라고 결정되면it != string::npos -> string::npos(string이 없다)와 값이 같지 않아서 있다고 인정된다맞을까요? C언어에 대한 기초 강의를 듣고 시작해도 조금 버겁네요ㅜㅜ

#include <bits/stdc++.h> using namespace std; int N, M, res; int vis[54][54]; char bd[54][54]; string s; vector<pair<int,int>> land; vector<int> select_land; int dy[4] = {0, -1, 0, 1}; int dx[4] = {1, 0, -1, 0}; void bfs(){ pair<int,int> st = land[select_land[0]]; // land pair<int, int> ed = land[select_land[1]]; // land queue<pair<int,int>> Q; Q.push({st.first, st.second}); // Q삽입 vis[st.first][st.second] = 1; // 방문표시 while(!Q.empty()){ pair<int, int> cur = Q.front(); Q.pop(); for(int dir = 0 ; dir < 4 ; dir++){ int ny = cur.first + dy[dir]; int nx = cur.second + dx[dir]; if(ny==ed.first && nx==ed.second) { vis[ny][nx] = vis[cur.first][cur.second] + 1; res = max(res, vis[ny][nx]); return; // 도착하면 종료 } if(ny >= N || nx >= M || ny < 0 || nx < 0) continue; if(bd[ny][nx]=='W' || vis[ny][nx]!=0) continue; // 방문했거나 물이면 pass Q.push({ny, nx}); vis[ny][nx] = vis[cur.first][cur.second] + 1; } } // 도착하지 못했다면, 그냥 for문을 빠져나옴. (res 업데이트 필요 X) } void solve(int n){ if(select_land.size()==2){ // 2개를 고름. bfs(); fill(&vis[0][0], &vis[0][0] + 54*54, 0); // vis배열 초기화 return; } for(int i = n+1 ; i < land.size() ; i++){ // 땅 전체 개수 (0번부터 land.size()-1번까지) select_land.push_back(i); // 01, 02, 03 ..... solve(i); select_land.pop_back(); } return; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i = 0 ; i < N ; i++){ cin >> s; for(int j = 0 ; j < M ; j++){ bd[i][j] = s[j]; if(s[j]=='L') land.push_back({i,j}); } } // 입력 받기 solve(-1); cout << res-1; }저는 랜드를 모두 구해서 랜드 중에 2개를 뽑고, 최단거리를 구하고 최단거리중 최대값을 뽑는 로직으로 구해봤습니다. 그런데 시간복잡도에서 계속 걸리네요 ㅠㅠ 혹시 크기가 50*50이라 재귀적으로 하려했는데 이 코드는 시간복잡도가 어떻게 되나요 ㅠㅠ

import java.util.*; import java.io.*; /* 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 입력 : 첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다. 출력 : 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. ex. 3 1 2 5 15 -> 3 ( 출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다. ) */ public class P05_동전교환 { static int N, total, answer; static Integer[] coins; public static void main(String[] args) throws Exception { // 초기 세팅 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); coins = new Integer[N]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i=0; i<N; i++) { coins[i] = Integer.parseInt(st.nextToken()); } total = Integer.parseInt(br.readLine()); // 로직 Arrays.sort(coins, Collections.reverseOrder()); // coins 내림차순 정렬 (int[] 배열이 아닌 Integer[] 배열이여야 함 !!) // 방법1. BFS // BFS(); // 방법2. DFS answer = total; DFS(0, 0); // 출력 System.out.println(answer); } public static void BFS() { Queue<Integer> q = new LinkedList<>(); for (int i=0; i<N; i++) { q.offer(coins[i]); } int count = 1; while (true) { int size = q.size(); for (int i=0; i<size; i++) { int tmp = q.poll(); for (int j=0; j<N; j++) { int next = tmp + coins[j]; if (next == total) { answer = count + 1; return; } q.offer(next); } } count++; } } public static void DFS(int count, int sum) { if (sum > total || count >= answer) { return; } if (sum == total) { answer = Math.min(answer, count); } else { for (int i=0; i<N; i++) { DFS(count+1, sum+coins[i]); } } } } 처음에 혼자 풀 때 BFS 문제인 것 같아 BFS로 풀었고, 강의보고 나서 다시 DFS로 풀어봤는데DFS와 BFS 풀이 방법 중 어느 것이 더 좋은 방법인가요 ?성능면에서 DFS와 BFS 중 어떤 것이 더 좋은지 궁금합니다 .. !

function solution(size, arr) { const cache = new Array(size).fill(0); let hit; for (let i = 0; i < arr.length; i++) { hit = false; for (let j = cache.length - 1; j >= 0; j--) { if (hit) { cache[j + 1] = cache[j]; } if (cache[j] === arr[i]) { hit = true; } } if (!hit) { cache.unshift(arr[i]); cache.pop(); } else cache[0] = arr[i]; } return cache; }바깥 for문 처음에 캐시 배열에 찾는 값이 있는지 확인하는 반복문을 한번 돌지 않고, 한번만 반복문을 돌면서 hit가 발생한 이후부터만 뒤로 한칸씩 미는 방법으로 코드를 짜봤습니다.이렇게 작성해도 괜찮을까요? 반례 있을까요?

public static void DFS(int index, int sum) { if (sum > C) { return; } if (index == N) { answer = Math.max(answer, sum); return; } else { DFS(index+1, sum+arr[index]); DFS(index+1, sum); } }if(index == N) {} << 여기에서 강사님은 return;을 따로 쓰지 않으셨던데 return; 을 쓰거나 쓰지 않는 기준이 따로 있는건가요 ?? 어차피 저쪽으로 가게된다면 맨 마지막 줄이기 때문에 따로 return; 을 작성하지 않으신건가요 ?

안녕하세요!! 이 문제 해설 코드를 보다가 궁금한 점이 생겨서 질문 드립니다.상어가 이동하고 한칸에 두마리가 있을 때 큰 상어가 나머지 상어를 먹는 부분인데요, 제가 잘못 이해하고 있는 건가 싶은게 있습니다. 코드 67번째 줄 부분인데요. # i는 1부터 M까지 if(temp[ny][nx]) { if(a[temp[ny][nx]].z < a[i].z) { a[temp[ny][nx]].death = 1; temp[ny][nx] = i; } else a[i].death = 1; } else temp[ny][nx] = i;이때 i가 1인 경우에도 이미 상어가 있는 곳으로 이동하는 경우도 있을 수 있지 않나요?제가 잘못 이해하고 있는건지.. 고민하다가 질문드립니다. 감사합니다!

5-H 풀이 강의투포인트 개념적용되는 문제로,중복되는 숫자가 나올때까지 e 를 증가시키고중복되는 수가 나오면 s 를 증가시키는 개념인 것은 이해를 했습니다만,s/e 가 변화해가면서 실질적으로 경우의 수를 산출하는 디테일한 부분에서 설명하신 내용만으로는 이해되지 않는 부분이 있어 질문 남깁니다. 4:41 경에1을 포함하는 집합을 다 빼야한다고 말씀해주셨는데요.말씀하신 문맥 흐름 상으로만 보면 경우의수에서 뺀다는 뜻으로 이해가 될 수가 있을 것 같습니다.코드상 ret 에는 아래와 같이 더해주는데 ret+=(e-s);뺀다는 표현이 어떤 의미인지 확인 부탁드립니다.코드 기반으로 제가 이해한 것은e = 3, s = 0 인 경우 (e-s) = 3 이고,1 / 12 / 123 에 대한 경우의 수를 ret 에다가 더해주는 것으로 저는 이해했습니다.   4:59 경에s=1 이 되면서 "이 구간(=갈색구간?)" 이 완성되는거라고 하셨는데, s 가 0 에서 1 이 되면서 비로소 2 / 3 / 1 구간 설정이 되는것인데, s=1 이 되고 2 / 3 / 1 구간에 대한 경우의 수를 확인할수있게 되는 것으로 보이는데요완성되었다는 표현이 어떤것을 의미하는것인가요? 

강사님이 강의에서 짜주신 코드처럼while (!q.isEmpty())로 하면 강의에서 보여주신 것처럼 return 이 따로 없을경우 에러가 나는데 (그래서 강의에서는 따로 return 0; 해주셨어요)while (true)로 하면 따로 return 이 없어도 에러가 안납니당 ,,혹시 while (true) 일때는 return 이 강의에서처럼 따로 없어도 에러가 안나는 이유가 있나요 ..? BFS 함수만 첨부하면 다음과 같습니닷// 방법3. BFS 상태트리탐색 (최단거리 BFS) - (2) : 로직 자체는 방법2와 동일, 배열 사용 및 코드 리팩토링 ! public static int BFS2(int S, int E) { Queue<Integer> q = new LinkedList<>(); int[] check = new int[10001]; int[] go = {-1, 1, 5}; // = 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. // 0번째 세팅 q.offer(S); check[S] = 1; int level = 0; // while (!q.isEmpty()) { while (true) { int size = q.size(); for (int i=0; i<size; i++) { int tmp = q.poll(); // if (tmp == E) { // return level; // } for (int j=0; j<go.length; j++) { int nx = tmp + go[j]; if (nx == E) { return level + 1; } if (check[nx]==0 && 1<=nx && nx<=10000) { q.offer(nx); check[nx] = 1; } } } level++; } }  

강사님이 작성하신 코드에서DFS 함수 위에 나머지는 다 앞에 static 붙여서 정적변수로 해놓으셨는데boolean flag = false; 만 static이 안 붙여져있더라구여boolean 형에만 static을 안 붙이신 이유가 있으신가여?DFS 함수 내에서만 사용되기 때문에 안 붙이신 건가요 ?

강의 듣기 전, 혼자 풀어볼 때 코드를 이렇게 짰는데 이것도 맞는 풀이일까요 ...?import java.util.*; import java.io.*; /* N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. ex. 6 1 3 5 6 7 10 -> YES */ public class P01_합이같은부분집합_DFS_아마존인터뷰 { static int total; static int[] arr; static String answer; static int index; static int sum; static int N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); arr = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); total = 0; for (int i=0; i<N; i++) { arr[i] = Integer.parseInt(st.nextToken()); total += arr[i]; } index = 0; sum = 0; answer = "NO"; DFS(index); System.out.println(answer); } public static void DFS(int index) { if (sum*2 > total || index==N) { return; } else { sum += arr[index]; if (sum*2 == total) { answer = "YES"; return; } DFS(index+1); sum -= arr[index]; DFS(index+1); } } } 채점 사이트에서 통과하기는 하는데 이 풀이가 맞아서 통과한건지 아님 운좋게(?) 테스트 케이스 5개가 다 맞아서 통과한건지 뭔가 풀이에 대한 확신이 없어서요 .. !

그래프 내용이 없네요 ㅠㅠ 그냥 화면에 있는거 받아적으면 되나요?

안녕하세요 큰돌님.강의 너무나도 잘 보며 공부하고 있습니다!2-p 연구소 조합을 재귀로 작성해 보았습니다.for문으로 조합을 구하는것과 별로 다른것이 없는거 같은데 재귀로 구하니 백준 2번째 테케가 틀리게 나옵니다! 시간되실때 봐주시면 정말 감사드리겠습니다!http://boj.kr/7ee04a6b382f416abe6647adff8912c6

http://boj.kr/b293b7352cda4189a70ce187abf9f9420퍼에서 바로 틀렸습니다 가 계속 뜨는데 어디가 잘못된건지 모르겠습니다. 한줄한줄 보기도하고 TC다 넣어봤는데 이상이 없었습니다