3-B번 보물섬 문제를 풀다가. 각 육지마다 BFS를 하는 것보다, 한 컴포넌트에서 BFS_1로 임의의 한 점에서 가장 먼 점을 찾고, 찾은 가장 먼 점에서 BFS_2로 또 가장 먼 점을 찾으면, 해당 컴포넌트에서는 가장 먼 점의 길이를 구할 수 있다고 생각하고 풀이하였는데 틀린 이유를 잘 모르겠습니다... 이렇게 풀면 틀린 이유가 있을까요?? 항상 수업 너무 잘 듣고 있습니다. 감사합니다! #include <bits/stdc++.h> using namespace std; int n, m; string a; char mapp[54][54]; bool visited[54][54]; int dis[54][54]; int dy[] = {0,-1,0,1}; int dx[] = {1,0,-1,0}; queue<pair<int,int>> q; queue<pair<int,int>> q2; int max_val = 0; pair<int,int> bfs_1(int y, int x){ visited[y][x]=1; q.push({y,x}); pair<int,int> here; while(q.size()){ here = q.front(); q.pop(); for(int i=0;i<4;i++){ int ny = here.first + dy[i]; int nx = here.second + dx[i]; if(ny<0||nx<0||ny>=n||nx>=m) continue; if(visited[ny][nx]) continue; if(mapp[ny][nx]=='W') continue; visited[ny][nx] = 1; q.push({ny,nx}); } } return here; } int bfs_2(int y, int x){ dis[y][x] = 1; q2.push({y,x}); pair<int,int> here; while(q2.size()){ here = q2.front(); q2.pop(); for(int i=0;i<4;i++){ int ny = here.first + dy[i]; int nx = here.second + dx[i]; if(ny<0||nx<0||ny>=n||nx>=m) continue; if(dis[ny][nx]>0) continue; if(mapp[ny][nx]=='W') continue; dis[ny][nx] = dis[here.first][here.second] + 1; q2.push({ny,nx}); } } return dis[here.first][here.second]; } int main(){ cin >> n >> m; for(int i=0;i<n;i++){ cin >> a; for(int j=0;j<a.length();j++){ mapp[i][j] = a[j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(mapp[i][j]=='W') continue; if(visited[i][j]) continue; pair<int,int> ret_1 = bfs_1(i,j); int max_dis = bfs_2(ret_1.first, ret_1.second) -1; max_val=max(max_val,max_dis); } } cout << max_val; return 0; }
안녕하세요 강사님, 좋은 강의 제공해주셔서 감사합니다! 저는 프론트엔드 개발자를 희망하여 JS 외 다른 언어 경험은 없는 상태입니다 ㅜ 그래서 다름이 아니라, C++를 JS로 포팅하는 방법 관련해서 질문이 있습니다:) (0주차 + 교안)을 학습하고 주차별로 학습을 하려고 하는데 예를 들어 next_permutation()와 같이 JS에 없는 함수 및 C++에서만 제공되는 문법의 경우, 그때그때 next_permutation() 동작 원리를 찾아보면서 JS로 구현해보는 연습을 병행하는 것이 효율적일까요? 아직 JS에 비해 C++ 및 알고리즘 경험이 많지 않다보니, 학습을 하면서 그 자체를 이해하려고도 하지만 자연스럽게 JS라면? 이라는 생각을 계속 하다보니 진도가 나가지 않는 것 같습니다.. 이렇게 학습하는 것이 맞는지도 조금 의구심이 들어서 혹시 이 부분에 대해서도 강사님의 명쾌한 조언을 듣고 싶습니다! 중복되는 질문이지만, 정리해보면 JS로의 포팅을 중간중간 따라가는 방법과 일단은 JS는 고려하지 않고 C++ 알고리즘 자체를 구현하는 방법을 학습 후, 추후 한꺼번에 JS로 포팅하는 방법 중 권장되는 방식도 궁금합니다:) 좋은 강의 제공해주셔서 감사드립니다.
안녕하세요 큰돌님. 8-F처럼 톱니바퀴나 다이얼을 돌려서 특정한 상태로 만드는 데 필요한 최소 횟수를 구하는 문제를 풀 때 어려운 점이 있습니다. 이런 문제의 풀이는 주로 왼쪽 아니면 위쪽부터 탐색을 진행해 답을 찾습니다. 하지만, 저는 내심 이런 불안감이 듭니다. '만일 최적의 횟수가 맨 위가 아니라, 중간이나 맨 하단에서 다이얼을 돌리는 방법에서 비롯된 거면 어떡하지'. '현재 위치 N에서 다이얼을 맞추지 않고, 그 다음의 위치에 있는 다이얼을 먼저 맞춘 후, 다시 위치 N으로 돌아와서 다이얼을 맞추는 게 최적일 수도 있지 않을까.' 위와 같이 다양한 가능성을 염두하니, 풀이법을 떠올리는 데 어려움이 많습니다. 제가 문제를 접근하는 방식이 어디가 잘못되었는지, 어떻게 고쳐야 하는 지 궁금합니다
저는 물웅덩이가 시작되는 위치를 기준으로 정렬을 한 뒤에 현재 위치를 0으로 잡고 만약 물웅덩이가 시작되는 위치가 현재 위치보다 크다면 현재 위치는 물웅덩이 위치로 한뒤 현재 위치 = 현재 위치 + 널빤지 위치, 만약 현재 위치가 물웅덩이가 시작되는 위치보다 크고 물웅덩이가 끝나는 위치보다 작은 경우 현재 위치 = 현재 위치 + 널빤지 위치. 이런식으로 현재 위치를 갱신해가면서 답을 구했는데 이 접근법은 이 문제에서만 유효한가요? 아래는 자바 코드 입니다. package _5thweek; import java.util.PriorityQueue; import java.util.Scanner; public class Baekjoon1911 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int l = sc.nextInt(); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> { if (a[0] > b[0]) { return 1; } else if (a[0] < b[0]) { return -1; } return 0; }); for (int i = 0; i < n; i++) { int start = sc.nextInt(); int finish = sc.nextInt(); pq.add(new int[]{start, finish}); } int ans = 0; int cur = 0; while (!pq.isEmpty()) { int[] poll = pq.poll(); int start = poll[0]; int end = poll[1]; while (cur < end) { if (cur < start) { cur = start; } ans += 1; cur += l; } } System.out.println(ans); } }
안녕하세요 2636번 치즈 문제 질문 드립니다. https://inf.run/LM71Q 위와같이 행렬을 두개 만들어서 풀었는데 시간 복잡도가 10,000,000을 넘을 것 같진 않은데 자꾸 시간 초과가 뜨는 것 같습니다. 혹시 이 부분에 대해 어떻게 해야할 지 답변 주시면 감사하겠습니다.
안녕하세요 강사님 1-H 문제에 대해서 강사님과 다른 방법으로도 풀어보았는데 ( https://inf.run/L1p8z ) 강사님의 구간합 방법 ( https://inf.run/4mSTg ) 보다 시간이 20ms 가량 높게 나와서 궁금증에 질문드립니다. 구간합의 반복횟수 보다 적게 반복 한 것 같은데, 내부에 분기문과 queue 사용으로 인해 시간이 더 늘어나게 된걸까요? 맞다면 queue의 처리는 O(1)으로 알고 있어서 분기문과 queue 중 처리 속도 증가의 원인을 꼽자면 분기문이 더 큰 비중을 차지하는지도 궁금합니다 퀄리티 높은 강의와 지속적인 피드백 늘 감사드립니다!
학습하는 분들께 도움이 되고, 더 좋은 답변을 드릴 수 있도록 질문전에 다음을 꼭 확인해주세요. 1. 강의 내용과 관련된 질문을 남겨주세요. 2. 인프런의 질문 게시판과 자주 하는 질문(링크)을 먼저 확인해주세요. (자주 하는 질문 링크: https://bit.ly/3fX6ygx) 3. 질문 잘하기 메뉴얼(링크)을 먼저 읽어주세요. (질문 잘하기 메뉴얼 링크: https://bit.ly/2UfeqCG) 질문 시에는 위 내용은 삭제하고 다음 내용을 남겨주세요. ========================================= [질문 템플릿] 1. 강의 내용과 관련된 질문인가요? (예/아니오) 예 2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예/아니오) 예 3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예/아니오) 예 [질문 내용] 여기에 질문 내용을 남겨주세요. 이중연결리스트는 안다루나요?
DP(동적 계획법) 에서는 " '초-기-메-롱' 패턴 이 쓰인다고 하셨는데, 이 패턴은 탑다운 방식에만 적용 가능한 건가요? 그렇다면 바텀업 방식 의 경우, 이 문제를 DP로 판단할 수 있는 기준은 무엇인가요? 예를 들어 아래 두 가지 조건으로 DP 여부를 구분할 수 있을까요? 점화식을 사용한다. 이전 값을 그대로 가져와서 사용한다. 또, dp[i] = dp[i-1] + dp[i-2] 같은 식도 메모이제이션 이라고 볼 수 있나요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 배열의 인덱스를 혹시 for(int i = 0; i < n; i++){ for(int i = 0; i < 5; i++){ arr[i][j] = sc.nextInt(); } } 이렇게 하면 안되는 이유가 있을까요?
일단 제가 틀린 코드인데, #include <bits/stdc++.h> using namespace std; typedef long long ll; int n, a[102]; ll dp[102][102]; // sum은 음수가 되면 안됨. 20을 넘어서도 안됨. ll go(int sum, int cnt) { if (sum < 0 || sum > 20) return 0; if (cnt == n - 1) { if (sum == a[n]) return 1; else return 0; } ll& ret = dp[sum][cnt]; if (ret != -1) return ret; ret = 0; ret += go(sum + a[cnt + 1], cnt + 1); ret += go(sum - a[cnt + 1], cnt + 1); return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; memset(dp, -1, sizeof(dp)); for (int i = 1; i <= n; ++i) { cin >> a[i]; } cout << go(0, 0); } 물론 이 방법이 불필요한 과정이 들어있는 것은 맞지만, 예제도 다 통과했고 결국 같은 과정을 거친다고 생각했는데, 오답이라고 나옵니다. 그래서 a[0]부터 접근하는 코드로 변경했을 때는 정답이라고 나오는데 어떤 차이점인지 잘 모르겠습니다. https://inf.run/hL4B9
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. #include<iostream> #include<algorithm> #include<vector> using namespace std; int n,ret; vector<int> v; stack<int> st; int check(int i,vector<int> &v){ int cnt=0; int mx =0; for(int j = i+1; j<n; j++){ if(v[j]<= v[i]){ if(v[j]>=mx && v[i]>=mx) { cnt++; if(j == i+1) mx = v[j]; else mx = max(mx,v[j]); } else{ break; } } else if(v[j]>v[i]){ cnt++; break; } } return cnt; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i =0; i<n;i++){ int num; cin>>num; v.push_back(num); } for(int i=0;i<n-1;i++){ ret += check(i,v); } cout<<ret; return 0; } 이 코드에서 예제는 통과하지만 틀리는 이유를 잘 모르겠습니다. 처음에는 스택을 하려고 했다가 매번 특정한 위치에 접근하는 것이 스택은 안되기에 무식한 방법으로 풀어보는 시도를 위해 vector를 이용해 보았습니다 (번외 질문 반례는 순수 노가다를 통해서 찾는건가요? 아님 다른 방법이 있을까요?
1. 현재 학습 진도 몇 챕터/몇 강을 수강 중이신가요? 2-6 어떤 알고리즘을 학습하고 계신가요? LinkedList 여기까지 이해하신 내용은 무엇인가요? 어떻게 로직이 흘러가는지 이해가 된 상태 입니다. 2. 어려움을 겪는 부분 어느 부분에서 막히셨나요? 어려운 부분은 아니고 뭔가 제 풀이에 대해서 공유 해드리고 싶습니다! 코드의 어떤 로직이 이해가 안 되시나요? 이해가 안되진 않는 것 같습니다! 어떤 개념이 헷갈리시나요? 없습니다! 3. 시도해보신 내용 문제 해결을 위해 어떤 시도를 해보셨나요? 우선 값들을 StringBuilder 로 만들어서 각각 Int로 파싱한다음 더해주는 과정을 해보았습니다. 에러가 발생했다면 어떤 에러인가요? 없습니다! 현재 작성하신 코드를 공유해주세요 package algorithm_practice.second_week; public class GetLinkedLiistSum_01 { // Node 클래스 정의 static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } // LinkedList 클래스 정의 static class LinkedList { Node head; public LinkedList(int value) { this.head = new Node(value); } public void append(int value) { Node cur = head; while (cur.next != null) { cur = cur.next; } cur.next = new Node(value); } } // 두 연결 리스트의 합을 계산하는 메서드 public static int getLinkedListSum(LinkedList list1, LinkedList list2) { StringBuilder firstNumber = new StringBuilder(); StringBuilder secondNumber = new StringBuilder(); Node cur1 = list1.head; Node cur2 = list2.head; while (cur1 != null && cur2 != null) { firstNumber.append(cur1.data); secondNumber.append(cur2.data); cur1 = cur1.next; cur2 = cur2.next; } int result = Integer.parseInt(firstNumber.toString()) + Integer.parseInt(secondNumber.toString()); return result; } // 메인 실행 테스트 public static void main(String[] args) { LinkedList linkedList1 = new LinkedList(6); linkedList1.append(7); linkedList1.append(8); LinkedList linkedList2 = new LinkedList(3); linkedList2.append(5); linkedList2.append(4); int result = getLinkedListSum(linkedList1, linkedList2); System.out.println("두 연결 리스트의 합: " + result); // 예시: 1032 } } 파이썬 코드를 자바로 변환해서 풀어봤는데 이렇게 접근해도 좋은 풀이 일까요~? 이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
원래 상태로 돌아오기까지 4n번의 횟수가 걸린다는 것은 이해를 했습니다. 그런데 제가 처음에 생각한 종료 조건은 둘 중 하나의 큐라도 비어있게 된다면 합을 같게 만들 수 없는 경우라 생각했습니다. 그런데 시간초과가 발생하네요. 하나의 큐가 원래 상태로 돌아가기 위해서는 그 과정에서 반드시 원소가 하나도 없는 경우가 생길것이라 생각했는데 아닌건가요?
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n, m, left=0; static int[][] boxes; static int[][] directions = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; static Queue<Integer[]> q; public int BFS() { /* 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸 | 모두 익을 때까지의 최소 날짜 nx-1, ny | nx, ny-1 | nx+1, ny | nx, ny+1 */ if (left==0) return 0; int L = 0; while (!q.isEmpty()) { int size = q.size(); for (int i=0; i<size; i++) { Integer[] point = q.poll(); for (int j=0; j<4; j++) { int nx = point[0] + directions[j][0]; int ny = point[1] + directions[j][1]; if (nx>=0 && nx<n && ny>=0 && ny<m && boxes[nx][ny]==0) { left--; boxes[nx][ny] = 1; q.offer(new Integer[]{nx, ny}); } } } L++; } if (left >0) return -1; return L-1; } public static void main(String[] args) { Scanner kb = new Scanner(System.in); m = kb.nextInt(); n = kb.nextInt(); boxes = new int[n][m]; q = new LinkedList<>(); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { boxes[i][j] = kb.nextInt(); if (boxes[i][j]==1) q.offer(new Integer[]{i, j}); if (boxes[i][j]==0) left++; } } Main main = new Main(); System.out.println(main.BFS()); } } 코드는 위와 같이 짰는데 계속 타임 에러가 발생해서 강의를 들었습니다.. 제가 보기엔 강사님이 짜신 거랑 차이를 모르겠는데 제 코드의 어떤 부분이 문제가 됐을까요? =========================== AI 답변 보고 혹시나 싶어서 강사님이 하신대로 Point class 를 따로 만들어서 진행했더니 해결됐습니다..!!!! 배열로 선언한 것과 차이가 있네요
