173만명의 커뮤니티!! 함께 토론해봐요.
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌선생님 매번 좋은강의 감사합니다 해당문제 풀이에서 다른부분은 모두 이해 가는데, make함수에서 if(interval == n) break; 부분이 왜 필요한지 잘 모르겠습니다. 어차피 for 루프가 끝나면 자동으로 종료되기때문에 필요없다고 생각하여 제출했는데 틀렸다고 나오네요 혹시 무엇때문에 필요한 것인가요?
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요, 강사님의 강의를 수강하며 코딩테스트를 준비하고 있는 수강생입니다. 강사님의 좋은 코드 설명과 양질의 코드로 항상 감사하게 생각하고 있는데요, 다름이 아니라 제가 5 - B 문제를 풀다가 질문이 생겨서 글을 올리게 되었습니다. 저는 해당 <문자열 폭발> 문제를 읽자마자 '아 여느 괄호 연쇄 폭발 문제랑 비슷하구나' 라는 생각이 들어서 스택으로 문제 풀이 가닥을 잡게 되었는데, 그 와중에 전과는 다르게 폭발하는 string의 길이가 길어 졌으니 매번 탐색을 해주어야겠다, 시간 복잡도도 괜찮을 것 같다! 라는 생각에 코드를 작성해봤습니다. 생각보다 정답 풀이가 저의 풀이와 비슷해서 기분도 좋았는데, 왠지 모르게 시간초과가 계속 발생합니다. <질문> 어느 부분을 고치면 시간 초과를 없앨 수 있을까요? 그리고 이러한 시간 초과를 겪지 않으려면 어떤 코딩 방식을 지향해야할까요? (이건 개인적으로 지금 발생하고 있는 문제가 제 코드 작성 습관과 관련이 있디고 생각해서 적었습니다.) #include<iostream> #include<stack> #include<queue> #include<vector> #include<string> #include<climits> #include<algorithm> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string str; cin >> str; string bomb; cin >> bomb; stack<char> s; int len = str.length(); int bomb_len = bomb.length(); for(int i = 0; i < len; i++) { char now = str[i]; // 폭탄을 확인할 만큼 stack이 큰지 확인 // 폭탄을 넣을 만큼 크지 않다면 그냥 stack에 문자 넣기 if(s.size() >= bomb_len - 1 && now == bomb[bomb_len - 1]) { // 폭탄 글자 길이 만큼 스택에서 글자 우선 뽑기 string token; token = token + now; for(int j = 1; j < bomb_len; j++) { token = token + s.top(); s.pop(); } reverse(token.begin(), token.end()); // 뽑은 문자열이 폭탄 글자인지 확인 // 폭탄이 아니라면 다시 넣어주고 폭탄이면 뺀 문자열 그냥 버림 if(token != bomb) { for(int j = 0; j < bomb_len; j++) { s.push(token[j]); } } } else { s.push(now); } } if(s.empty()) { cout << "FRULA"; } else { string answer; int ans_len = s.size(); for(int i = 0; i < ans_len; i++) { answer = answer + s.top(); s.pop(); } reverse(answer.begin(), answer.end()); cout << answer; } }
미해결
자바 코딩테스트 - it 대기업 유제
import java.io.*; import java.util.*; public class Main { public static int[] dy; public int solution(String s){ int answer = 0; dy= new int[101]; answer = dfs(0,s); return answer; } public static int dfs(int s, String str) { if(dy[s]>0 ) return dy[s]; if(s<str.length() && str.charAt(s)=='0') return 0; if(s==str.length()-1 || s==str.length()) return 1; else { int res = dfs(s+1, str); String num = str.substring(s,s+2); if(Integer.parseInt(num)>26) return 0; //26보다 크면 리턴 else return res += dfs(s+2, str); //그렇지 않다면 재귀 } } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution("25114")); System.out.println(T.solution("23251232")); System.out.println(T.solution("21020132")); System.out.println(T.solution("21350")); System.out.println(T.solution("120225")); System.out.println(T.solution("232012521")); } } 이 코드에서 if(Integer.parseInt(num)>25) return 0 코드랑 if(Integer.parseInt(num)<=26) res+=dfs(s+2, str)랑 차이가 있나요?? num이 25보다 크면 리턴해주고 그렇지 않을때 res+=dfs(s+2, str)해준다는 거랑 다른 의미인가요??
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
Mac 유저일 경우, 초반 컴파일러 설정에서 다음과 같이 에러가 뜰 수 있습니다. 저는 sudo 를 사용해도 에러가 뜨더군요ㅠㅠ 구글링을 좀 하다보니 다음과 같이 해결방법을 찾게 되어 공유드립니다. /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include 이 파일 경로에 bits 디렉토리를 생성하고 똑같이 작성하면 문제없이 잘 작동합니다!
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
강의 매우 유익하게 듣고있는 학생입니다! 많이 부족하지만 열심히 공부하는 중입니다! 2-J문제 풀이에서 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 0) { int cnt = 1; while (a[i][j + 1] == -1) { a[i][j + 1] = cnt++; j++; } } } } 여기서 while문 돌면서 j++을 계속 해주는데 열을 계속 증가시키면서 -1인지 아닌지를 검사해주는데 j < m인 조건을 안걸어주면 j++을 계속하면서 index범위를 침범하지 않나 싶어서 질문 드립니다!
해결됨
2주만에 통과하는 알고리즘 코딩테스트 (2024년)
재귀 안에 answer 변수를 사용하려면 global answer 로 지정 해줘야 하지 않나요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-Q 1344 문제 질문입니다! #include <bits/stdc++.h> using namespace std; double A,B,ret; // 1~18까지 소수가 아닌 수로 배열 선언 int arr[11]={1,4,6,8,9,10,12,14,15,16,18}; int main() { cin >> A >> B; // 2차원 배열을 통해 18 combination n을 구현 for (int i=0;i<11;i++){ for (int j=0;j<11;j++){ double A_com=1,B_com=1; double per=1,A_per=1,B_per=1; //A_com으로 A가 arr[i](소수가 아닌 수만큼) 번 득점했을 때의 경우의 수를 구함 //A_per은 arr[i]만큼 득점했을 확률, 18-arr[i]만큼 득점 못했을 확률을 곱함 for (int k=0;k<arr[i];k++){ A_com*=(18-k); A_com/=(k+1); A_per*=(A/100); } for (int k=0;k<18-arr[i];k++){ A_per*=(100-A)/100; } //B도 마찬가지 for (int k=0;k<arr[j];k++){ B_com*=(18-k); B_com/=(k+1); B_per*=(B/100); } for (int k=0;k<18-arr[j];k++){ B_per*=(100-B)/100; } //A_com*A_per은 A가 arr[i]만큼 득점할 확률 //B_com*B_per은 B가 arr[j]만큼 득점할 확률 //모두 곱하면 A와 B 모두 소수가 아닌 숫자만큼 득점할 확률 per*=A_com*A_per*B_com*B_per; ret+=per; } } // 1-(A와 B모두 소수가 아닌 숫자만큼 득점할 확률)=적어도 한 팀이 소수로 득점할 확룰 printf("%f",1-ret); } 문제 해설과는 다르게 조합을 이용해서 풀었는데 결과가 맞지 않습니다. 예제 1번과 2번은 맞는데 어떤 부분이 잘못되었는지 알려주시면 감사하겠습니다 ㅠㅠ
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
copy의 인자로 v, v+5, ret을 넣는데 원래 copy (InputIterator first, InputIterator last, OutputIterator result) 이렇게 이터레이터가 들어가야 하잖아요 array to pointer decay 때문에 그냥 v를 넣으면 되는 건가요? 포인터로 선언을 시켜주지 않아도 이터레이터가 들어가야 할 자리에 인자로 넣어주면 이런 현상이 일어나는건지 궁금합니다!
미해결
입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]
선생님 안녕하세요 선생님이 새로 강의 여신 이 강의를 다듣고 나면 프로그래머스 레벨 2정도까지는 어느정도 다 풀수 있을까요? 기업 시험을 보게되면 프로그래머스 형식으로 문제를 풀게되서 문의드리게 되었습니다 ㅠ 기존에 올리셨던 파이썬 프로그래머스 문제풀이 강의도 듣고는 있는데 알고리즘에 대한 이론 지식이 부족해서 이강의도 끊게 되었습니다 ㅠ 말씀부탁드립니다!
미해결
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 강사님께서 강의 도중 2차원 문제일 경우 레벨로 푸는게 힘들다고 하신 이유가 궁금합니다. 다른 분들이 숙제검사 맡으신 것처럼 레벨로 푸는 것 역시 배열을 새로 만들어서 값을 저장하기때문에 2차원 문제도 레벨을 통해 거리를 구하고 2차원 배열에 저장하는 방법으로 풀리지 않나요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/78f586fab057402f93621ce7d148e6bb 지도를 입력받을 때 탈출 부분을 벡터에 push_back 하고 사람과 불을 각각 bfs 돌렸습니다. 탈출 부분 벡터를 반복문으로 돌면서 탈출이 가능한 경우 그 시간을 ret 벡터에 넣고 ret의 크기가 0이면 impossible을 출력하고 0이 아니면 정렬하여 맨 앞의 숫자를 출력하도록 했는데 메모리 초과가 뜹니다... ㅠㅠ 왜그럴까요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요. 3 - J 주난의 난 문제를 다음과 같은 방법으로 풀었습니다 2차원 arr 에 입력을 저장하고 상하좌우 bfs 로 탐색을 진행하면서 만약 '1' 이 나올 경우 이를 q2에 저장 만약 '0' 이 나올 경우 계속 bfs 탐색을 진행하고 목표에 도달하지 못하고 탐색을 다 마친경우 q2 에 저장된 '1' 을 전부 '0' 으로 바꿔주고 BFS 탐색을 다시 처음부터 진행 위의 같은 방법으로 진행하였는데 큰돌의 해설을 보니 '0' 이 아닌 경우 '0' 으로 바로 바꾸고 탐색을 마친 후 temp 큐에 있던 좌표를 기반으로 다시 탐색을 진행하게 되는데 저는 '1' 을 마주친 경우 바로 바꾸지 않고 나중에 바꾸고 탐색을 처음부터 다시 진행 큰돌님의 코드는 '1' 을 마주친 경우 바로 바꾸고 탐색을 이어서 진행 으로 해석할 수 있는 걸까요?? 코드의 로직은 동일하나 변경 시점과 탐색 시점이 다른 거다 라고 보면 될까요?? 큐를 2개 써야된다는 큰돌님의 조언만 듣고 바로 문제를 풀어서 정답을 맞았지만 정확히 이해가 됐는지 확인하고자 질문드립니다!! 제 전체 코드는 https://www.acmicpc.net/source/66428450 입니다! 그리고 저는 BFS 를 처음부터 탐색하여 visited 를 계속 초기화 해주었는데 fill(&visited[0][0], &visited[0][0] + N * M, 0); 으로 문제에서 주어지는 N 과 M 크기 만큼만 초기화 하려고 하니 무한루프를 벗어나지 못하는 일이 생겨 fill(&visited[0][0], &visited[0][0] + 301 * 301, 0); 결국 visited 배열의 크기 만큼 초기화를 하는 것으로 바꾸니 정상 동작하였습니다! 저는 처음 코드가 사용한 만큼의 영역에 대해서만 초기화 한다고 생각했지만 그렇지 않은 걸까요??
해결됨
파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
from collections import deque N = int(input()) N_list = list(map(int, input().split())) dq = deque(N_list) current = 0 res = "" left = dq.popleft() right = dq.pop() while len(dq) >= 0: if current > left and current > right: break if len(dq) == 0: if current < left and current < right: if left < right: res = res + 'L' # current = left break elif left > right: res = res + 'R' # current = right break elif left > current > right: res = res + 'L' # current = left break elif right > current > left: res = res + 'R' # current = right break else: if current < left and current < right: if left < right: res = res + 'L' current = left left = dq.popleft() elif left > right: res = res + 'R' current = right right = dq.pop() elif left > current > right: res = res + 'L' current = left left = dq.popleft() elif right > current > left: res = res + 'R' current = right right = dq.pop() print(len(res)) print(res) deque 이용하여 pop(), popleft() 로 left, right 설정하여 분기하면서 찾았는데 실제 코딩테스트에서 이러한 코드도 시간 초과 문제가 발생하지 않을 지 궁금합니다. 강사님 풀이의 경우 while 문 안에 sort()가 계속 돌아가서 시간 이 더 오래 걸릴거 같다고 생각해서 질문드립니다!
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
const solution = (arr, mathScore={}) => { let count = result = 0; arr.forEach((list) => { list.forEach((rank, idx) => { mathScore[rank] = mathScore[rank] ? [...mathScore[rank], idx] : [idx] }); }); for(let i=1;i<=arr[0].length; i++) { for(let j=1;j<=arr[0].length; j++) { count=0 if(i !== j) { for(let k=0;k<arr.length; k++) { mathScore[i][k] > mathScore[j][k] && count++ } } count === arr.length && result++ } } return result }
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
function solution(size, arr) { let answer = [0, 0, 0, 0, 0]; arr.forEach((element) => { if (!answer.includes(element) && answer.length !== size) { answer.unshift(element); } else if (!answer.includes(element) && answer.length === size) { answer.pop(); answer.unshift(element); } else if (answer.includes(element)) { let index = answer.findIndex((el) => el === element); let tmp = answer[index]; answer.splice(index, 1); answer.unshift(tmp); } }); return answer; } forEach안에서 for문을 돌지 않고 짜봤습니다. 좀 코드가 지저분한것 같은데 괜찮은 코드일까요? 감사합니다.
해결됨
2주만에 통과하는 알고리즘 코딩테스트 (2024년)
왜 두 수 사이에 3개 이상은 불가능한지 귀납법으로 어떻게 증명할지를 모르겠어서 질문 남깁니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
https://www.acmicpc.net/source/66347779 문제코드입니다 중간에 시간초과가 나는부분이 find와 substr등의 함수를 이용해 덱에 넣어야하는 넘버를 체크하는데에 시간초과가 발생하는듯 하여 읽어들인 문자열에서 숫자를 카운팅하여 집어넣는식으로 해결하였는데 해당 부분의 find와 stoi, substr등으로 인해 시간초과가 발생하는것이맞을까요?
해결됨
코딩테스트 [ ALL IN ONE ]
안녕하세요! two_sum 문제에 dictionary를 적용 관련하여 문의드리고자합니다. 강의 코드에서는 중복값이 존재 (ex : nums = [4,1,9,7], target = 14])일 때에 대해서는 해결이 되지 않았고, 해당 문제에 대해서는 해결을 하였습니다. 다만 leet code에서는 같은 값이 n번(n>=2) 들어갔을 경우 (ex : nums = [4,1,9,7,7], target = 14])에 대해서도 true를 반환해야할 것으로 보입니다. 파이썬 dictionary의 경우 nums = [4,1,9,7,7]로 dictionary를 생성하게되면 중복값은 key값 생성이 되지 않는 것으로 확인됩니다. 예를들어, memo = {} for index, v in enumerate(nums): memo[v] = index 하게되면, { 4:0, 1:1, 9:2, 7:3, 7:4 }가 아닌 { 4:0, 1:1, 9:2, 7:4 }로 생성되는 것 같습니다. 이렇게 된다면 아래 조건식에서 판단이 어려운데 혹시 dictionary를 무조건 활용한다는 가정하에 가능한 방법(중복 key처리, 중복값에 대한 여부 저장 등(?))이 있을까요? 제가 문제에 대해 정확히 이해한것이 아닐 수 있어 만약 해당 상황에 대한 풀이는 필요하지 않다면 미리 양해말씀드립니다 ㅎㅎ..
미해결
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
코드가 왜 오답인지 잘 모르겠습니다ㅠㅠ import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Block implements Comparable<Block> { int a; int h; int w; public Block(int a, int h, int w) { this.a = a; this.h = h; this.w = w; } @Override public int compareTo(Block o) { return o.a - this.a; } } class Main { static int[] dy; static int[] dis; public int solution(ArrayList<Block> arr, int n) { int answer = 0; Collections.sort(arr); dy[0] = 1; dis[0] = arr.get(0).h; for (int i = 1; i < n; i++) { int max = 0; int max_h = 0; for (int j = i - 1; j >= 0; j--) { if (arr.get(j).w > arr.get(i).w && dy[j] >= max && dis[j] > max_h) { max = dy[j]; max_h = dis[j]; } } dy[i] = max + 1; dis[i] = max_h + arr.get(i).h; answer = Math.max(answer, dis[i]); } return answer; } public static void main(String[] args) { Main T = new Main(); Scanner kb = new Scanner(System.in); int n = kb.nextInt(); ArrayList<Block> arr = new ArrayList<Block>(); dy = new int[n]; dis = new int[n]; for (int i = 0; i < n; i++) { int a = kb.nextInt(); int h = kb.nextInt(); int w = kb.nextInt(); arr.add(new Block(a, h ,w)); } System.out.println(T.solution(arr, n)); } }
미해결
눈떠보니 코딩테스트 전날
퀵정렬 시간복잡도가 최악이 O(nlogn), 베스트가 O(n^2)라고 표기되어 있는데 이게 맞나요?
