inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

묻고 답해요

176만명의 커뮤니티!! 함께 토론해봐요.

비트마스킹 질문

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 선생님 비트마스킹의 어려움 때문에 복습하고 있는데 1~20 까지 수들의 이진수를 외워 두는게 도움이 될까요???

  • c++
  • 코딩-테스트
안창완 댓글 2 좋아요 0 조회수 75

강의 마지막부분에 질문이 있습니다.

미해결

[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part1: C++ 프로그래밍 입문

안녕하세요 루키스님 강의에 질문이 있어서 글 작성합니다. rsp에 16을 더해주는 이유에 대해서 정확히 이해를 하지 못했습니다. push를 2회 하면서 이미 rsp가 16이 더해진 상태로 있다고 생각을 하고 있는데 왜 또다시 16을 더해준것인지 잘 이해가 안갑니다.

  • c++
여울 댓글 2 좋아요 0 조회수 267

8-B 질문 있습니다.

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

퀘스트를 한개씩 풀며 str, int를 비교하고 가능하면 point를 받아 이를 str과 int에 분배하며 최대한 많이 푸는 문제 이해서 static int go (int STR, int INT) { if(dp[STR][INT] != -1) return dp[STR][INT]; dp[STR][INT] = 0; int point = 0; ArrayList<Integer> list = new ArrayList<>(); for (int i=0; i<n; i++) { if(arr[i][0] <= STR || arr[i][1] <= INT) { if(!visited[i]) { visited[i] = true; for (int j=0; j<=arr[i][2]; j++) { int a = Math.min(1000, STR +j); int b = Math.min(1000, INT+arr[i][2]-j); dp[a][b] = Math.max(dp[a][b], go(a, b)+1); } visited[i] = false; } } } return dp[STR][INT]; } 이렇게 풀어야한다고 생각합니다. 즉 1번 퀘스트가 현재 능력치로 해결 가능하면 1. 방문처리 2. 그 포인트로 str, int에 분배하면서 다시 재귀 2 -1 . 현재 퀘스트를 해결한 것이니 go()재귀 다녀온 결과의 +1 함 3. 방문처리 해제 하지만 이렇게 접근하면 정답이 안되더라구요 왜 이 코드가 불가능한지 궁금합니다. 그래서 강사님 코드가 더더욱 이해가 가지 않습니다. 제가 문제를 잘 못 이해한건가요? 현재 str, int에서 최대한 한번에 해결할 수 있는 것을 모아서 한번에 해결하고 그 포인트를 모아서 분배하는 방법이 이해가 가지 않습니다. 포인트 분배는 마음대로니까 str, int 모두 point 분배를 전혀 안한 경우를 포함한 경우라고 생각하면 될까요? 이해가 가지 않는 코드부분은 for(int i = 0; i < n; i++){ if(a[i].x <= STR || a[i].y <= INT){ ret++; // <-- 요부분과 if(!visited[i]){ visited[i] = true; pnt += a[i].c; // <-- 요부분입니다 v.push_back(i); } } }

  • c++
  • 코딩-테스트
tjd125gns 댓글 1 좋아요 0 조회수 110

4-A 질문 있습니다.

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 선생님 문제를 어떻게 접근해야 되는지 어떤 순서로 로직 작성해야되는지는 떠올랐기 했는데 문제에서 완탐 처럼 nC1, nC2...등등에서 써야 된다 하면 비트 마스킹에서 (1 << n) 요 부분 코드 22번째 줄 if(i & 1 << j) 요걸 사용한다 식으로 외워도 될가요?? 막상 비트마스킹 사용할려고 해도 어떻게 쓸지 떠올리가 않네요 ㅠㅠ dfs,bfs, 스택 등등 공식처럼 금방 떠올라서 사용할 수 있는데 비트마스킹은 뭐랄까 다른 차원에 개념인거처럼 이걸 언제 쓰고 어떻게 응용할지 감이 안잡히네요

  • c++
  • 코딩-테스트
안창완 댓글 2 좋아요 0 조회수 131

배추심기 질문이 있습니다.

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

http://boj.kr/2097fb2384af4c5ebffe94487b5d5a00 메모리 초과가 나느데 이유를 잘 모르겠네요..

  • c++
  • 코딩-테스트
댓글 2 좋아요 0 조회수 117

3-Q 질문

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

http://boj.kr/5cc22e317fde47e8b77e3ffe89d2194a 위와같이 풀어봤는데 효율측면에서 거리가 초과된다면 탐색을 그만하게 했습니다. 강사님 코드와 비교해봤을때 좀 더 효율적이라 할 수 있나요? 아니면 같은 효율일까요?

  • c++
  • 코딩-테스트
송인서 댓글 1 좋아요 0 조회수 91

2-S vector선언 관련 질문 드립니다 :)

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님 🙂 그동안 풀었던 문제들을 마지막으로 점검하고 있는데요, 아무 생각없이 지나갔던 개념이 있더라구요. 그동안 풀었던 그리디 문제를 생각해보면, overflow 방지를 위해 아래처럼 vector의 크기를 미리 N으로 정해두었습니다. cin >> N; vector<pair<int, int>> vec(N); 이렇게 선언한다면, 제가 알기로 vec은 N만큼의 크기를 가지면서, 요소를 채워넣지 않으면 컨테이너 내부에 어떤 값도 존재하지 않는 것으로 알고 있습니다. 아래는 2-S 문제에서 선언된 vector입니다. 이 문제와 더불어, 다익스트라에서 가중치와 도착 지점을 저장해주는 adj vector는 같은 형태를 띄고 있습니다. vector<int> vec[10004]; 이렇게 선언한다면 vec은 배열처럼 10004개의 칸이 생기며, 전역에서 생성할 경우에는 모든 칸이 0으로 초기화되는 것으로 알고 있습니다. 이 형태를 1번으로 변경을 하면서 'DFS함수에 파라미터로 vec을 넣어주면 되겠다'라는 생각으로 접근을 했는데요, 시작하자마자 에러가 발생했습니다. 혹시 vector<int> vec[10004]과 같은 형태는 vector<vector<int>>와 같은 타입인걸까요? 이유가 무엇인지 알고싶습니다..!!

  • c++
  • 코딩-테스트
한유태 댓글 1 좋아요 0 조회수 97

2-J 질문드립니다!

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

우선.. 저는 bfs로 풀었는데 강사님 코드랑 유형을 보니깐 시뮬 구현이었군욥..! http://boj.kr/56216e6ba1ce4b12bbfcbcfa9450293c 우선, 궁금한 건 강사님 코드에선 18번 째 줄 while(a[i][j+1] == -1 )인데 이렇게 되면 j+1에서 오버플로우가 왜 일어나지 않았는지 궁금합니다!

  • c++
  • 코딩-테스트
황경훈 댓글 2 좋아요 0 조회수 138

7-R 아이디어 질문있습니다 :)

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님 🙂 문제풀이에 궁금한 것이 있습니다. 문제를 보자마자 먼저 투포인터를 떠올렸구요, 시간복잡도가 굉장히 크기 때문에 이분탐색을 생각했습니다. 하지만, 이분탐색을 사용하면 배열의 value 또는 인덱스 중 어떤 것도 탐색할 수 없기 때문에 올바른 방법이 아니라고 생각했습니다. 아이디어가 너무 안떠올라서 정답풀이를 보니까 DP더라구요.. 머리가 너무 아픕니다 ㅠㅠ 문제를 풀이하는 방법은 다음과 같습니다. 어떻게 풀어야겠다는 아이디어 아이디어를 어떤 알고리즘을 사용해서 어떻게 풀이해야겠다는 설계 구현 그동안 문제를 풀면서 느낀 점은, 아이디어와 설계만 제대로 되어있다면 구현은 문제가 될 것이 없다는 것이었습니다. 반대로, 아이디어와 설계가 제대로 되어있지 않으면 구현은 해봤자 의미가 없었습니다. 이렇게 아이디어와 설계가 안떠오르는 문제들은 어떻게 극복해야할까요? 선생님의 조언이 절실하게 필요합니다..

  • c++
  • 코딩-테스트
한유태 댓글 2 좋아요 0 조회수 111

7-H 질문있습니다 :)

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님 🙂 한 가지 궁금한 것이 있어서 질문 드립니다 ^^ 입력 값을 int형 변수가 아닌 vector컨테이너를 사용하면 문제가 생기는 경우가 있는데요, 무엇때문에 발생하는 문제인지 모르겠습니다. 아래는 정답의 수도코드입니다. dp[0] = 1; for (int i = 0; i < n; i++) { cin >> temp; for (int j = temp; j <= k; j++) { dp[j] += dp[j - temp]; } } 여기서 안쪽 for문 중 j = 1로 변경하면, 연산 자체는 늘어나겠지만 정답인 것은 변함이 없습니다. 아래는 temp변수를 vector 컨테이너로 변경한 코드입니다. vector<int> vec(n); dp[0] = 1; for (int i = 0; i < n; i++) { cin >> vec[i]; for (int j = vec[i]; j <= k; j++) { dp[j] += dp[j - vec[i]]; } } temp 변수를 이용한 것보다 vector 컨테이너를 사용하기 때문에 공간복잡도와 시간복잡도 측면에서 손해를 보지만, 결과는 같습니다. 하지만, 안쪽 for문의 j를 j = 1로 수정하면 오답이 됩니다. 테스트케이스에서도 출력 값이 다르게 나오더라구요. 이유가 무엇인지 알려주시면 감사하겠습니다 :) http://boj.kr/0cbbe29b33424769a1e8006da134bd7b

  • c++
  • 코딩-테스트
한유태 댓글 2 좋아요 0 조회수 129

3 - G 질문있습니다.

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

강의의 코드 중 25번째 줄 까지는 이해를 했습니다. 그러나 26 - 28번째 줄의 부분에서 이해가 안가는 것이 있습니다. 문제는 최단거리를 바라고 있습니다. 그렇다면 26번째 줄, else if (visited[next] == visited[now] + 1) 에서 visited[next]는 next에 도달한 가장 적은 걸음 수를 뜻합니다. 여기서 제가 이해가 안되는것은 visited[next]가 어떻게 가장 적은 걸음수가 보장 되는지 입니다. visited[now] + 1이 visited[next]보다 작아서 새로운 경로가 더 빠를 수 있는 경우의 수는 신경을 안써도 되는 이유가 무엇인지 궁금합니다. BFS를 사용하면, 가장 먼저 도착한 케이스가 가장 빠른 케이스다 라는 경험과 느낌은 있지만, 이번에는 가중치가 동일하지 않은 상황에서, 특히 뒤로도 갈 수 있는 상황에서 이렇게 생각하고 넘어가기에는 찝찝함이 있어 질문해봅니다.

  • c++
  • 코딩-테스트
비스킷 댓글 2 좋아요 0 조회수 126

6-D vector 초기화 질문있습니다 :)

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님 🙂 테스트케이스가 여러 개인 문제기 때문에 vector를 clear해줬는데요, out of range error가 발생해서 질문 드립니다. 아래 코드의 주석을 살리면 위 에러가 발생합니다. 조언 부탁 드립니다 🙂 http://boj.kr/f9dc05bf7b6e4897a286d9746368c283

  • c++
  • 코딩-테스트
한유태 댓글 2 좋아요 0 조회수 134

강의 마무리가 언제 되나요?

해결됨

C++로 만들면서 배우는 게임 개발과 알고리즘 with Windows API

11월 말까지는 강의 마무리가 가능할까요?

  • c++
  • 게임수학
  • 알고리즘
  • winapi
  • 게임-물리
2juneyong 댓글 2 좋아요 0 조회수 225

강의 리뉴얼 요청!

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

아이패드로 드로잉 하면서 강의 설명해 주실때, 좀 깔끔하게 필기를 해주시던가, 펜 굴기를 적절하게 좀 줄여서 판서 해주세요. 현재강의는 너무 두꺼워서 글에 집중하다 보면 강의 내용이 묻히고, 강의내용에 집중하다보면 판서가 안읽히는 강의가 너무 많습니다.. 판서 리뉴얼 좀 싹 부탁드려요!

  • c++
  • 판서
  • 필기
  • 아이패드
  • 강의수정요청
Chat GPT 댓글 2 좋아요 0 조회수 159

7-M 시간초과 질문입니다.

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

http://boj.kr/77d12fe723574ecc9f5d7a3804c0d7ea 안녕하세요! 선생님과 비슷한 방법으로 푼거같은데 어디가 문제인지 잘 모르겠습니다 ㅠㅠ

  • c++
  • 코딩-테스트
김준 댓글 2 좋아요 0 조회수 139

6-H 맵 관련 질문있습니다 :)

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님 🙂 시간복잡도가 굉장히 타이트해서 이분탐색으로 푸는 문제인 것은 알고 있으나, 테스트 겸 map으로 다시 풀어보다가 이해가 되지 않는 부분이 있어서 질문드립니다. 30번째 줄의 mp[vecA[i]]++; 이 부분때문에 틀리는건데요, mp[vecA[i]] = 1;이라고 하면 맞더라구요. 둘이 연산 차이가 없어보이고, 테스트케이스도 정상적으로 출력이 되는데요, 제가 놓치고 있는 부분이 있을까요? http://boj.kr/076e9301948a40c9afb2262e5e4c26c0

  • c++
  • 코딩-테스트
한유태 댓글 2 좋아요 0 조회수 101

최신화하기

미해결

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

#include <iostream> #include <ctime> using namespace std; struct TM { int tm_year; }; int main() { time_t timer = time(NULL); struct tm* t = localtime(&timer); int yeardb, year = t->tm_year + 1900, age; char Id[20]; cin >> Id; // 주민번호 입력 // 성별 계산 if (Id[7] == '1' || Id[7] == '2') { yeardb = 1900 + ((Id[0]-48) * 10 + (Id[1]-48)); // 특정 문자열의 문자숫자를 숫자로 변환하기 위해서는 '0' 문자0의 아스키 십진수인 48을 뺀다. } else { yeardb = 2000 + ((Id[0]-48) * 10 + (Id[1]-48)); } age = year - yeardb + 1; printf("%d ", age); if (Id[7] == '1' || Id[7] == '3') printf("M\n"); else printf("W\n"); return 0; } 24년 기준 53세

  • c++
  • 코딩-테스트
빠타박스 댓글 1 좋아요 0 조회수 224

5-F 재질문드립니다 :)

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님 🙂 해당 문제 재질문드립니다. 이 글은 아래의 순서로 이루어져있습니다. 문제를 풀이한 내용 이해되지 않는 부분 설명 궁금한 부분이 무엇인지 3 2 1 65 5 23 2 99 10 2 위의 예시는 문제의 2번 테스트케이스인데요, 풀이를 해보면 아래와 같습니다. 무게가 2인 가방에 알맞는 1과 2의 무게를 가지고 있는 요소들의 가치를 pq에 넣어 내림차순 정렬하면 99, 65 순으로 가치가 저장되어, 반복문 안에서 result값에 99를 더하고 빼면 65가 남아있다. 이미 pq에 65가 저장되어있고, 99는 사용되었기 때문에 무게가 10인 가방에 알맞는 크기인 5의 무게를 가지고 있는 요소의 가치인 23을 pq에 저장하여 내림차순하면 65, 23 순으로 정렬되어있고, 1번을 반복하면 result에 65를 더하고 pq에 23이 남아있는채로 마무리된다. 위와 같이 이해했습니다. 정확히 이해한거 같은데요, 이해가 되지 않는 조건이 하나 있습니다. // 한유태 코드 for (; j < N; j++) { if (C[i] >= vec[j].first) pq.push(vec[j].second); } // 선생님 코드 for (; j < N && C[i] >= vec[j].first; j++) { pq.push(vec[j].second); } 디버깅을 해보니, 제 코드는 vec[j].first가 테스트케이스의 1, 2, 5가 나왔구요, 선생님 코드는 1과 5가 나왔습니다. j++이라는 후위증감연산자에 초점을 맞춰서 분석을 해봤는데요, 저는 이거때문에 문제가 생겼다면 1을 제외한 2와 5가 나와야 한다고 생각합니다. 질문은 아래와 같습니다. 어떻게 해서 2가 스킵된 것인지 궁금합니다. 조건문을 for문에 넣지 않고 if문 안에 넣게 되면 어떤 문제가 생기는지 궁금합니다. 테스트케이스는 정답처리가 되어서 오히려 더 헷갈립니다. http://boj.kr/b7ff0aa67f734625837cddfcf08e7abe

  • c++
  • 코딩-테스트
한유태 댓글 2 좋아요 0 조회수 121

3-D 질문있습니다.

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

강의 듣고 나름 반례도 다 처리했다고 생각했는데 2%에서 넘어갈수가 없군요... 제가 어디서 정신줄을 놓았는지 모르겠습니다... 부탁드립니다... http://boj.kr/777d2db6af894cf2a9c3599f9638e7fd

  • c++
  • 코딩-테스트
비스킷 댓글 2 좋아요 0 조회수 99

2-l 질문있습니다.

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

문제를 풀어보았는데 비주얼스튜디오에서는 통과가 되는데 백준에서는 런타임에러가 발생했습니다. 이유를 알고싶습니다. http://boj.kr/e5488fc5d35b4753bd9850e582e2a043

  • c++
  • 코딩-테스트
Steven 댓글 2 좋아요 0 조회수 302

인기 태그

인프런 TOP Writers

주간 인기글