묻고 답해요
141만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
[2468번] segmentation fault
// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; // 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. // 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. ////입력 : // 1. 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N (N은 2 이상 100 이하의 정수) // 2. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. // 3. 높이는 1이상 100 이하의 정수이다. ////출력 : //첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다. int n; int arr[100][100]; int visited[100][100]; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; priority_queue<int> safeAreas; void dfs(int y, int x, int height){ //방문처리 visited[y][x] = true; //4방향 탐색 for(int i=0; i<4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; //탐색 x 조건 if( y < 0 || x < 0 || y >= n || x >= n ) continue; // out of bound if( visited[ny][nx] ) continue; if( arr[ny][nx] <= height ) continue; //물에 잠긴 지역 // 방문 dfs(ny,nx,height); } } // find connected graphs int getSafeAreaCnt(int height){ memset(visited, 0, sizeof(visited)); int connected = 0; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(!visited[j][i] && arr[j][i] > height ){// 방문하지 않았고, safe area dfs(j,i, height); connected++; } } } return connected; } int main() { //입력 cin >> n; string input; int maxHeight=0; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin >> arr[j][i]; maxHeight = max( maxHeight , arr[j][i] ); // 1. 높이의 max 값을 구한다. } } for(int height=0; height <= maxHeight; height++){ safeAreas.push( getSafeAreaCnt( height ) ); } cout << safeAreas.top() << '\n'; } https://www.acmicpc.net/problem/2468안녕하세요 큰돌님. segmentation fault 나는데 어디서 나는지 잘 모르겠습니다 ㅠ priority queue 때문인 거 같은데 한 번 더 확인 해보겠습니다.
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
투포인터스 알고리즘으로 푸는 방법이 제가 이해한게 맞을까요?
제가 이해한 걸로는 두개의 포인터 변수를 이용하여서 반복문을 하나를 가지고 문제를 푸는거라고 이해를 해서 아래와 같이 하나의 반복문으로 풀려고 노력했는데 해당 알고리즘이 제가 이해한 이론이 맞나요? function solution(arr1, arr2) { let answer = []; let sorArr1 = arr1.sort((a, b) => a - b); let sortArr2 = arr2.sort((a, b) => a - b); let n = sorArr1.length; let m = sortArr2.length; let p1 = (p2 = 0); while (p1 < n) { if (sorArr1[p1] === sortArr2[p2]) { answer.push(sorArr1[p1]); } p2++; if (p2 === m - 1) { p1++; p2 = 0; } } return answer; } console.log(solution([1, 3, 9, 5, 2], [3, 2, 5, 7, 8]));정답은 잘 나옵니다만... 핵심이 두개의 포인터 변수와 하나의 반복문만 사용한다 라고 기억 할려고 하는데 이게 맞을지...
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
시간초과
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 큰돌쌤! 현재 알고리즘을 공부하고 있는 학생입니다. 이 문제에서 ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL) '\n' 을 쓰지 않으면 시간초과가 나던데 이런거에 집중하는 거보다 이런 아이디어만 챙겨가면 되겠죠...? 몇몇 문제들이 이런 경우가 있던데 어떻게 공부하면 좋을지 조언을 받으려 게시판에 올립니다!
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
concat과 sort로 풀었는데 맞는지 모르겠네요
function solution(arr1, arr2) { let answer = ""; return arr1.concat(arr2).sort((a, b) => a - b); } console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-I 17071번 숨바꼭질 5 질문있습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 큰돌님,3-I 해설을 보다가 이해가 안가는것이 있어 질문드립니다.수빈이가 3초에 도착하고 동생이 5초에 도착하면 +1,-1 로 만날수 있다 하셨는데해당 코드에서 어떻게 구현된건지 이해가 안갑니다.turn이 시간이고 홀수짝수로 visited에 도착한 시간을 나누는데 turn이 3이면 visited[1][수빈이 위치]에 저장이 되고 nx==b에 의해 바로 break 걸려 출력이 되는것 아닌가요...?이해가 안가 횡설수설 죄송합니다.
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
코드리뷰 부탁드립니다
<html> <head> <meta charset="UTF-8" /> <title>출력결과</title> </head> <body> <script> function solution(board, moves) { let answer = 0; let stack = []; for (let j = 0; j < moves.length; j++) { stack.push(board[moves[j] - 1].pop()); if (stack[stack.length - 1] === 0) { stack.pop(); } if ( stack.length >= 2 && stack[stack.length - 1] === stack[stack.length - 2] ) { stack.pop(); stack.pop(); answer += 2; } } return answer; } let a = [ [0, 0, 0, 0, 0], [0, 0, 1, 0, 3], [0, 2, 5, 0, 1], [4, 2, 4, 4, 2], [3, 5, 1, 3, 1], ]; let b = [1, 5, 3, 5, 1, 2, 1, 4]; console.log(solution(a, b)); </script> </body> </html>
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-J 다른 풀이 방법 질문드립니다.
제가 처음에 접근했던 방법은 옷의 개수가 3가지라면 3C0 + 3C1 + 3C2 + 3C3으로 입을 수 있는 모든 경우의 수를 구한 후, 같은 종류의 옷을 입은 경우의 수를 구해 빼는 방식이였는데void combi(int start, vector b){ if(b.size() == k){ print(b); return; } for(int i = start + 1; i < n; i++){ b.push_back(i); combi(i, b); b.pop_back(); } return; }이 함수를 사용해서 map<string,string>mp을 선언하고 옷의 이름과 종류 모두 입력 받아서 같은 종류의 옷을 입은 경우를 판별하여 구할 수는 없는지 여쭤보고 싶습니다.
-
해결됨코딩테스트 [ ALL IN ONE ]
제약조건으로 시간 복잡도를 구하는 방법..
안녕하세요. 코테 제약조건으로 시간 복잡도 계산하는 부분을 듣고 있는데요.10^4에 n^2을 넣으면 10^8이 된다고 하셨는데 제가 예체능 수포자여서 이 계산 방법이 잘 이해가 안됩니다. ㅠㅋ용어가 맞는지 모르겠지만... BigO로 표기했을 때의 시간 복잡도의 지수와 제한 사항으로 주어진 지수끼리의 곱이 시간 초과 때문에 8이 넘으면 안된다고 이해하면 되는건가요? 이렇게 구하는 게 맞는지...그리고 제약 조건에서 n을 구할 때 연산자 사이에 있는 조건이 n이 되는 것이고 그 n이 1이 되는지, n^2이 되는지에 따라 시간 복잡도를 따지는 건가요?시간 복잡도를 중첩 반복문으로 계산하는 정도만 공부를 해서 잘 이해가 안됩니다. ㅠㅠ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6 - F
http://boj.kr/798b9379c3254770abccef965fd8ee87몬스터 때리는 부분을 제외하면 작성해주신 정답 코드랑 유사해보이는데 어디가 잘못됐는지 잘 모르겠습니다.
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-H 질문있습니다
if(isVowel(idx)) mcnt++, scnt = 0, is_include_v = 1;else scnt++, mcnt = 0;if(mcnt == 3 || scnt == 3) flag = 1;이 부분이 제가 이해하고 있는 것이 맞는지 궁금합니다.예제 입력에 ptoui를 예를 들어보겠습니다.for문에서 ptoui라는 문자열을 알파벳 하나하나 받아주면서p -> vcnt++, lcnt = 0 => vcnt = 1, lcnt = 0t -> vcnt++, lcnt = 0 => vcnt = 2, lcnt = 0o -> lcnt++, vcnt = 0 => vcnt = 0, lcnt = 1u -> lcnt++, vcnt = 0 => vcnt = 0, lcnt = 2i -> lcnt++, vcnt = 0 => vcnt = 0, lcnt = 3 다음 if문에서 lcnt == 3이므로 flag = 1이 되고,flag = 1일 때는 not acceptable 출력.이게 맞나요???
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
배열 대신 벡터 사용 해도 괜찮나요?
int cnt[26]; 대신에 vector <int> answer (26); 를 사용했는데어떤 문제 이든지 배열 대신 벡터를 사용 했을 때 문제될 여지가 있을까요?
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-F 질문입니다.
http://boj.kr/ffa390ab1d0145a8a863f6733fdf21f0k가 주어졌을 때, a n t i c은 무조건 배워야하니까 21개 중 k-5개를 뽑는 경우의 수에서 기저사례에서 최댓값을 갱신하는 방법으로 코드를 짰는데요..제 코드 시간 복잡도를 계산해보면 21C(k-5)*50*15로 계산했습니다(50은 단어의 최대개수,15는 k의 최대 범위). 궁금한 점은 1.저의 코드의 시간복잡도 계산을 저렇게 하는게 맞는지 2. 왜 시간초과가 나는지 모르겠습니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
강의교재126 int형 우선순위큐
while(pq.size()){ cout << pq.top() << " : " << pq2.top() << " : " << pq3.top() << '\n'; pq.pop(); pq2.pop(); pq3.pop(); } 이코드에서 궁금한것이 있는데요 pq.size()는 5이고 참이니깐 while문 안에있는 조건은 계속 돌아가서 무한루프가 되는게 아닌가요?그리고 코드마지막에 있는 pq.pop(); pq2.pop(); pq3.pop(); 는 왜 한번씩 더 써주는건가요? 위에 있는 코드로도 충분하지 않나요?
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
공주 구하기 문제 풀이 시간 복잡도 질문
안녕하세요 제가 푼 코드와 강의의 풀이가 차이가 있어서 질문 드립니다. 저는 아래와 같이 문제를 풀어 봤는데요. 강의와 제 풀이의 시간 복잡도가 어떻게 되는건지 궁금합니다. 제 풀이는 while문이 하나 있으니 O(n)으로 표시하면 되는 것일까요? 강의 풀이는 while문 안에 for문이 있는데 그럼 O(n^2) 인건가요? 아니면 K를 상수로 보고 O(n) 이라고 생각하면 되는 걸까요.. public int solution(int n, int k) { int answer = 0; Queue<Integer> queue = new LinkedList<>(); for (int i = 1; i <= n; i++) { queue.add(i); } int cnt = 1; while (queue.size() > 0) { if (cnt == k) { answer = queue.poll(); cnt = 1; } else { queue.add(queue.poll()); cnt++; } } return answer; } 두 코드 중 어떤 것이 더 효율적인 코드인지 궁금합니다. 실행 시간을 비교해서 더 짧게 나오는 것이 효율적인 코드라고 봐도 되는 걸까요?
-
해결됨코딩테스트 [ ALL IN ONE ]
강의 교재 부탁드려요
안녕하세요. 강의 너무 잘 보고 있습니다.교재 공유 요청 했는데 확인 한번 부탁드리겠습니다~!구글폼에 접수한 메일에는 아무것도 안와있어서요.
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
바둑이 승차 질문입니다!
package other.study; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import static java.lang.Integer.MIN_VALUE; import static java.lang.Math.max; import static java.lang.System.in; // todo: 해결 필요!! public class Main3 { static int[] ch = new int[100000000]; static int c, n, answer = MIN_VALUE; public static void main(String[] args) { Scanner kb = new Scanner(in); c = kb.nextInt(); n = kb.nextInt(); ch = new int[n]; int[] arr = new int[n + 1]; for (int i = 0; i < n; i++) { arr[i] = kb.nextInt(); } // DFS(0, 0, arr); BFS(0, arr); System.out.println("answer = " + answer); } static void DFS(int L, int sum, int[] arr) { if (sum > c) return; if (L == n) { answer = max(answer, sum); } else { DFS(L + 1, sum + arr[L], arr); DFS(L + 1, sum, arr); } } static void BFS(int L, int[] arr) { Queue<Node> Q = new LinkedList<>(); Q.offer(new Node(0, arr[0])); while (!Q.isEmpty()) { int len = Q.size(); for (int i = 0; i < len; i++) { Node tmp = Q.poll(); if (tmp.weight > c) continue; if (L == n) { answer = max(answer, tmp.weight); } else { Q.offer(new Node(tmp.level + 1, tmp.weight + arr[tmp.level + 1])); Q.offer(new Node(tmp.level + 1, tmp.weight)); } } System.out.println(); L++; } } static class Node { private int level, weight; public Node(int level, int weight) { this.level = level; this.weight = weight; } } }안녕하세요 선생님!명품 강의 정말 잘 듣고 있어요! 바둑이 승차를 BFS로도 풀어봤는데, 문제되는 부분이 있을까해서 질문 드립니다! 늦었지만 새해 복 많이 받으세요!
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
코드의 시간 복잡도에 대해 궁금합니다!
function solution(str, t) { let answer; const counts = {}; const formatted = [...str]; formatted.forEach((char, i) => { if (counts[char]) { return counts[char].push(i); } counts[char] = []; counts[char].push(i); }); const tIndexs = counts[t]; answer = formatted.reduce((store, cur, i) => { const tmp = []; tIndexs.forEach((index) => { tmp.push(Math.abs(index - i)); }); store.push(Math.min(...tmp)); return store; }, []); return answer.join(' '); } let str = 'teachermode'; console.log(solution(str, 'e')); 입력값의 크기 N마다 tIndex만큼 반복하니까 O(N^2) 인지아니면 O(N)의 시간복잡도를 갖는지 궁금합니다.
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
쇠막대기 풀이 질문
안녕하세요, 첫번째 else 문에서 바로 pop을 해줘도 오류가 나지 않는 이유, 두번째 if문에서 stack.isEmpty() 체크를 해주지 않는 이유가 무조건 처음 한번은 '(' 괄호가 들어가기 때문인가요? for (int i = 0; i < arr.length; i++) { if (arr[i] == '(') stack.push(arr[i]); else { stack.pop(); if (arr[i - 1] == '(') answer += stack.size(); else answer++; } } import java.util.*; public class Main { public int solution(String str) { int answer = 0; Stack<Character> stack = new Stack<>(); char[] arr = str.toCharArray(); for (int i = 0; i < arr.length; i++) { if (arr[i] == '(') stack.push(arr[i]); else { stack.pop(); if (arr[i - 1] == '(') answer += stack.size(); else answer++; } } return answer; } public static void main(String[] args) throws Exception { Main T = new Main(); Scanner kb = new Scanner(System.in); String str = kb.next(); System.out.println(T.solution(str)); } }
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
코드 리뷰
안녕하세요 강의 듣기 전에 혼자서 풀어보았는데 다음 코드도 가능할까요 ?function solution(s, arr) { let answer = Array.from({ length: s }, () => 0); for (let i = 0; i < arr.length; i++) { let p = answer.indexOf(arr); if (p > -1) { let tmp = arr[i]; for (let j = p; j > 0; j--) { answer[j] = answer[j - 1]; } answer[0] = tmp; } else { for (let j = answer.length - 1; j >= 0; j--) { if (answer[j] === 0 || j === answer.length - 1) continue; let tmp = answer[j]; answer[j + 1] = tmp; } answer[0] = arr[i]; } } return answer; }
-
해결됨SQL 코딩테스트를 위한 마지막 걸음
lag, leag 강의에서 game-play-analysis-iv 문제
https://leetcode.com/problems/game-play-analysis-iv/ 이 문제를 풀고 있는데,제가 작성한 코드는 SELECT ROUND(COUNT(player_id) /(SELECT COUNT(DISTINCT player_id) FROM Activity),2) as fractionFROM( SELECT player_id, LAG(player_id) OVER (ORDER BY player_id) AS prev_id, LAG(event_date) OVER (ORDER BY player_id) AS prev_date, event_date, RANK() OVER (PARTITION BY player_id ORDER bY event_date) AS rnk FROM Activity) AWHERE rnk = 2AND DATE_ADD(prev_date, INTERVAL 1 day) = event_date AND player_id = prev_id입니다. 이 코드로 정답을 체크해 보았을 때 wrong answer라 뜨지만, A FROM절 안에서 event_date, rnk의 순서를 LAG 앞으로 바꾸어 주었을 땐 정답 처리가 되었습니다. 왜 그런걸까요??아래는 순서를 바꿨을 때 정답처리 되었던 코드 입니다.SELECT ROUND(COUNT(player_id) /(SELECT COUNT(DISTINCT player_id) FROM Activity),2) as fractionFROM(SELECT player_id, event_date, RANK() OVER (PARTITION BY player_id ORDER bY event_date) AS rnk, LAG(player_id) OVER (ORDER BY player_id) AS prev_id, LAG(event_date) OVER (ORDER BY player_id) AS prev_dateFROM Activity) AWHERE rnk = 2AND DATE_ADD(prev_date, INTERVAL 1 day) = event_date AND player_id = prev_id
