http://boj.kr/4468d92db7694335bf1119b95b6c26fe테스트 케이스는 모두 통과하는데 어떤 점에서 놓친 부분이 있는지 모르겠습니다.

4주차 이론을 듣고 4-a 를 풀어봤습니다.http://boj.kr/1505ce542738451d97357d5977350e46문제를 딱 보자마자 그냥 완전탐색으로 풀어야겠다고 생각하고비트마스킹 생각을 하지않고 그냥 문제를 풀게 됐고 그 후강의를 보니 비트마스킹을 사용해서 풀이하신 걸 보고어떻게 이 문제를 보고 비트마스킹을 사용해야겠다고 생각하신건지 비트마스킹의 장점이 무엇인지 궁금해서 질문남깁니다. 1.경우의 수를 탐색하는 문제에서 사용하는 것 같은데 나중에는 무조건 비트마스킹을 사용해야만 하는 문제도 있나요? 아니면 이 문제처럼 그냥 완전탐색으로 풀어도 대부분 풀리는 건지 궁금합니다!2. 비트마스킹의 장점은 속도 인가요? 시간 초과가 타이트할 때 사용하는 건지 아니면 다른 장점이 있는 건지 궁금합니다. 이론강의를 듣고 나서도 잘 이해가 안가서 질문드립니다! 

http://boj.kr/3508e81686454e2ea04b64d2c4a3ba94풀이법과 조금 다르지만 같은 원리로 풀었습니다 그런데http://boj.kr/9f02c3d4d7b14d9eb585cb7dabfc6d2a이건 두번째로 생각해본 풀이인데 이 코드는 틀렸다고 나옵니다.두 코드의 차이점은 매개변수 y (지수부분)가 홀수일 때 첫번째 코드는 go(y-1) , go(1) 을 해서 한쪽부분을 짝수로 만들어준 것이고두번째 코드는 go(y/2) ,go(y/2) ,go(1) 로 2로 나눠주면서 홀수라서 남는 부분을 곱해주는 방식입니다. 모듈러 공식이 (a * b) % c = ((a%c)*(a%c))%c 라고 하면(a*b*c)%c 도 같이 적용되어야 하는게 아닌가 싶어서 질문드렸습니다! 

#include <stdio.h> int main() { //freopen("input.txt","rt",stdin); int n,abs,left,right,res=1; scanf("%d",&n); int a[n]={0,}; scanf("%d",&left); for(int i=1;i<n;i++){ scanf("%d", &right); abs=(right-left>0)?right-left:left-right; a[abs]=1; left=right; } for(int i=1;i<n;i++){ if(a[i]!=1) res=0; } if(res==1){ printf("YES\n"); } else{ printf("NO\n"); } return 0; }강의 듣기 전 스스로 짠 코드입니다. 채점결과 마지막 케이스만 이렇게 출력되는데 다섯번째 파일만 따로 돌려봐도 에러없이 종료되어서 원인을 잘 모르겠습니다ㅠㅠ

import java.util.Scanner; public class Main { public String solutions(int target, int[] high) { String answer = ""; for (int i = 0; i < target; i++) { if (answer.isEmpty()) { answer += high[i]+" "; } else if (high[i]>high[i-1]) { answer += high[i]+" "; } } return answer; } public static void main(String[] args) { Main t = new Main(); Scanner sc = new Scanner(System.in); int target = sc.nextInt(); int[] high = new int[target]; for (int i = 0; i < target; i++) { high[i] = sc.nextInt(); } System.out.println(t.solutions(target, high)); } }강의 보기전에 혼자 이렇게 해봤는데 채점 정답처리는 받았습니다. 혹시 문제가 없을까요?

구글폼으로 작성하였습니다.

자바스크립트 강의자료로 공유된 노션 링크가 없는 페이지라고 나옵니다. 파이썬 강의 노션페이지의 경우 전체 리스트는 나오는데 각 섹션이 없는 페이지라고 뜨거나 로딩속도가 느려 보이지 않습니다.

안녕하세요. 큰돌님. 이 문제는 제가 직접 풀지 못해서 선생님 답안을 보고 익히고 있는 중 궁금한 게 생겨서 질문 남깁니다.for문을 나오면 있는 끝점을 계산하는 코드입니다.마지막에 이긴 팀을 기준으로 끝점을 계산하는 게 아닌득점을 많이 한 팀 기준으로 끝점을 계산하신 이유가 궁금합니다

강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)1. 저번 강의에서 풀이하신 것처럼 이번 강의에도 재귀 함수의 depth를 그려보았는데 맞나요?2. 혹시 CS 면접 관련해서 대략 어떻게 준비해야 하는지 질문 드려도 되나요? 

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/7d1b078d34894888995766119fc55780 아래와 같은 사고 과정을 따라 문제를 풀었습니다. 먼저 동생이 0에서 출발하더라도 1000초면 500,000을 넘어간다는 것을 확인했습니다.또한 500,000 크기를 가지는 int형 배열이 약 2MB 정도의 공간만을 차지하므로동생의 위치에 따른 시간을 먼저 broPos 배열에 저장했습니다.ex. 동생이 5를 0초에 방문, 6을 1초에 방문, 8을 2초에 방문 -> broPos[5] = 0, broPos[6] = 1, broPos[8] = 2 이후 수빈이가 bfs를 통해 탐색하되같은 시간에 동생을 만나는 경우(broPos[next] == visited[next] - 1) 리턴후 시간 출력동생의 지나갈 위치를 짝수초만큼 먼저 지나가는 경우 리턴 후 시간 + 짝수초 출력동생이 500,000을 넘는 시간이 지나면 리턴 후 -1 출력 해당 방법으로 문제를 풀이했는데 어느 부분이 틀린걸까요? 

#include <bits/stdc++.h> using namespace std; #define ll long long ll N, M; vector<ll> attractions; // mid 시간안에 놀이기구를 다 탈 수 있는지 확인하는 함수 bool CanRide(ll mid) { ll cnt = 0; for(int i=0; i<M; i++) { cnt += mid/attractions[i]; } return cnt >= N - M; } // 마지막 아이가 타게되는 놀이기구 index 출력 ll GetIdx(ll mid) { ll cnt = M; for(ll i=0; i<attractions.size(); i++) { cnt += (mid-1) / attractions[i]; } for(ll i=0; i<attractions.size(); i++) { if(mid % attractions[i] == 0) cnt++; if(cnt == N) { return i+1; } } return -1; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i=0; i<M; i++) { ll tmp; cin >> tmp; attractions.push_back(tmp); } ll left = 1, right = 60000000009, mid; if(N < M) { cout << N; return 0; } while(left <= right) { mid = (left + right) / 2; if(CanRide(mid)) { right = mid - 1; } else { left = mid + 1; mid = left; } } cout << GetIdx(mid); return 0; }안녕하세요, 문제가 풀리지 않아 선생님의 풀이를 보고 충실히 따라 구현하여 제출하였는데 78%쯤에서 계속 틀렸다고 나와 질문드립니다.이분탐색 범위도 맞게 설정된거 같고, 자료형도 범위에 맞게 long long으로 잘 사용한거 같은데 어디가 틀렸는지 찾을 수 없어 질문드립니다.

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/e5455ffb96284f2d983e2afeae83ec1c 선생님이랑 비슷하게 문제를 풀었습니다.하지만 궁금한 부분이 있어서 질문드립니다.선생님께선 flower부분에 이중 for문을 돌리실 때 i, j =0으로 하셨는데 제 코드의 go함수를 봐주시면 sy, sx를 사용했고 sx가 for문을 벗어나면 sx=1로 초기화해서 i++이 되어도 첫칸부터 탐색할 수 있도록 하였습니다. 이렇게 작성한 이유가 i,j를 0으로 설정해서 탐색을 하면 탐색을 했던 부분을 또 탐색을 해서 시간초과가 나오지 않을까 생각했기 때문입니다. 혹시 다른 문제가 나와도 현재 제가 올린 코드처럼 sy, sx를 사용해서 코드를 짜도 큰 문제가 없을지 궁금합니다.

안녕하세요 선생님. 선생님 강의와 함께 학교랑 병행하면서 알고리즘 공부한지 한달 정도 됐네요. 시작과 비교했을때 bfs, 완전탐색 개념이 조금씩 쌓이고 문제를 혼자서 다 풀 수는 없지만 80퍼는 그래도 혼자 코드를 짤 수 있는 실력이 생긴 걸 보아 실력이 조금씩 느는것 같긴 하네요..!1,2학년때 다른 공부를 준비한다고 현재 3학년되서 알고리즘을 첨하지만 열심히 하고 있는데 내년엔 4학년이라 늦은 것 같아서 불안해지네요,,

안녕하세요 지식공유자님덕분에 많은 도움이 되고 있습니다.강의 영상 캡쳐 및 내용 정리를 활용하여 개인블로그에 업로드해도 될까요? 출처는 해당 인프런 강의 링크를 달도록하겠습니다.

안녕하세요, 12번 멘토링 문제 풀다가 첫 번째 채점 결과 값이 3으로 잘 나왔습니다. 그런데 그 다음 입력부터는 전부 오답이 나오는 상황인데, 어떤 부분에서 틀린 건지 알려주시면 감사하겠습니다 ㅠㅠ // package = " "; import java.io.*; import java.util.*; class Main { public int Solution(int n, int m, int arr[][]){ String mathMark = ""; ArrayList<Integer> ans = new ArrayList<>(); HashMap<String, Integer> countMap = new HashMap<>(); for(int i = 0; i < n; i++){ // 첫째부터 계속 다음 줄 내려가서 검사 for(int j = 0; j < m; j++){ // for(int k = 0; k < m; k++){ // System.out.println("j값 : "+j+", "+"k값 : "+k); if(j != k && j < k){ // System.out.println(arr[i][j]+", "+arr[i][k]); if(i == n-1 && j == m-1 && k == m-1){ mathMark += arr[i][j]+""+arr[i][k]; } else{ mathMark += arr[i][j]+""+arr[i][k]+" "; } } } } } /* m개 값을 가지고 있는 수 찾기 */ String numArray[] = mathMark.split(" "); // 숫자 등장 횟수 카운트 for(int i = 0; i < numArray.length; i++){ countMap.put(numArray[i],countMap.getOrDefault(numArray[i],0) + 1); } // 등장 횟수가 3 이상인 숫자 Count for(Map.Entry<String, Integer> entry : countMap.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); if(entry.getValue() == n){ ans.add(1); } } return ans.size(); } public static void main(String[] args) throws Exception{ Main m = new Main(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] numStr = br.readLine().split(" "); // 1. N과 M 입력받기 int column = Integer.parseInt(numStr[0]); int raw = Integer.parseInt(numStr[1]); int arr[][] = new int[raw][column]; for(int i = 0; i < raw; i++){ String[] test = br.readLine().split(" "); for(int j = 0; j < column; j++){ arr[i][j] = Integer.parseInt(test[j]); } } System.out.println(m.Solution(raw, column, arr)); br.close(); } }

문제링크: https://www.acmicpc.net/problem/17136이번 7주차 DP 하면서 자꾸 TLE 뜨다 보니깐 이게 완탐이나 백트래킹으로 가능한지 감이 잘 안잡혀요 ㅠㅠ큰돌님은 이 문제 바로 백트래킹으로 접근해도 된다라는걸 어떻게 파악하신건가요?예를 들어서 테스트케이스 7번0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1가 있고 큰돌님의 코드를 돌려보면 [1,1] 위치에서 만들어 질 수 있는 정사각형의 최대 사이즈는 2이므로 [1,1] 위치에서 2 크기의 정사각형의 색을 칠하면서 탐색하는데 [1,1]의 위치에서는 2의 크기로 색칠하고 시작하면 답이 안된다는걸 사람의 눈으로는 파악이 돼죠 왜냐하면 [1, 2]를 기준으로 크기 4의 정사각형을 그릴 수 있다는걸 알기 때문에요.그럼에도 불구하고 큰돌님은 위 상황을 인지한 상태에서 백트래킹으로 시도를 해보신건가요? 아니면 이게 백트래킹으로 풀린다는걸 아시고 푸신건가요?

package Ex08; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class ex10 { static int[][] arr; static int answer; public static void main(String[] args) throws IOException { ex10 T = new ex10(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); arr = new int[7][7]; for (int i = 0; i < 7; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for (int j = 0; j < 7; j++) { int tmp = Integer.parseInt(st.nextToken()); arr[i][j] = tmp; } } T.DFS(0, 0); // 시작점을 (0, 0)으로 수정 System.out.println(answer); } public void DFS(int dx, int dy) { if (dx == 6 && dy == 6) { // 종료 조건 수정 answer++; } else { int[] dxs = {-1, 0, 1, 0}; // 위, 오른쪽, 아래, 왼쪽 순으로 이동 int[] dys = {0, 1, 0, -1}; for (int i = 0; i < 4; i++) { int x = dx + dxs[i]; int y = dy + dys[i]; if (x >= 0 && x < 7 && y >= 0 && y < 7) { if (arr[x][y] == 0){ arr[x][y] = 1; // 방문한 곳을 1로 표시 DFS(x, y); arr[x][y] = 0; // 백트래킹: 이전 상태로 돌아감 } } } } } }이 코드가 항상 정답값의 두배가 나오는데 어느 로직이 잘못된건지 모르겠습니다ㅠ 

http://boj.kr/63da4f35132841e68fcc5d77ff53fc60말씀해주신 풀이법이랑 좀 다르게 풀었는데,이렇게 하면 왜 오류가 발생하는지 알수있을까요?? 그리고 제 코드에서 org(입력된 원본 배열)를 별도로 만들어 최소visited처리하는데 사용했는데,혹시 이거보다 좀 더 효율적으로 하는 방법 이 있다면 알려주시면 감사하겠습니다!!

해당문제를 푸는데 강사님과 같은 방법으로 풀어나가고 있습니다만, 계속 12% 대에서 실패가 뜹니다. 조건문이 문제인가 싶어 dfs함수에 들어가기 전 조건문 세개 중 두, 세번째를 강의 내용처럼 합쳐보기도 하고, 문제를 잘못읽었나 싶어 map의 범위를 50 50 에서 51 * 51로도 해보고 전역변수 선언에 문제가 있나 싶어 변경도 해봤지만 해결이 안되네요. <http://boj.kr/85c9f690f6c64294a29406a816169cc0>

P11438 문제 교재 코드 그대로 쳤는데 시간초과가 발생하네요 ㅜ어딜 고쳐야 할까요 ㅠimport java.util.*; import java.io.*; public class Main { static ArrayList<Integer>[] tree; static int[] depth; static int kmax; static int[][] parent; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // 노드의 수 tree = new ArrayList[N + 1]; for(int i = 1; i <= N; i++) { tree[i] = new ArrayList<Integer>(); } StringTokenizer st; // 1. 인접리스트에 그래프 데이터 저장하기 for(int i = 0; i < N - 1; i++) { st = new StringTokenizer(br.readLine()); int s = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); tree[s].add(e); tree[e].add(s); } depth = new int[N+1]; visited = new boolean[N + 1]; int temp = 1; kmax = 0; while (temp <= N) { // 최대 가능 depth 구하기 temp <<= 1; kmax++; } parent = new int[kmax + 1][N + 1]; // 2. depth와 바로 윗 부모 bfs로 구하기 bfs(1); // 3. 2^k 부모 구하기 for(int k = 1; k <= kmax; k++) { for(int n = 1; n <= N; n++) { parent[k][n] = parent[k - 1][parent[k - 1][n]]; } } int M = Integer.parseInt(br.readLine()); // 4. 질의 수행하기 for(int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int LCA = excuteLCA(a, b); System.out.println(LCA); } } static int excuteLCA(int a, int b) { // 더 깊은 depth가 뒤에 오도록 변경 if (depth[a] > depth[b]) { int temp = a; a = b; b = temp; } for(int k = kmax; k >= 0; k--) { // 높이 빠르게 맞추기 if(Math.pow(2, k) <= depth[b] - depth[a]) { if(depth[a] <= depth[parent[k][b]]) { b = parent[k][b]; } } } for(int k = kmax; k >=0; k--) { // 조상 빠르게 찾기 // 최대 위로 올라가서 같은 부모를 가리키면 k를 1씩 감소하며 다른 지점을 찾음 if(parent[k][a] != parent[k][b]) { a = parent[k][a]; b = parent[k][b]; } } // 여기 온 것은 k = 0일때 고려 // case 1. k=0, 둘이 같은 노드를 가리킴 -> 그곳이 최소 공통 조상 // case 2. k=0, 둘이 다른 노드를 가리킴 -> 바로 위에가 최초 공통 조상 -> 2^0 위에 보기 int LCA = a; if(a != b) { LCA = parent[0][LCA]; } return LCA; } // bfs 구현 private static void bfs(int node) { Queue<Integer> queue = new LinkedList<>(); queue.add(node); visited[node] = true; int level = 1; int now_size = 1; int count = 0; while(!queue.isEmpty()) { int now_node = queue.poll(); for(int next : tree[now_node]) { if(!visited[next]) { visited[next] = true; queue.add(next); parent[0][next] = now_node; // 부모 노드 저장하기 depth[next] = level; // 노드 depth 저장하기 } } count++; // 자식 노드 모두 검사했는지 확인 if(count == now_size) { count = 0; now_size = queue.size(); level++; } } } }