// 정답코드 else if(S[i]>='a' && S[i]<='z'){ if (S[i] + 13 > 'z'){ S[i] = S[i]-26+13; } else{ S[i] = S[i] + 13; } } // 입력: Baekjoon Online Judge // 출력: Onrxwbba Bayvar Whqtr // 오류 코드 else if(S[i]>='a' and S[i]<='z'){ S[i] = S[i] + 13; if (S[i] > 'z'){ S[i] = S[i]-26; } } // 입력: Baekjoon Online Judge // 출력: Onrxwbba Bayvar W굌tr문자를 if문에서 비교하기전에 13을 더하면 Judge의 ud부분이 깨지는데 정답코드와 왜 다른건지 궁금합니다.  

섹션1 [기본]시간복잡도 2:39 부분이에요. 여기서 시간복잡도가 전부 더하면 5n²+3n+33ns 아닌가요 왜 5n²+3n+30ns 인가요ㅠㅠ단순 오타인건지 제가 이해를 못하는건지 모르겠네요...ns는 나노세컨드 이런의미인가요..?

안녕하세요이전에도 비슷한 질문이 있었지만 그래도 이해가 잘 가지 않아 질문남깁니다. 문제에서형택이는 앞으로 게임을 다 이긴다하지만 형택이의 게임 기록은 지울 수 없다게임 기록은 이렇다게임 횟수 x : 1~10억이긴 게임 y : 0~X이렇게 되면 게임 횟수 x는 여태까지 진행한 게임 횟수이지 앞으로 할 수 있는 게임의 횟수는 아닌 것 아닌가하는 의문이 생깁니다.강의의 계산식에서도 게임 횟수를 여태까지 진행한 횟수라고 상정하고 초기 z의 계산이 진행되어 있습니다.고민하는 동안 앞으로 몇 판의 게임을 최대값으로 두고 게임을 진행해야하는지 알 수 없기 때문에 이분탐색으로 계산을 진행할 수 없었습니다.수학적인 부분이 약해서 수학적으로 선행된 게임의 횟수가 x라면 추가로 x번 진행하면서 x번 전부 승리했을 때 확률이 바뀌지 않는다면 해당 확률은 변할 수 없다라는 식으로 처리되는 것인지는 잘 모르겠네요 단순히 x가 최대 10억이기 때문에 hi도 10억까지로 잡는다고 하는 부분이 이해가 잘 가지 않아서 질문글을 남깁니다.감사합니다.

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. function solution(str) { let answer = []; for(let i of str) { if(i != ')') answer.push(i); else { while(answer[answer.length - 1] != '(') { answer.pop(); } answer.pop(); } } return answer.join(''); } let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)"; console.log(solution(str));해당 코드도 괜찮은 코드인가요?

클래스 사용해서 작성했는데, 계속 무한 반복을 도는 것 같습니다. 어디가 잘못된건지 잘 모르겠습니다. import java.util.*; class Node implements Comparable<Node>{ int x; int y; int c; Node(int x,int y, int c){ this.x=x; this.y=y; this.c=c; } @Override public int compareTo(Node o) { return this.c - o.c; } } class Main { public static int n,m; public static int INF = (int)1e9; public static boolean[][] visit; public static int[] dx = {0,0,1,-1}; public static int[][] map,dist; public static int[] dy = {1,-1,0,0}; public static int dij(int s1,int s2,int e1, int e2) { PriorityQueue<Node> q =new PriorityQueue<>(); q.offer(new Node(s1,s2,0)); dist[s1][s2] = 0; while(!q.isEmpty()) { Node tmp = q.poll(); int nowx = tmp.x; int nowy = tmp.y; int nowcnt = tmp.c; if(nowcnt>dist[nowx][nowy]) continue; for(int i=0; i<4; i++) { int nx = nowx+dx[i]; int ny = nowy+dy[i]; while(nx>=0 && ny>=0 && nx<n && ny<m && map[nx][ny]==0) { //맵의 범위안을 만족하면 계속 같은 방향으로 이동 nx+=dx[i]; ny+=dy[i]; nowcnt++; } //벽에 막혔다. nx-=dx[i]; //이전 칸으로 이동 ny-=dy[i]; nowcnt--; //이전 칸으로 이동했으니까 갯수 하나 감소 if(dist[nx][ny]>nowcnt) { //우선순위 큐에 넣기 dist[nx][ny] = nowcnt; q.offer(new Node(nx,ny,dist[nx][ny])); } } } //답 출력 if(dist[e1-1][e2-1]==Integer.MAX_VALUE) return -1; return dist[e1-1][e2-1]; } public int solution(int[][] board, int[] s, int[] e){ int answer = 0; n=board.length; m=board[0].length; dist = new int[n][m]; for(int i=0; i<n; i++) Arrays.fill(dist[i], INF); map = new int[n][m]; for(int i=0; i<n; i++) { for(int j=0; j<m;j++) { map[i][j] = board[i][j]; } } answer = dij(s[0],s[1],e[0],e[1]); return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{1, 0}, new int[]{4, 5})); System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 2})); System.out.println(T.solution(new int[][]{{1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}}, new int[]{0, 3}, new int[]{4, 2})); System.out.println(T.solution(new int[][]{{0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 5})); System.out.println(T.solution(new int[][]{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 3})); } }

안녕하세요 큰돌 강사님 코드에 대해 질문있습니다공유 코드입니다http://boj.kr/6afa87cbba6042c59e5314d9cd919887문자형 백터에 연산자를 모두 넣고 연산자 인덱스를 백트레킹하여 순열을 구한 뒤 백터에 대입해서 풀었습니다.해설에 있는 코드와 실행시간 차이가 꽤 많이 나는데 두 코드가 어떤 부분에서 효율성의 차이가 나는지 궁금하여 질문 남깁니다.

아래 코드가 시간초과가 나는데 이유를 모르겠습니다. https://www.acmicpc.net/source/62130856ekjongh@gmail.com

 위 문제를 파이썬으로 시도했습니다. 몇 주 동안 cpp하다가 파이썬으로 하니 파이썬이 불편함이 있네요..아래 코드를 실행한 경우, 시간 초과가 떴습니다. 제 생각에는 cpp 내용으로 파이썬 문법으로 그대로 옮겨 적은 거나 마찬가지라고 생각하는데요.from sys import stdin def main(): ret = 0 ans = [] n, m = map(int, stdin.readline().split()) visited = [0 for _ in range(n + 1)] tree = [[] for _ in range(n + 1)] def dfs(root: int): visited[root] = 1 cnt = 1 for there in tree[root]: if not visited[there]: cnt += dfs(there) return cnt for _ in range(m): a, b = map(int, stdin.readline().split()) tree[b].append(a) for i in range(1, n): cnt = 0 visited = [0 for _ in range(n + 1)] if len(tree[i]) != 0 and not visited[i]: cnt = dfs(i) if cnt > ret: ans.clear() ret = cnt ans.append(i) elif cnt == ret: ans.append(i) s = "" for i in ans: s += str(i) + " " print(s) if __name__ == "__main__": main() cpp 쓰다가 파이썬을 쓰니 초기화하는 것도 불편하고, 시간도 많이 걸립니다. (오랜만에 파이썬으로 다시 짜보면 무슨 느낌일지 궁금해서 시도해봤습니다. 아직은 병행하지 않고, 강의 완주 후에 파이썬으로 해볼 생각입니다. 파이썬을 사용하려는 이유는 파이썬을 사용하는 백엔드 회사에 들어갈려고 하거든요. 백엔드로 취업할려면 자바 스프링하라는 영상을 이미 시청했습니다.)main 안에다가 변수를 선언하고 그 안에 dfs 함수를 사용해서 클로저 방식으로 사용해봤는데요. 클로저를 사용 안하고 아래 조건문 안에 선언한 후,if __name__ == "__main__": ... visited = [0 for _ in range(n + 1)] main() 아래 코드처럼 dfs()를 호출하기 전에 visited를 초기화했음에도 불구하고도, for i in range(1, n): cnt = 0 visited = [0 for _ in range(n + 1)] if len(tree[i]) != 0 and not visited[i]: cnt = dfs(i) dfs()는 main()을 호출하기 전 visited를 인식하여 문제 풀이에 에러가 발생하는 것 같습니다. 일반적으로 변수를 선언한 후, 초기화하면서 변수에 그 값을 담는 방식이라면 파이썬은 이와 달리 변수 이름이 그 값에 라벨링처럼 지시하는 방식이라서 새롭게 변수를 생성하여 다른 변수로 인식하는 것 같습니다.global 이나 nonlocal 로 선언하여 사용하는 방식이 있으나, 이런 경우 시간 초과가 발생하더군요. 어떻게 해결할 수 있을까요? 

안녕하세요. 강의 잘 듣고있습니다.아래 코드 체크 한번만 부탁드립니다...답과 차이는 child++ 대신 리스트 사이즈로 체크했는데 어떤 반례가 있는지 모르겠습니다.감사합니다 :)http://boj.kr/9d478a7184dd4667ba1266a2ac37acb0

일단 먼저 풀어봤는데, 객체지향으로 풀려고 Player라는 클래스를 생성 후 몸무게와 키를 저장해 이중 for문으로 풀었는데 통과해버렸습니다.해당 코드는 150~200ms정도가 나오는데 통과하는게 정상인건지 궁금해서 여쭤봅니다. import java.util.Scanner; class Player { int height; int weight; public Player(int height, int weight) { this.height = height; this.weight = weight; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Player[] players = new Player[n]; for (int i = 0; i < n; i++) { int height = sc.nextInt(); int weight = sc.nextInt(); Player player = new Player(height, weight); players[i] = player; } System.out.println(solution(n, players)); } private static int solution(int n, Player[] players) { int answer = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (players[i].height < players[j].height && players[i].weight < players[j].weight) { answer--; break; } } } return answer; } }

저는 입력값이 크지가 않아서 가능한 문자열의 길이가 n이 되면 팰린드롬을 체크해서 중복방지를 위해 해시셋에 만족하는 문자열을 담는 걸로 구현을 했습니다.근데 재귀함수 안에서는 출력값이 잘 나오는거 같은데, 그걸 해시에 담았는데, 해시의 크기가 0으로 나옵니다. 무엇이 잘못된건가요??? import java.util.*; class Main { public static boolean[] visit; public static int n; public static String[] ll; public static HashSet<String> ans = new HashSet<>(); public String[] solution(String s){ String[] answer = {}; dfs(0,""); n=s.length(); visit = new boolean[n]; ll = s.split(""); //s를 문자열 배열로 분리 ans = new HashSet<>(); answer = new String[ans.size()]; System.out.print(answer.length); return answer; } public static void dfs(int L, String str) { //문자열 만들어주기 if(L==n) { if(check(str)) { //팰린드롬인지 체크 //System.out.println(str); ans.add(str); } else return; } else { for(int i=0; i<ll.length;i++) { //i번째 문자 썼는지 확인하면서 문자열 만들어주기 if(!visit[i]) { visit[i] = true; dfs(L+1,str+ll[i]); visit[i] = false; } } } } public static boolean check(String str) { //팰린드롬인지 체크 String[] list = str.split(""); int lt=0; int rt= list.length-1; while(lt<rt) { if(list[lt].equals(list[rt])) { lt++; rt--; } else return false; } return true; } public static void main(String[] args){ Main T = new Main(); System.out.println(Arrays.toString(T.solution("aaaabb"))); System.out.println(Arrays.toString(T.solution("abbcc"))); System.out.println(Arrays.toString(T.solution("abbccee"))); System.out.println(Arrays.toString(T.solution("abbcceee"))); System.out.println(Arrays.toString(T.solution("ffeffaae"))); } }

조합으로 이렇게 작성했는데, 답이 다르게 나옵니다.잘못 생각한 부분이 있을까요?? import java.util.*; class Main { public static boolean[] visit; public static int answer; public static int[] white,black; public static int sum1,sum2,n; public int solution(int[][] cans){ int answer = Integer.MAX_VALUE; n=cans.length; white = new int[n]; black = new int[n]; visit = new boolean[n]; int i=0; for(int[] x : cans) { //흰색돌, 검정돌 분리해주기 white[i] = x[0]; black[i] = x[1]; i++; } dfs(0,0); //조합 탐색 시작 return answer; } public static void dfs(int L, int s) { if(L==n/2) { sum1=0; sum2=0; for(int i=0; i<n; i++) { //방문했던곳은 흰색 돌, 그렇지 않은 곳은 검은돌 if(visit[i]) sum1+=white[i]; //흰색돌들의 합 else sum2+=black[i]; //검정색 돌들의 합 } answer = Math.min(answer, Math.abs(sum1-sum2)); } else { for(int i=s; i<n; i++) { if(!visit[i]) { visit[i] = true; dfs(L+1, i+1); visit[i] = false; } } } } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution(new int[][]{{87, 84}, {66, 78}, {94, 94}, {93, 87}, {72, 92}, {78, 63}})); System.out.println(T.solution(new int[][]{{10, 20}, {15, 25}, {35, 23}, {55, 20}})); System.out.println(T.solution(new int[][]{{11, 27}, {16, 21}, {35, 21}, {52, 21}, {25, 33},{25, 32}, {37, 59}, {33, 47}})); } } 

안녕하세요.두 로직이 같은 것 같은데 하나는 맞고 하나는 틀려서 질문드립니다.부분합 계산하는 로직은 똑같은데, 답지 풀이와 다르게 처음에 부분합을 구하고 한 칸씩 옮기면서 다음 값들을 빼고 더하는 로직입니다.<맞는 코드>http://boj.kr/71648b379df54b9da80fe0b80ec8ca33#include<bits/stdc++.h> using namespace std; int N, K, num; vector<int> temperatures; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> K; for (int i = 0; i < N; i++) { cin >> num; temperatures.push_back(num); } int sum = 0; for (int i = 0; i < K; i++) { sum += temperatures[i]; } int ret = -10000000; ret = max(sum, ret); for (int j = K; j < N; j++) { sum = sum + temperatures[j] - temperatures[j - K]; ret = max(sum, ret); } cout << ret << "\n"; }<틀린 코드>http://boj.kr/c2a7e69a69f6426d87429b3920570c4c#include<bits/stdc++.h> using namespace std; int N, K, j; vector<int> temperatures; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> K; for (int i = 0; i < N; i++) { int num = 0; cin >> num; temperatures.push_back(num); } int sum = 0; for (int i = 0; i < K; i++) { sum += temperatures[i]; } int ret = -10000000; ret = max(sum, ret); j = K; do { sum = sum + temperatures[j] - temperatures[j - K]; ret = max(sum, ret); j++; } while (j < N); cout << ret << "\n"; }사실 변경점이 do-while문을 for문으로 바꾼 것 밖에 없는데 맞더라구요...혹시 제가 발견하지 못한 차이점이 있을까요?좋은 강의 감사합니다. ㅎㅎ

if L==n 부분에서 return 을 안해도 되나요?예를 들면 DFS(6,30,20) -> DFS(7,30,20) 이런식으로 dfs 재귀가 무한으로 반복되는거 아닌가 헷갈리네요.. 

강사님 강의중에 파이썬 강의가 두 개 있고, 두 강의 모두 입문용으로 되어있는데 커리큘럼을 보면 내용이 겹치는 것 같은데 [입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]]강의는 요약, [파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)]강의는 전체적으로 학습하는걸로 이해하고 이 강의만 들어도 될까요?

만약 강의에서처럼 규칙을 찾지 못해서큐로 구현했는데, 이렇게 구현하면 안되는건가요??? import java.util.*; class Node{ int number; //해당 작업의 작업시간 int idx; //작업 번호 Node(int number, int idx){ this.number = number; this.idx = idx; } } class Main { public static Queue<Node> q= new LinkedList<>(); public int solution(int[] tasks, long k) { int answer = 0; for(int i=0; i<tasks.length; i++) { q.offer(new Node(tasks[i],i+1)); //1 2 3, 각 작업 번호들 대입 } long time=0; while(!q.isEmpty()) { Node tmp = q.poll(); int nownumber = tmp.number; int nowwork = tmp.idx; nownumber--; time++; if(time==k) { answer = nowwork; break; } if(nownumber!=0) { q.offer(new Node(nownumber, nowwork)); } } return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution(new int[]{1, 2, 3}, 5)); System.out.println(T.solution(new int[]{8, 5, 2, 9, 10, 7}, 30)); System.out.println(T.solution(new int[]{8, 9, 12, 23, 45, 16, 25, 50}, 100)); } }

이렇게 작성했는데, 시간 복잡도에 걸리지 않게 작성한것이 맞나요?? import java.util.*; class Main { public int solution(int[] score, int k){ int answer = 0; Arrays.sort(score); int sum=0; ArrayList<Integer> ans = new ArrayList<>(); //k개 원소를 담을 리스트 for(int i=0; i<score.length; i++) { //배열을 처음부터 탐색한다. int diff = score[i+k-1] - score[i]; //앞 뒤 원소의 차이를 구한다. if(diff<=10) { //만약 그 차이가 10이하이면 int cnt=0; //개수를 세기위한 변수 int j=i; //i번째 원소부터 시작해서 리스트에 담는다. while(true) { //10이하의 경우에서 제일 첫번째로 찾는게 정답이다. if(cnt==k) break; //k개만큼 담았으면 반복문 멈춘다. ans.add(score[j++]); //답에 해당하는 원소들을 ans에 담아준다. cnt++; } break; } } sum=0; //원소들의 합계를 구하기 위한 변수 for(int i=0; i<ans.size(); i++) { sum+=ans.get(i); } answer = (int)sum/k; return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution(new int[]{99, 97, 80, 91, 85, 95, 92}, 3)); System.out.println(T.solution(new int[]{92, 90, 77, 91, 70, 83, 89, 76, 95, 92}, 4)); System.out.println(T.solution(new int[]{77, 88, 78, 80, 78, 99, 98, 92, 93, 89}, 5)); System.out.println(T.solution(new int[]{88, 99, 91, 89, 90, 72, 75, 94, 95, 100}, 5)); } }

이진수를 나타내는 Integer.toBinary()를 사용해서 사용자 정렬로 했는데, 답이 다르게 나옵니다. 라이브러리 함수를 사용하면 안되는 건가요??  import java.util.*; class Node implements Comparable<Node>{ int idx; //배열의 원소값 int cnt; //1의 개수 Node(int idx, int cnt){ this.idx = idx; this.cnt = cnt; } @Override public int compareTo(Node o) { if(this.cnt==o.cnt) return this.idx - o.idx; //1의 개수가 같으면 배열의 원소를 기준으로 오름차순 else return this.cnt- o.cnt; //그게 아니면 1의 개수가 작은것을 기준으로 오름차순 } } class Main { public static ArrayList<Node> list = new ArrayList<>(); public int[] solution(int[] nums){ int[] answer; for(int i=0; i<nums.length; i++) { String s = Integer.toBinaryString(nums[i]); //2진수로 만들어주기 list.add(new Node(nums[i], count(s))); } Collections.sort(list); //조건에 맞게 정렬 answer = new int[list.size()]; for(int i=0; i<list.size(); i++) { answer[i] = list.get(i).idx; } return answer; } public static int count(String ss) { //1의 개수를 세주는 메소드 int cnt=0; String[] list = ss.split(""); for(int i=0; i<list.length; i++) { if(list[i].equals("1")) cnt++; } return cnt; } public static void main(String[] args){ Main T = new Main(); System.out.println(Arrays.toString(T.solution(new int[]{5, 6, 7, 8, 9}))); System.out.println(Arrays.toString(T.solution(new int[]{5, 4, 3, 2, 1}))); System.out.println(Arrays.toString(T.solution(new int[]{12, 5, 7, 23, 45, 21, 17}))); } }

안녕하세요, 틀린 코드에서 일부를 바꿨더니 맞았는데 이해가 되지 않아 질문을 드립니다. cost <= minCost 일때 최소 비용과 선택된 항목들을 갱신할 경우 사전순으로 뒤쪽인 것이 덮어쓰기 때문에 sort가 반드시 필요하게 되지만cost < minCost일때만 갱신할 경우 앞쪽에서 같은 비용인게 먼저 나왔다면 뒤에선 갱신되지 않기 때문에 사전순으로 앞쪽인 답이 나온다고 생각했습니다. for문을 오름차순으로 돌리고 있기에 사전순이 뒤집힐 이유도 없을텐데 어디서 문제가 생기는 걸까요?http://boj.kr/c09cb2b0628143d48288d23ea6a78b82

import java.util.*; class Main { public char solution(int n, String s){ int[] cnt = new int[n]; // 알파벳 등장 횟수 배열 char[] ch = s.toCharArray(); for (int i = 0; i < n; i++) { cnt[ch[i]-65]++; // count배열에 a,b,c,d,e 투표결과 저장 } int max = Integer.MIN_VALUE, answer =0; for(int i = 0; i<5; i++){ // count배열의 인덱스 0,1,2,3,4만 체크 if(cnt[i] > max){ answer = i; max = cnt[i]; } } return (char)(answer+65); } public static void main(String[] args){ Main T = new Main(); Scanner kb = new Scanner(System.in); int n=kb.nextInt(); String str=kb.next(); System.out.println(T.solution(n, str)); } }이렇게 짜도 괜찮을까요?