from itertools import permutationsinfos = list(input())ans = 0for comb in set(permutations(infos)): ok = True for i in range(0,len(infos)-1): if comb[i] == comb[i+1] : ok = False break ans += okprint(ans)BOJ 1342번 문제를 다음과 같이 풀었는데 계속해서 메모리초과 때문에 오답처리가 나서 질문 남깁니다.permutations가 한 번에 모든 순열을 생성하기 때문에 메모리 문제가 발생한다고 GPT의 답변을 얻을 수 있었으나, 강사님의 풀이 1번에도 permutations가 있는데도 메모리초과가 나지 않고 정답처리가 나서 왜 이런 차이가 나는 지 궁금합니다. 

안녕하세요. 선생님. 문제는 다 이해가 됐는데 코드 시간때문에 질문 올립니다.void make1(int num, vector<int>& pSum, map<int, int>& pCount) { for (int interval = 1; interval < num; interval++) // 피자 조각을 몇 개를 더 이어서 고를 것인지, 전부 선택은 제외 { for (int start = interval; start <= num + interval - 1; start++) { int sum = pSum[start] - pSum[start - interval]; pCount[sum]++; } } pCount[pSum[num]]++; // 전부 선택하는 경우}void make2(int num, vector<int>& pSum, map<int, int>& pCount){ for (int start = 1; start <= num; start++) // 첫번째부터 출발 { for (int interval = 0; interval < num - 1; interval++) // 피자 조각을 몇 개를 더 이어서 고를 것인지, 전부 선택은 제외 { int tPSum = pSum[start + interval] - pSum[start - 1]; // 사이즈 pCount[tPSum]++; // 해당 사이즈 카운트 추가 } } pCount[pSum[num]]++; // 전부 선택하는 경우}make1함수를 사용시 840ms정도 걸리고,make2함수 사용시 480ms정도 걸립니다.왜 이럴까요...? 챗 지피티는 메모리 접근이 순차적이지만, '일정한 간격 유지'가 '인덱스 하나 고정 + 순차 증가'보다 cpu 캐시 히트가 더 유리해서 라는데, 혹시 제가 놓치고 있는 부분이 없을까요?

my_input = sys.stadin.readline 으로 정의해주셨는데, 혹시 my_input = sys.stadin.readline() 이렇게 정의하고 list(map(int, my_input.split()))이렇게 쓸 수도 있나요?

http://boj.kr/e8efaf05143848f897d8154f0609f71e현재 코드는 맞았습니다. 가 뜹니다. 맞은 이유가 // ios_base::sync_with_stdio(false); // cin.tie(NULL); // cout.tie(NULL);이렇게 주석처리를 하니까 맞더라구요.. 이것때문에 2틀정도 머리를 싸맸는데 왜 위 코드 3줄을 주석처리 한다고 맞았습니다 가 뜨는지 잘 이해가 안가는데 왜 그런것인가용??

http://boj.kr/24eb99ddd0bb4e11af50a5e4579c8107 해당 문제에 대해서 진짜 많이 고민해보았는데, 원인을 알 수가 없습니다.. 기본적인 부분에서 틀린 것 같은데, 코드가 지저분한 것 같아서 그런지 봐도 문제가 무엇인지 잘 모르겠습니다 ㅠㅠ

LCA 코드에서 left, right 변수는 방명록 (visited) 변수와 같이 방문한 값을 저장하기 위한 용도로 사용하는 것인 가요?!

pq를 쓰지 않고, 골동품 가치를 내림차순으로 정렬하고 가방 무게를 오름차순으로 정렬해서 풀면 틀린 명제일까요??

이전강의에서 풀엇던것처럼 ch체크 배열만들고 시계방향 9,12,3,6시 방향으로만 체크해서 이렇게 만들었는데강사님이 강의 때 하셧던거에 비하면 효율이 많이 떨어지는지 궁금해서 질문 남깁니다  package section9; import java.util.ArrayList; import java.util.Scanner; public class Main13 { static int[] dx= {-1,0,1,0}; static int [] dy= {0,1,0,-1}; static int[][] ch,dir,map; static int n,answer; public static void main(String[] args) { // TODO Auto-generated method stub Scanner s=new Scanner(System.in); ArrayList<Integer> list = new ArrayList<>(); answer=0; n=s.nextInt(); map= new int[n][n]; ch= new int[n][n]; dir= new int[n][n]; for(int i=0;i<n;++i) { for(int z=0;z<n;++z) { map[i][z]=s.nextInt(); } } for(int i=0;i<7;++i) { for(int z=0;z<7;++z) { if(map[i][z]==1 && ch[i][z]==0) { DFS(i,z); if(answer>1) { list.add(answer); answer=0; } }else { answer=0; continue; } } } System.out.println(list.toString()); System.out.println(list.size()); } static void DFS(int x,int y) { if(map[x][y]==1) { answer++; } if(ch[x][y]==1) return; if(map[x][y]==0) return; if(x<0 || x>6 || y<0 || y>6) { return; }else { ch[x][y]=1; for(int i=0;i<4;++i) { int nx= x+dx[i]; int ny=y+dy[i]; if(nx>=0 && nx<7 && ny>=0 && ny<7 && ch[nx][ny]==0 && map[nx][ny]==1) { DFS(nx,ny); } } } } }

제목 그대로 union and find 알고리즘을 써서 이문제를 풀었습니다.풀이를 보니 dfs를 써서 푸는 방법도 있는거 같은데 어떤 접근법이 시간 복잡도가 더 낮은 가요?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하시렵니까 본론부터 말씀드리자면, 해당 강의 3분 27초경에 출력되는 값을 보면 0x...0100x...0100x...0140x...014라는 것을 확인할 수 있는데, 주소 값이 4가 커졌다는 건 int 배열의 각 값들이 4 Byte이기 때문이라고 이해했습니다. 다만 이전 강의에서- int는 4바이트, double은 8바이트니까 포인터도 4, 8바이트가 되어야 하는 게 아닌가?- 포인터의 크기는 실행 OS 체제의 비트마다 달라짐- Window OS 64비트를 사용하는 경우의 포인터 사이즈 = 8 Byte- Window OS 32비트를 사용하는 경우의 포인터 사이즈 = 4 Byte 이러한 내용을 확인할 수 있었는데, int 배열을 포인터로 변환했으니, 이전과 마찬가지로 주소값이 8이 커져야 한다고 생각했는데 그렇지 않았다는 점에서 의문이 생겼습니다! int 배열을 포인터에 할당하면서 포인터로 전환되는 것이 아니라 단순히 주소를 할당했기 때문에 이런 일이 발생하는걸까요? 또한, 포인터의 크기가 8 Byte라고 했을 때, 연속되는 포인터라고 가정한다면 두 포인터의 주소값 차이는 8이 맞는지도 궁금합니다! 감사합니다.

안녕하세요 선생님.#2234 문제에 대해서 Connected Component개념으로 DFS를 소개해주셔서 문제풀이를 이해하는데 수월했습니다. 다만, 처음 문제를 저 혼자 풀 때,각 방 칸의 크기가 1이고, 방 칸의 개수에 따라 방 넓이가 결정되므로 가중치가 동일하니 BFS로도 풀 수 있지 않을까라고 생각되어 아래와 같이 풀어봤습니다.http://boj.kr/896f1a9fbf8e47628666c1c0a8c59db5 각 방을 탐색할때마다 queue를 생성하고 queue pop을 할 때마다 방 칸의 개수를 cnt++라는 변수에 담고,탐색을 더이상 진행할 수 없을 때 방 칸의 개수값 cnt를 return하도록 하여 탐색했는데요. 문제에서 주어진 예제 입력1은 통과했지만 채점에서도 어떠한 반례에 걸려 fail이 발생한 것 같습니다.BFS 탐색 코드에 어떠한 문제점이 있는지 피드백 주시면 감사드리겠습니다... 감사합니다. 

우선순위큐 크기가 가방 총 크기보다 클 때만 큐에서 빼는 로직을 작성했는데 왜 틀렸는지 궁금합니다#include<bits/stdc++.h> using namespace std; typedef long long ll; priority_queue<ll> pq; ll n,k,ret; int main(){ cin>>n>>k; pair<ll,ll> v[n]; //jewelry ll bag[k]; for (int i=0;i<n;i++){ cin>>v[i].first>>v[i].second; } for (int i=0;i<k;i++){ cin>>bag[i]; } int idx=0; //bag index sort(v,v+n); sort(bag,bag+k); int idx2=0; while (idx2<n){ while (idx<k && idx2<n){ if (bag[idx]<v[idx2].first) idx++; else{ if (pq.size()==k){ if (v[idx2].second>pq.top()){ pq.pop(); pq.push(v[idx2].second); } }else if (pq.size()<k) pq.push(v[idx2].second); } idx2++; } } while (pq.size()){ ret+=pq.top(); pq.pop(); } cout<<ret;

n이 15000이고 2초의 제한 시간이라 조합이 떠올랐지만 이중 for문으로 풀 생각을 못했습니다. 문제를 재귀로 풀고 생각해보니 최악의 경우인 15000 * 15000이 될 수 없긴 한데 그래도 N^2의 시간 복잡도인데 어떻게 통과한 것인지 궁금하고 이런 경우 대충?의 시간 복잡도를 어떻게 계산해서 -> 이중 for문으로도 풀어도 되겠다라는 생각까지 이어지는 것인지 궁금합니다.

http://boj.kr/35af496c1fb44628be4b5f27dde803d3문제 보자 마자 조합이 떠올라서 위처럼 풀었습니다.코드 자체에 대한 질문은 아니고 '재귀함수의 시간 복잡도를 어떻게 계산'하는지 궁금합니다.함수를 호출시 스택 프레임이 쌓이고 이것을 반환하고..등등의 작업 까지 생각하는 것은 아닌거같아 질문드립니다.재귀 함수의 깊이가 100이면 O(100)으로 시간 복잡도가 잡히는 것인지 궁금합니다.

안녕하세요 정답과 다르게 코드를 짜봤는데 코드 평가 해주실 수 있나요?? http://boj.kr/e426c9cd01624541b5251528546a8eae 강의 잘 보고있습니다 감사합니다

안녕하세요. 선생님.강의 교안 p.33에서cout << a << " " << "" << b << '\n';"" 빈 문자열을 넣으신 이유가 있을까요?빈 문자열을 빼도 출력 값은 동일하게 보이는데 어떤 의미로 넣으신건지 궁금합니다.혹시 cout 설명처럼 입력할 문자열을 넣을 수 있다를 설명하기 위해서 그런건가요?   

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.#include<iostream> #include<algorithm> #include<vector> #include<utility> using namespace std; int n,person[14],ret =987654321,temp,temp1,visited[14],comp[14]; string s; vector<int> adj[14]; pair<int,int> dfs(int here, int value){//인접구 개수, 인구수 반환 visited[here] =1; pair<int,int> ret = {1,person[here]}; for(int there:adj[here]){ if(comp[there] != value) continue; if(visited[there]) continue; pair<int,int> temp_ = dfs(there,value); ret.first +=temp_.first; ret.second += temp_.second; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i =1; i<=n;i++){ cin>>person[i]; } for(int i =1;i<=n;i++){ cin>>temp; for(int j =0; j<temp;j++){ cin>>temp1; adj[i].push_back(temp1); adj[temp1].push_back(i); } } for(int i =1;i<(1<<n)-1; i++){ fill(&comp[0],&comp[0]+14,0); fill(&visited[0],&visited[0]+14,0); int idx1=-1,idx2 =-1; for(int j =0; j<n;j++){ if(i&(1<<j)){ comp[j+1]=1; idx1 = j+1; } else idx2 = j+1; } pair<int,int> comp1 = dfs(idx1,1); pair<int,int> comp2 = dfs(idx2,0); if(comp1.first+comp2.first == n) ret = min(ret,abs(comp1.second-comp2.second)); } cout<<(ret==987654321 ? -1:ret); return 0; }저는 이렇게 백준에 제출했을때 맞았다고 나오는데 제 vscode에서는 예제에서 밑에 만큼 입력하면 -1이 출력되어 끝나 버립니다 왜 그런건가요..? 다른 문제 풀때도 정답은 맞지만 제가 실행하면 도중에 입력을 그만 받습니다.. ㅠㅠ6 5 2 3 4 1 2 2 2 4 4 1 3 6 5

c@fa$ 가 입력 되었을 때, 제 생각에는결과가 그대로 나와야 하지 않나 싶은데, (짝이 되는 알파벳이 없음) a@fc$이 나오는 이유가 궁금합니다.

http://boj.kr/b3912cd4b65448baa4a27bea951494cb안녕하세요, 큰돌님.해당 문제를 queue를 이용한 BFS로 풀었습니다.더 효율적으로 수정할 부분이 있을까요?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 위험도가 높은 환자 순서로 우선순위 큐를 만들었습니다. 정답으로 찾아야 하는 환자의 위치의 번호를 이동해가면서 현재 치료 받는 환자가 찾아야 하는 환자인지를 체크 했고요. 우선순위 큐에서 poll한 값을 통해서 현재 대기하고 있는 환자가 현재 치료를 받아도 되는지(우선순위가 가장 높은지)를 체크 했습니다. public int solution(int[] input1, int m) { Queue<Integer> q = new LinkedList<>(); Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); int seq = m; for (int i : input1) { q.offer(i); pq.offer(i); } int cnt = 0; while (true) { Integer poll = q.poll(); seq--; if (Objects.equals(pq.peek(), poll)) { cnt++; if (seq == -1) { break; } pq.poll(); } else { q.offer(poll); if (seq == -1) { seq = q.size() - 1; } } } return cnt; }