173만명의 커뮤니티!! 함께 토론해봐요.
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
선생님 제가 정말 많은 반례를 넣어봤는데 다 실행이 되지만 백준에서 실행시켜보면 2%에서 실패됩니다. 반례 찾아주시면 정말 감사하겠습니다! http://boj.kr/06c2448042e64476b47b0a2dd5c7eeb0
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌님, 제가 작성한 코드가 큰돌님의 예시 답안 코드와 로직이 거의 비슷하다고 느끼는데 제 코드는 백준에서 패스가 안되서 한번 의견을 구하고자 합니다. 혹시 왜 accept이 안되는지 이유가 보이시면 답변 부탁드립니다~! #include<bits/stdc++.h> using namespace std; int tc, n, m, k, a, b, ny, nx, cnt; int cabbage[51][51], visited[51][51]; const int dy[4] = {-1, 0, 1, 0}; const int dx[4] = {0, 1, 0, -1}; void dfs(int y, int x){ visited[y][x] = 1; for(int i=0; i<4; i++){ ny = y + dy[i]; nx = x + dx[i]; if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue; if(visited[ny][nx] == 1) continue; if(cabbage[ny][nx] == 0) continue; dfs(ny, nx); } return; } int main(){ cin.tie(NULL); cout.tie(NULL); //tc 개수 받기 cin >> tc; for(int e=0; e<tc; e++){ // n, m, k 받기 cin >> n >> m >> k; // 초기화 cnt = 0; fill(&cabbage[0][0], &cabbage[n-1][m], 0); fill(&visited[0][0], &visited[n-1][m], 0); // 배추의 위치 입력 for(int i =0; i<k; i++){ cin >> a >> b; cabbage[b][a] = 1; } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(cabbage[i][j] == 1 && visited[i][j]==0){ dfs(i,j); cnt++; } } } cout << cnt << "\n"; } return 0; }
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌님 bfs로 최단거리를 탐색하여 문제를 풀어 보았습니다. q에서 뺄때, 방문처리를 할때는 맞는데, https://www.acmicpc.net/source/61392099 q에 넣을때 방문처리를 할때는 틀립니다. https://www.acmicpc.net/source/61392143 최단거리라 q에 넣을때 바로 방문처리를 해줘서 더 높은 cnt일때 방문한 값이 다시 큐에 들어갈일이 없도록 하는것이 맞는것 같은데, 어떤 경우에서 틀린지 모르겠습니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌님! 벡터에 trace를 저장하여 k에 도달하면 trace를 출력하는 방식으로 풀었습니다. 벡터의 push_back()은 시간 복잡도 O(1)으로 알고 있습니다. 때문에 왜 시간 초과가 나는지 궁금합니다! https://www.acmicpc.net/source/61394001
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/75cc76adfce24cbd88595ea4ea999a5d 안녕하세요 강사님 ㅎㅎ 해당 강의 초반에 무식하게 풀었을 때의 시간복잡도가 (n * n-1 / 2) *n 이라고 설명하시는데 제가 혼자 문제풀 때는 다르게 계산을 했거든요... 저는 연속된 수들의 곱이니까 이중 for문으로 for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ 식의 연산이 필요하다 생각했고 여기다가 백트래킹으로 == 0일때 break 정도하는 조건까지만 넣었습니다. 이러면 등차수열의 합 정도의 시간복잡도가 되니 O(n^2)이고 n의 최대범위가 10000 -> 제곱은 1억 -> 1억에서 천만까지는 해볼만하다고 알려주셔서 위 생각의 흐름대로 문제를 풀었습니다. 혹시 제가 시간복잡도 계산을 잘못한건가요..?
미해결
입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]
강의에서 실무에서는 10~20개의 연결리스트만하기때문에 해시의 O(1)을 갖는다고 하셨는데, 면접에서 물어볼경우는 O(n) 이라고 답하는게 맞을까요 O(1)이라고 하는게 맞을까요? 실무에서는 제한을 두지만 여기서는 그런 제한을 두고 물어볼거라는 의도가 있을까? 해서요
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
재귀함수로 순열을 구현해서 돌려보면 312 다음에 321이 나와야 맞는데 321 뒤에 312 가 나오는 현상이 있습니다. 전에 선생님께서 주신 코드도 같은 현상이 나오는데 어떻게 해야할까요 ㅠㅠ
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요! 8-I 나무심기 해설 코드를 보다 작은 의문점이 생겨서 질문드립니다! 바로 중복된 좌표에 나무를 심는 경우인데요. 나무의 개수를 저장하는 부분인 update(treeCnt, num, 1)에서 좌표가 중복되는 경우에는 1이 아니라 나무의 개수로 갱신되어야 하지 않나하는 궁금증이 생겨버렸습니다. 중복되는 경우, 나무를 뽑고 다시 심는 개념으로 이해해야 하는 걸까요? 제가 아직 펜윅트리를 완벽하게 익힌 것이 아니라...많이 헷갈립니다! #include<iostream> #include<vector> using namespace std; typedef long long ll; int N; vector<ll> t; vector<ll> tcnt; vector<ll> treeSum; vector<ll> treeCnt; ll answer = 0; void update(vector<ll> &tree, int i, int diff) { while(i < tree.size()) { tree[i] += diff; i += (i & -i); } } ll sum(vector<ll> &tree, int i) { ll r = 0; while(i > 0) { r += tree[i]; i -= (i & -i); } return r; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; t = vector<ll>(N + 1, 0); tcnt = vector<ll>(200004, 0); treeSum = vector<ll>(200004, 0); treeCnt = vector<ll>(200004, 0); for(int i = 1; i <= N; i++) { ll num; cin >> num; num++; t[i] = num; tcnt[num]++; if (i != 1) { ll l, r; ll value; l = sum(treeCnt, t[i] - 1) * t[i] - sum(treeSum, t[i] - 1); r = (sum(treeSum, 200004) - sum(treeSum, t[i])) - (sum(treeCnt, 200004) - sum(treeCnt, t[i])) * t[i]; value = l + r; if (answer == 0) answer = 1; answer = ((answer % 1000000007) * (value % 1000000007)) % 1000000007; } update(treeSum, num, num); update(treeCnt, num, 1); } cout << answer << "\n"; return 0; }
해결됨
코딩테스트 [ ALL IN ONE ]
안녕하세요! 좋은 컨텐츠 감사합니다. [질문] 14:15에 등장하는 class LinkedList가 왜 object를 상속하나요? 없어도 되지 않을까 하는데, 무슨 이유가 있는 것인지 궁금합니다. class Node는 상속없이 작성되었기에, 그 차이가 더욱 궁금합니다. 감사합니다.
미해결
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
안녕하세요. 수업중 질문사항이있어서 문의드립니다. '5. K번째 큰 수' 강의 중 설명 부분에 대하여 의문점이 들었습니다. 문제 설명 부분에 '만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.' 라는 설명이 있는데, k번째로 큰값은 71로 수정되어야 할것같습니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 멘토님 안녕하십니까? string()이게 생소해서 질문 드립니다. 아래는 멘토님이 짜신 정답 코드 일부인데요 string quard(int y, int x, int size){ if(size == 1) return string(1, a[y][x]); char b = a[y][x]; string ret = ""; for(int i = y; i < y + size; i++){ for(int j = x; j < x + size; j++){ if(b != a[i][j]){ ret += '('; ret += quard(y, x, size / 2); ret += quard(y, x + size / 2, size / 2); ret += quard(y + size / 2, x, size / 2); ret += quard(y + size / 2, x + size / 2, size / 2); ret += ')'; return ret; } } } return string(1, a[y][x]); } 2번째 줄과 마지막 줄에 string()를 써서 1또는 0을 return한다고 강의에서 말씀하셨는데, string이 함수로 쓴다는건 처음알아서 생소해서 그런지 이해가 안갑니다. 부가 설명을 해주실 수 있을까요? 또, 구글링으로 "c++ string()"정도로만 검색해도 자료가 잘 안나오던데, 제가 직접 찾아보려면 msdn? 어디서 찾아보면 좋을 지 조언 받을 수 있을까요?
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
function solution (str) { let strArr = str.split(""); let length = strArr.length; let answer = ''; answer = length/2 !== Math.round(length/2) ? strArr[Math.round(length/2)-1] : strArr[length/2 -1] + strArr[length/2]; return answer; } console.log(solution("good"));
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요! split() 함수를 알려주신 로직대로 짰는데 시간 초과가 뜹니다. 왜 그런건지 알 수 있을까요? http://boj.kr/7c52cc03df5842a487e17a1b18df29fb 항상 좋은 강의해주셔서 감사합니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/f62ec3c209234df98988f6cc6d37ddee 선생님 안녕하세요 위 코드가 제 코드입니다. 다름이 아니라 제 코드는 예제입력 4 실행시 두번째 인구이동에서 (1,2)->(2,2)->(2,1)이 되어야하는데 코드가 (2,2)에서 dfs를 타고 (2,1)로 넘어가지를 않습니다. 혹시 이유를 알려주시면 정말 감사하겠습니다!!
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
https://www.acmicpc.net/source/share/a683363852be4b508750d3f3382be974 안녕하세요 강사님! 강사님 풀이에서 X의 최댓값이 10억이니까 hi를 10억으로 놓는다는게 잘 이해가 가지 않습니다 ㅜ 제가 갖고있는 의문점은 '게임을 10억판보다 더 해야 Z가 변하는 case도 있지 않을까?'인데 혹시 X의 최댓값이 10억인 경우 10억 판(승리) 안으로 z가 무조건 변한다는 것이 증명이 되는건가요?
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
로 보는 건 그런가 보다 싶은데 왜 질투심으로 보석을 나눠야 하는지 이해가 안 갑니다
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
어느 부분에서 틀렸는지 잘 모르겠습니다. 제가 놓친 부분이 강의에서 INF로 초기화하는 거라고 생각해서 보고 수정했었지만 똑같았습니다. 그래서 원래 썼던 코드로 공유합니다. http://boj.kr/b143a73e068a49a9b8687b692265b563
미해결
파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
#my sol def DFS(x,y): global cnt if x>7 or y>7: return if x==7 and y==7: cnt+=1 else: for i in range(4): nx=x+dx[i] ny=y+dy[i] if maze[nx][ny]==0: maze[nx][nx]=1 DFS(nx,ny) maze[nx][nx]=0 if __name__=='__main__': maze = [list(map(int, input().split())) for _ in range(7)] maze.insert(0,[1]*7) maze.append([1]*7) for row in maze: row.insert(0,1) row.append(1) cnt=0 dx=[-1,0,1,0] dy=[0,1,0,-1] maze[1][1]=1 DFS(1,1) print(cnt) #solution dx=[-1,0,1,0] dy=[0,1,0,-1] def DFS(x,y): global cnt if x==6 and y==6: cnt+=1 else: for i in range(4): nx=x+dx[i] ny=y+dy[i] if 0<=nx<=6 and 0<=ny<=6 and maze[nx][ny]==0: maze[nx][nx]=1 DFS(nx,ny) maze[nx][nx]=0 if __name__=='__main__': maze = [list(map(int, input().split())) for _ in range(7)] cnt=0 maze[0][0]=1 DFS(0,0) print(cnt) 위의 코드는 강의 듣기 전에 혼자 작성한 코드이고, 아래는 강의에서 알려주신 코드입니다. 두 코드가 접근 방식이 같은 것은 알고 있습니다. 그런데 제 컴퓨터에서 두 코드 모두 채점 프로그램을 돌렸을 때 결과 계산을 하지 못 합니다.(5초짜리로 해도 같고, 코드에 setrecursionlimit 추가해도 같음) import sys sys.setrecursionlimit(10**6) 그리고 pdf 예제조차도 RecursionError: maximum recursion depth exceeded in comparison 에러가 납니다.(예제는 setrecursionlimit 추가 시 파이썬이 응답을 멈춰서 강제 종료됨) 혹시 제가 발견하지 못 한 코드 상의 문제가 있는 것인지、 제 컴퓨터 사양 때문인지 궁금합니다。
해결됨
Do it! 알고리즘 코딩테스트 with JAVA
저자 선생님 안녕하세요 좋은 교재와 강의 잘 보고 있습니다. 강의가 없는 1016번 문제에 대해 오래동안 고민을 해도 해결이 안되어 질문을 드리고 싶은데, 받아주시면 정말 감사하겠습니다. 시간초과가 난 전체 코드입니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { InputStreamReader is = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(is); StringTokenizer st = new StringTokenizer(br.readLine()," "); long min = Long.parseLong(st.nextToken()); long max = Long.parseLong(st.nextToken()); // 최댓값과 최솟값의 차이만큼 배열 선언하기 boolean[] Check = new boolean[(int)(max-min+1)]; // 2의 제곱수인 4부터 Max보다 작거나 같은 값까지 반복하기 /* 저자님 코드(정답) for(long i=2; i*i<=max; i++){ long pow = i*i; //제곱수 long start_index = min/pow;//최솟값/제곱수 if(min%pow!=0){ start_index++; } for(long j = start_index; pow*j <=max; j++){//제곱수를 true로 변경하기 Check[(int)((j*pow)-min)] = true; } } */ //제 코드(시간초과) for(long i=2; i*i<=max; i++){ long pow = i*i;//제곱수 for(long j=1; (j*pow)<=max; j++){ long t= j*pow;//제곱수의 배수 if((min<=t) && (t<=max)){//제곱수의 배수가 min과 max 범위 안이면 Check[(int)(t-min)] = true; //제곱수의 배수 표시 } } } // long count = 0; for(long i = 0; i<=max-min; i++){ if(!Check[(int)i]){ count++; } } System.out.println(count); } } 위의 전체 코드에서 저자 선생님 코드를 주석 /* */ 로 감싸고 제 코드를 바로 아래에 작성했는데, 보시기 힘들 것 같아서 보라색과 초록색으로 구분한 스크린샷을 같이 올려드립니다. 제 코드의 경우, 백준 문제에서 보여준 테스트케이스는 통과하는데 시간초과가 발생했습니다. 그래서 많은 테스트케이스를 시도해봤는데 입력 1000000000000 1000001000000 이 테스트케이스에서 저자 선생님 코드는 제대로 작동을 하고, 제 코드는 시간초과가 발생하는 것 같았습니다. 하루종일 고민해도 그 이유가 도저히 이해가 안돼서, 질문을 드리고 싶습니다. 가르쳐주시면 정말 감사하겠습니다. 읽어주셔서 감사합니다. +오후 8시에 질문을 추가드립니다. 시간초과가 안나는 핵심 로직이 long start_index = min/pow;//최솟값/제곱수 if(min%pow!=0){ start_index++; } 같은데 이 부분이 이해가 너무 어렵습니다.. 이 코드를 더 자세하게 가르쳐주시면 감사하겠습니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/c486a4712da546db8d98b08c3e5084f4 제 코드중에 a배열을 int로 하였더니 예제출력이 9가나와서 오답입니다. 동일한코드에서 int a배열을 char배열로 바꿧더니 정답이 8이됩니다. int만 char로 바꾸었는데 정답이 바뀔수 있나요? 제가 알기로는 int a[]하고 a에 'W'를 집어넣거나 a[ny]=='W' 동일하다고 알고있는데 제가 잘못알고잇던것같습니다. char a 배열로 선언후 cin>>a[i][j]를 하면 따닥따닥입력도 한글자씩 입력되는지 int a 배열로 했을때 왜 맞왜틀인지 궁금합니다.
