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++; } } } }
선생님이 작성해 주신 조합 코드에서 제가 보기 편하게 임의로 수정했는데 잘 한 건지 궁금합니다. 완전히 같은 코드인가요? (실행 결과는 같습니다.) 아니라면 어떻게 다른지 왜 선생님이 작성해 주신 코드를 사용해야 하는지 가 궁금합니다! http://boj.kr/2e6fe99f57874e4c8932b2f0817c9377 항상 좋은 강의 감사합니다.
안녕하세요. cnt[a]가 어떻게 알파벳의 개수를 출력하는지 이해가 되지 않습니다. 근본적으로 이해가 되지 않아 좌표이동 개념은 제외하고 질문드립니다! for(char a:str) cnt[a]++; 에서 be가 입력되면 b,e가 각각 a로 들어와서 cnt[b]=98 cnt[e]=101 위와 같이 받는 것까지는 알겠는데 cnt[a]++면, 1개씩 증가한다는 연산자인데.. 그럼 99,102가 되는 거 아닌가요..? 어떻게 알파벳의 개수를 출력하는건지 모르겠습니다 감사합니다!
http://boj.kr/946c8f57d8884275ae800627eb01ada3 안녕하세요 강사님. 일단은 이 문제를 보고 이분탐색 방법이 딱히 떠오르지가 않아서 그냥 마음가는대로(?) 풀었습니다. 그런데, 게시판의 반례는 다 맞는 것 같은데 제출하면 바로 틀렸다고 떠서 그냥 잘못 풀었나 보다 하고 강사님 강의를 찾아보니 이진탐색과 그리디 방법 두 가지가 있더라구요! 혹시나 해서 그리디 부분을 보니 제가 그래도 근접은 했구나 생각이 들었는데, 아무리 생각해도 어디가 틀렸는지 정확히 모르겠어가지고 잠이 안옵니다 ㅠㅠ 강사님께서는 HP를 마지막에 +1 하셨는데, 저는 그냥 처음부터 생존하기 위해 필요한 HP 1을 안고 쭉쭉 계산하는 식으로 생각했습니다. 아무래도 이 부분이 틀린것 같다고 생각은 드는데 정확히 왜 틀린건지를 모르겠습니다 ㅠㅠ 한번만 도와주세요 흑흑..
import java.util.Scanner; public class lecture02 { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); String s=scanner.next(); char [] t=s.toCharArray(); String s1=""; System.out.println(); for (int i = 0; i < t.length; i++) { if(Character.isLowerCase(t[i])) { s1+=Character.toUpperCase(t[i]); } else if(Character.isUpperCase(t[i])) { s1+=Character.toLowerCase(t[i]); } } System.out.println(s1); } } 이 코드가 정상적으로 구현한것 같은데 , 채점 사이트에서 컴파일 오류가 아닌 , 오답으로 처리 되고 있어서 어떤 부분이 잘못 된 것인지 궁금합니다 ( 예시 출력이나 몇개의 예시로는 올바르게 출력이 되는것 같아서 질문합니다)
def insert(self, idx, value): new_node = Node(value) if idx == 0: new_node.next = self.head self.head = new_node else: current = self.head for _ in range(idx-1): current = current.next new_node.next = current.next current.next = new_node def remove(self, idx): if idx == 0: self.head = self.head.next # garbage collector가 알아서 처리해준다. else: current = self.head for _ in range(idx-1): current = current.next current.next = current.next.next def insert의 if문에서 self.head.prev=new_node 이렇게 연결지어주지 않아도 괜찮나요? def insert의 else문에서 new_node.prev=current current.next .prev=new_node 이 부분을 추가 안해도 괜찮나요? def remove의 if문에서 garbage collector가 알아서 처리해주신다고 했는데 1->2->3 이렇게 연결되어있고 인덱스 0인 1을 삭제한다고 했을 때 위의 코드대로 하면 head는 2를 가리킨 상태여도 1이랑 2는 아직 연결되어있는데 알아서 삭제가 되나요? 그래서 self.head.prev=None 이 코드를 추가해야된다고 생각했는데 맞을까요? def remove의 else문에서 마찬가지로 current.next .prev=current 문을 추가하지 않아도 괜찮나요?
이 영상 문제풀이에서 def __init__(self, homepage): self.head=self.current=ListNode(val=homepage) 이렇게 초기화를 해주셨는데 self.head=ListNode(val=homepage) self.current=ListNode(val=homepage) 이거와의 차이점이 뭔가요?
안녕하세요. 공부하다가 질문이 있어 글을 쓰게 되었습니다. 3-A 문제에 보면 ' 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. ' 이런 조건이 있는데요. 영상을 보면 무조건 M개를 고르고 M보다 작은 수는 고려하지 않고 코드를 짜셨더라고요. 무조건 M개 일 경우 최단 거리가 나와서 그 외 경우들은 무시하고 코드를 짜도 되는건가요?
선생님 안녕하세요. Reverse가 아닌 다른방법으로 1-D를 풀어봤는데요. 왜 틀렸다고 하는지 모르겠습니다. 로컬에서 제가 생각한 케이스를 넣어봤을 때는 잘 되는데요. 제가 생각하지 못한 케이스가 있는걸까요? http://boj.kr/f4f4371560a5411ba03513a90129c3bd
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 강사님, 안녕하세요!! 본 문제를 저는 bfs로 풀었습니다. 제 풀이를 돌렸을 떄 77%까지 가고 안되는데 무엇 떄문에 안되는 걸까요... http://boj.kr/1afed87142b944609ac3c01867aeaf8d
