묻고 답해요
130만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
12번 멘토링 질문입니다!
안녕하세요, 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(); } }
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-N 시간 복잡도 질문이 있습니다.
문제링크: 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의 정사각형을 그릴 수 있다는걸 알기 때문에요.그럼에도 불구하고 큰돌님은 위 상황을 인지한 상태에서 백트래킹으로 시도를 해보신건가요? 아니면 이게 백트래킹으로 풀린다는걸 아시고 푸신건가요?
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
10. 미로탐색 (DFS)
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; // 백트래킹: 이전 상태로 돌아감 } } } } } }이 코드가 항상 정답값의 두배가 나오는데 어느 로직이 잘못된건지 모르겠습니다ㅠ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-J 질문
http://boj.kr/63da4f35132841e68fcc5d77ff53fc60말씀해주신 풀이법이랑 좀 다르게 풀었는데,이렇게 하면 왜 오류가 발생하는지 알수있을까요?? 그리고 제 코드에서 org(입력된 원본 배열)를 별도로 만들어 최소visited처리하는데 사용했는데,혹시 이거보다 좀 더 효율적으로 하는 방법 이 있다면 알려주시면 감사하겠습니다!!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2 - B 문제 질문있습니다
해당문제를 푸는데 강사님과 같은 방법으로 풀어나가고 있습니다만, 계속 12% 대에서 실패가 뜹니다. 조건문이 문제인가 싶어 dfs함수에 들어가기 전 조건문 세개 중 두, 세번째를 강의 내용처럼 합쳐보기도 하고, 문제를 잘못읽었나 싶어 map의 범위를 50 50 에서 51 * 51로도 해보고 전역변수 선언에 문제가 있나 싶어 변경도 해봤지만 해결이 안되네요. <http://boj.kr/85c9f690f6c64294a29406a816169cc0>
-
미해결Do it! 알고리즘 코딩테스트 with JAVA
LCA 빠르게 구하기 Java 코드 시간초과
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++; } } } }
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
"조합"코드를 임의로 수정했는데 확인해 보고 싶습니다.
선생님이 작성해 주신 조합 코드에서 제가 보기 편하게 임의로 수정했는데 잘 한 건지 궁금합니다.완전히 같은 코드인가요? (실행 결과는 같습니다.)아니라면 어떻게 다른지왜 선생님이 작성해 주신 코드를 사용해야 하는지 가 궁금합니다!http://boj.kr/2e6fe99f57874e4c8932b2f0817c9377항상 좋은 강의 감사합니다.
-
해결됨코딩테스트 [ ALL IN ONE ]
오픈카카오톡 비밀번호
노션에 오픈카톡이 있던데 비밀번호가 있더라고요 혹시 입장코드 알수있을까요?
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
for(char a:str) cnt[a]++가 어떻게 알파뱃의 개수를 출력하는건가요?
안녕하세요. cnt[a]가 어떻게 알파벳의 개수를 출력하는지 이해가 되지 않습니다. 근본적으로 이해가 되지 않아 좌표이동 개념은 제외하고 질문드립니다! for(char a:str) cnt[a]++; 에서be가 입력되면 b,e가 각각 a로 들어와서 cnt[b]=98cnt[e]=101위와 같이 받는 것까지는 알겠는데 cnt[a]++면, 1개씩 증가한다는 연산자인데.. 그럼 99,102가 되는 거 아닌가요..?어떻게 알파벳의 개수를 출력하는건지 모르겠습니다 감사합니다!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6-F 그리디 질문입니다.
http://boj.kr/946c8f57d8884275ae800627eb01ada3 안녕하세요 강사님.일단은 이 문제를 보고 이분탐색 방법이 딱히 떠오르지가 않아서그냥 마음가는대로(?) 풀었습니다. 그런데, 게시판의 반례는 다 맞는 것 같은데제출하면 바로 틀렸다고 떠서그냥 잘못 풀었나 보다 하고 강사님 강의를 찾아보니 이진탐색과 그리디 방법 두 가지가 있더라구요!혹시나 해서 그리디 부분을 보니 제가 그래도 근접은 했구나 생각이 들었는데, 아무리 생각해도 어디가 틀렸는지 정확히 모르겠어가지고 잠이 안옵니다 ㅠㅠ 강사님께서는 HP를 마지막에 +1 하셨는데,저는 그냥 처음부터 생존하기 위해 필요한 HP 1을 안고 쭉쭉 계산하는 식으로 생각했습니다. 아무래도 이 부분이 틀린것 같다고 생각은 드는데 정확히 왜 틀린건지를 모르겠습니다 ㅠㅠ 한번만 도와주세요 흑흑..
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-C 질문
안녕하세요 선생님복습하면서 코드를 다시 짜보았습니다. 코드를 다 짜고 분명 맞는 코드라고 생각 되는 코드가 있는데 왜 안되는지 알 수 있을까요?? http://boj.kr/bb19d1d7a24e4a63ae40d2df911dbb51 답변 미리 감사드립니다!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
질문드립니다!
http://boj.kr/9c2c43aa11a1499e9dca2322e2ed5c55큰돌님 풀이를 보지 않고 이런식으로 구현을 해보았는데, public TC는 다 맞는데 어느 부분에서 틀린지 잘 모르겠습니다! 제가 미처 구현하지 못한 부분이 있을까요?
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
안녕하세요
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); } }이 코드가 정상적으로 구현한것 같은데 , 채점 사이트에서 컴파일 오류가 아닌 , 오답으로 처리 되고 있어서 어떤 부분이 잘못 된 것인지 궁금합니다 ( 예시 출력이나 몇개의 예시로는 올바르게 출력이 되는것 같아서 질문합니다)
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
5강 재귀 2번 요리사 문제
안녕하세요, 강의 전에 풀었을 때 다음과 같은 코드를 작성했는데 정답 인덱스가 비어있게 나오네요.혹시 왜 이런건지 알 수 있을까요? 강의자료에 있는 pop을 이용하는 방법은 이해했습니다.먼저 결과창입니다. 6 100 70 90 10 30 55 10 8 100 60 10 10 2 70 10 80 50 0 50 40 30 30 8 60 60 10 70 2 120 20 70 50 4 4 [1, 2, 3, 4, 5] [] [] [] [5] [3, 4, 5] [2, 3, 4, 5] [] [] 134 []코드입니다.n=int(input()) std= list(map(int, input().split())) ing=[list(map(int, input().split())) for _ in range(n)] price=1e9 tmp_best=[] best=[] def dfs(idx,a,b,c,d,p,check): global best global tmp_best global price if idx==n: if a>=std[0] and b>=std[1] and c>=std[2] and d>=std[3] : if p<price: price=p best=tmp_best.copy() print(best) tmp_best=[] else: tmp_best=[] return if check==1: tmp_best.append(idx) dfs(idx+1,a+ing[idx][0], b+ing[idx][1], c+ing[idx][2], d+ing[idx][3],p+ing[idx][4],1) dfs(idx+1,a,b,c,d,p,0) dfs(0,0,0,0,0,0,0) print(price, best)
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
shift, splice연산
안녕하세요shift 연산을 사용하면 원소값들이 한칸씩 다 당겨진다고 알고 있는데 맞나요??만약에 맞다면 N이 클경우는 원형큐같이 직접구현해서 사용하는게 시간복잡도상 더 좋은 코드일까요?
-
해결됨코딩테스트 [ ALL IN ONE ]
디스코드 Doubly LinkedList 구현 코드 관련 질문
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.nextdef 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 문을 추가하지 않아도 괜찮나요?
-
해결됨코딩테스트 [ ALL IN ONE ]
초기화할때 질문
이 영상 문제풀이에서 def __init__(self, homepage): self.head=self.current=ListNode(val=homepage) 이렇게 초기화를 해주셨는데 self.head=ListNode(val=homepage) self.current=ListNode(val=homepage) 이거와의 차이점이 뭔가요?
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-F 백준 런타임에러
안녕하세요 선생님dev에서 출력까지 모두 확인하고 백준에 제출하였는데 런타임에러(Segfault)가 뜨네요. 왜 그런건지 알수있을까요??http://boj.kr/909703751c8045c0af6d239464b65482
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-A 문제 질문있습니다
안녕하세요. 공부하다가 질문이 있어 글을 쓰게 되었습니다.3-A 문제에 보면' 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. ' 이런 조건이 있는데요.영상을 보면 무조건 M개를 고르고 M보다 작은 수는 고려하지 않고 코드를 짜셨더라고요. 무조건 M개 일 경우 최단 거리가 나와서 그 외 경우들은 무시하고 코드를 짜도 되는건가요?
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-D 다른방법으로 풀어봤는데 왜 틀렸는지 모르겠습니다.
선생님 안녕하세요.Reverse가 아닌 다른방법으로 1-D를 풀어봤는데요.왜 틀렸다고 하는지 모르겠습니다. 로컬에서 제가 생각한 케이스를 넣어봤을 때는 잘 되는데요.제가 생각하지 못한 케이스가 있는걸까요?http://boj.kr/f4f4371560a5411ba03513a90129c3bd