안녕하세요, 시간초과가 나서 질문드립니다. http://boj.kr/8e5586c64a774c39bac19c6aa002074f 제 로직은 다음과 같습니다. 2차원 벡터로 사다리를 표현합니다. 다만 각 행열의 값은 0일 경우 이어진 사다리가 없고, 값을 가질 경우 index+1의 value를 가집니다. 즉 (0,0)-(0,1) 사이에 사다리가 있을 경우 (0,0)=2, (0,1)=1을 갖습니다. 뽑을 수 있는 사다리의 조합을 구합니다. 이는 벡터의 현재 값과 다음 값이 모두 0이면 후보군 벡터에 추가합니다. (코드에선 parti입니다.) parti 벡터를 0부터 3까지 조합을 구합니다. 후보군 중 0개, 1개, 2개, 3개 를 뽑는 모든 조합을 구합니다. 조합을 만들 때 연속된 사다리는 피했습니다. 조합이 완성될 경우 check 함수를 호출하여 사다리 타기를 진행합니다. 이런 플로우를 갖고있고, 이렇게 풀 경우 백트래킹도 필요가 없기에 오히려 적은 연산을 할 거라고 생각했습니다. (아니면 비슷하거나) 하지만 시간초과가 발생하기에 질문드립니다. 디버깅을 해보니 조합은 제대로 뽑히고 있습니다. 필요없는 연산은 딱히 없어보이는데 무슨 문제가 있을까요? +) 백트래킹이란 말을 그냥 완전탐색을 진행하되 중간에 답이 나오면 끝내겠다. 혹은 기존의 답보다 깊게 탐색이 진행되는 것을 막겠다. 라는 것으로 이해했는데 이게 맞는건가요? 그렇다면 보통은 다들 그런 식으로 구현할텐데 굳이 백트래킹이란 단어를 쓰는 이유는 뭘까요..? 감사합니다.
public int solution(int n, int m, int arr[]){ int answer =0; int sum=0; int start= 0; int end =start+1; while(start<n-1 && end<n){ if(arr[start]==m) answer++; if(sum<m-arr[start]){ sum += arr[end]; end++; }else if(sum==m-arr[start]){ answer++; sum=0; start++; end=start+1; }else{ sum=0; start++; end=start+1; } } 혹시 sum에 end 값을 더해서 누적 시키고 m(특정 숫자)에서 start 뺀 것과 비교해서 같다면 start를 1 증가시키고 end를 그 다음 위치시키고 크다면 start와 end를 위와 같이 방식으로 증가 시키는 접근 방식은 잘못되었을까요? 제출 결과 케이스에 따라 정답도 있고 오답은 무조건 정답에서 -1 이라 헷갈리네요 ㅠㅠ
// 1. dfs 실행 int answer = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { if(visited[i][j] == false) dfs(i, j); answer++; } } 안녕하세요. dfs문을 호출한 이후에 answer++;를 했을 때는, 주어진 값과 다르게 나오는데, 어떤 부분에서 차이가 있는지 궁금합니다.. 감사합니다!
선생님 소수와 관련된 문제라 에라토스테네스의 체 알고리즘을 이용하여 배열에 미리 소수에 대한 여부를 파악하여 저장해두었습니다. isPrime 함수는 단순히 해당 배열의 값이 true인지 false인지 리턴을 하는것이라, 함수 자체의 의미가 없어지는거 같은 느낌이 들어서요. 실제 코딩테스트에도 이와같이 작성해도 문제가 없을까요? 아니면 함수의 의미에 맞게 함수 내부적으로 연산을 수행해야 할까요? #include <iostream> bool isPrime(int x); int reverse(int x); // 에라토스테네스의 체 알고리즘 static bool primes[100001]; int main() { int N, numInput; scanf_s("%d", &N); // 모두 true로 초기화 for (int i = 0; i < 100001; ++i) primes[i] = 1; // 0과 1은 소수가 아님 primes[0] = primes[1] = false; // 에라토스테네스의 체 알고리즘을 통해 모든 소수 판별 for (int i = 2; i <= std::sqrt(100001); ++i) { if (!primes[i]) continue; primes[i] = true; for (int j = i * 2; j < 100001; j += i) primes[j] = false; } // 나머지 계산 for (int i = 0; i < N; ++i) { scanf_s("%d", &numInput); int reverseNum = reverse(numInput); if (isPrime(reverseNum)) printf("%d ", reverseNum); } } bool isPrime(int x) { return primes[x]; } int reverse(int x) { int num = 0; while (x > 0) { num = num * 10 + x % 10; x /= 10; } return num; }
안녕하세요. 해당 문제의 코드를 다음과 같이 짰는데, 출력하면 항상 0이 출력됩니다. 강의에 나온 부분과 거의 동일한데, 어느 부분에서 오류가 발생하는지 잘 모르겠습니다. 감사합니다. import java.util.*; import java.io.*; class Main { final static int MAX = 50 + 10; static boolean[][] map; static boolean[][] visited; static int W, H; static int[] DirY = {-1, -1, -1, 0, 0, 1, 1, 1}; static int[] DirX = {-1, 0, 1, -1, 1, -1, 0, 1}; public static void dfs(int y, int x) { visited[y][x] = true; for(int i = 0; i < 8; i++) { int newY = y + DirY[i]; int newX = x + DirX[i]; if(map[newY][newX] && visited[newY][newX] == false) { dfs(newY, newX); } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 0. 입출력 while(true) { StringTokenizer st; st = new StringTokenizer(br.readLine()); W = Integer.parseInt(st.nextToken()); H = Integer.parseInt(st.nextToken()); // 마지막 입력 값이 0이면 while 문 빠져나오기 if(W == 0 && H == 0) break; map = new boolean[MAX][MAX]; visited = new boolean[MAX][MAX]; for(int i = 1; i <= H; i++) { st = new StringTokenizer(br.readLine()); for(int j = 1; j <= W; j++) { map[i][j] = (Integer.parseInt(st.nextToken()) == '1') ? true : false; } } int answer = 0; for(int i = 1; i <=H; i++) { for(int j = 1; j <=W; j++) { if(map[i][j] && visited[i][j] == false) { dfs(i, j); answer++; } } } bw.write(String.valueOf(answer)); bw.newLine(); } bw.close(); br.close(); } }
교안을 처음부터 보면 기본 사용법이랑 입출력등이랑이 나오는데 강의는 시작부터 재귀함수부분을 들어가고 있는데 알고리즘교안이랑 강의랑 어떻게 사용하면될까요?? 재귀함수를 파트도 교안에서 보이지않는데 일단은 교안을 보면서 따라 사용해보고 그다음에 재귀함수를 듣고 포인터를 강의랑 교안을 같이사용하면서 듣는게 맞는건가요?
http://boj.kr/de8945ab75c34aa8a4034d0ebe22fc4f 문제를 bfs로도 한번 풀어 보았습니다! 예제는 정확하게 정답이 나왔습니다. 전역변수로 선생님과 같은 배열들의 크기를 잡았는데 제출시 메모리초과가 뜨는 이유는 bfs안에 queue를 만들어서 그런것일까요?? 추가로 시간복잡도는 주어진 문제의 변수에 범위를 보고 내가 쓸 로직과 비교하여 이 로직이 될지 안될지 판단이 어느정도 가능해 졌는데, 문제에서 제공한 제한된 공간복잡도를 만족하는지에 대한 판단은 어떻게 해야 될까요?
안녕하세요! 항상 수업 듣고 예제를 풀이하는 방식으로 공부하고 있습니다. 이번에도 그렇게 풀려고 천천히 문제를 읽었더니 조금 다른 문제인 것 같아서.. 수정 요청 드립니다. 3강의 문제 1번 백준 유사 예제는 2259가 아니라 2559인 것 같습니다. 수정 부탁드립니다!
https://www.acmicpc.net/source/share/36b096b47b1e43518dee34891f9e1897 안녕하세요 큰돌님, 혹시 제 코드도 괜찮은 코드인지 여쭤드립니다, 다름이 아니라, 여기까지 오면서 그동안 visited를 쓸때 2차원 배열로 했었는데, 이번 영상에서는 1차원 배열을 써서, 저는 배운데로 일단 저만의 방식으로 코드를 짜긴했는데, 혹시 효율성이나 1차원 배열로 한 이유를 설명해주시면 감사합니다 ㅎㅎ
안녕하세요 강사님. 질문이 있어 글 남깁니다. DFS로 문제를 풀이하는 과정에서 DFS의 종료 조건이 없어 단지 하나를 다 탐색하고 DFS내의 For 문이 한 번 더 그냥 도는 거로 보이는데 이렇게 For Loop가 한 번 더 의미 없이 안돌게 하려면 어떻게 해야 할까요??
선생님께서 추가적으로 답변해주신 것을 늦게 확인하였습니다. 아마 선생님께서도 제가 추가로 답변한 것을 확인하시지 못하신 것 같아서 추가로 커뮤니티에 질문드립니다. 선생님이 추가로 답변해주신 마지막 답변에서 "idx 0인 경우를 포함하지 않는 경우는 체크하지 않게 되기 때문"이라는 부분을 읽고 깨우친 것 같습니다. 완전탐색과 백트래킹을 사용하는 경우의 차이를 알게 된 것 같습니다. 제가 이해하기로는 완전탐색 -> 해당 상황마다 이 경우를 포함하는지 안하는지를 전부 따져가며 경우를 모두 구함 백트래킹 -> 한 지점이 고정이고 그 지점부터 목적지까지 가는 모든 경로 or 전체 중 몇가지를 고르는 문제와 같이 "무조건 첫번째(경로 문제에서는 첫 지점 고정, 몇가지를 고르는 경우 문제에서는 무조건 처음 한가지를 고르고 다음 순서로 넘어가는 것)를 포함"하는 상황 이런 상황별로 완전탐색과 백트래킹을 푸는 경우가 나뉘는 걸로 이해되었는데 맞을까요? 답변 주신 후에 이 글은 이전 질문과 이어지는 것이기 때문에 삭제하겠습니다!
닫는 괄호를 만날 때마다 count++를 해주는 방식은 왜 정답이 안나오는 지 알 수 있을까요? import java.util.Scanner; import java.util.Stack; public class Main { public static int solution(String str){ int answer = 0; char[] strTochars = str.toCharArray(); Stack<Character> stack = new Stack<>(); int count = 0; for (int i=0; i<strTochars.length; i++) { if (strTochars[i] == '(') stack.push('('); else { if (!stack.isEmpty() && stack.peek() == '(') { stack.pop(); count ++; if (i>0 && strTochars[i-1] != '(') { // 막대 answer += count; count = 0; } } } } return answer; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); System.out.println(solution(str)); } }
실패 http://boj.kr/07dc01c4e7c2492580934f84b3f2c8af 성공 http://boj.kr/6d68ec80a15341a09987a0a32f32fc8f deque 하나만 써서 풀었습니다. BFS로 탐색하면서 빈공간이면 push_front, 친구를 만나서 멈춰야하면 push_back을 했고 각각 visit값을 동결, +1 해줬습니다. 그리고 목표지점에 도착했을 때 끝냈습니다. 실패한 코드와 성공한 코드의 차이점은 하나 입니다. 시작지점의 visit값을 0으로 뒀는가 (미방문은 모두 0) 아니면 1로 두고 시작했는가 (첫 시작점의 visit을 1로 둔 것) 둘 다 결과는 잘 나옵니다 (예제가 적어서 테스트할 게 적지만 bfs로 탐색하는거 따라가보면 제대로 작동합니다.) 하지만 시작지점의 visit을 0으로 뒀을 때는 귀신같이 시간초과가 나게 됩니다..; 개인적으론 이런 알 수 없는(?) 시간초과나 메모리초과 때문에 백준이 너무너무 싫은데요 ㅠ 혹시 이것도 제가 생각못한 다른 이유가 있어서 시간초과가 뜬건지.. 궁금합니다. cin,cout 입출력 동기화는 쓰지 않았습니다만 인간적으로 그런걸로 정답/오답이 갈리는건 문제가 문제있다고 생각됩니다 (화가 나서 그런거 맞습니다 흑흑)
