안녕하세요 현재 투포인터 알고리즘 강의를 듣고 궁금한 점이 생겨서 질문을 남깁니다. 투포인터 설명을 듣고 그럼 모든 투포인터 알고리즘 문제에서 "start포인터와 end포인터를 양 끝에 위치시켜놓고 시작하는거구나"라고 생각하고 강의에 있지는 않지만 "프로그래머스 - 보석쇼핑" 문제를 풀던 중에 해당 문제는 투포인터 문제임에도 start와 end를 처음 지점부터 동시에 시작하는 방식으로 풀어야만 했습니다. 제가 생각했을 때 start, end를 양 끝점에 두냐, 혹은 시작점에 두개를 모두 위치시키느냐 를 결정짓는 조건이 문제에서 주어지는 값들이 "sort를 하는 것이 의미있냐 없냐"의 여부에 따라 결정된다고 생각했습니다. 문제에서 주어진 값들이 sort하는 것이 의미가 있다면: 양 끝점에 위치 문제에서 주어진 값들이 sort하는 것이 의미가 없다면: 모든 포인터 시작점에 위치 (sort한 후에) 이렇게 생각해도 맞는 것인지 아니면 그냥 문제를 보고 이를 판단해야 하는 것인지 궁금합니다.
아래는 소수 판단 여부를 알려주는 함수입니다! 여기서 if(n%2==0) return 0; 이 부분이 모듈러 연산에 이미 포함되어 있는 내용 아닌가요? (n%2==0) 이 조건도 따로 서술해줘야하는지 궁금합니다. bool check(int n){ if(n<=1) return 0; if(n==2) return 1; if(n%2==0) return 0; <-이건 이미 for (int i =2; i*i <=n; i++){ <-모듈러 연산에 포함되어 있는 것 아닌가요? if (n%i==0) return 0; } return 1; }
https://www.acmicpc.net/source/share/71ef58daaf4144a5bf9ab254f862398a 3-H 숨바꼭질4 문제에서 정점을 방문하면서 방문한 정점을 벡터에 담고 그 벡터를 큐로 넘겨주어서 k에 도착했을때 벡터를 출력하도록 로직을 짰습니다. 하지만 시간초과가 나오는데 원인을 잘 모르겠어서 질문드립니다. 그리고 추가로 c++에서는 벡터나 배열의 일부분을 잘라서 이용하는 로직은 잘 사용하지 않는지 궁금합니다. JS로 알고리즘을 풀때는 splice 나 slice등으로 배열을 자르고 복사하는 방식을 자주 사용했었는데 지금까지 큰돌님의 강의를 들으면서 그 와 같은 방식은 잘 못 본 것 같아서 질문드립니다.
공유 소스 보기 (acmicpc.net) if문이 true인 경우는 (word 가 0이 아님 당연한거 아닌가?) (그리고 and &&) (word&mask==word 둘이 같음) 걸로 봤는데 이런 의미가 아닌가요? word && 이부분을 빼보니까 답이 제대로 안 나오긴 하네요 그러니까 질문은 word &&~ 이 부분이 무슨 의미인지 모르겠네요
큰돌님 안녕하세요? 어쩌다보니 구형 / 신형 교안 섞여서 갖고 있는데 구형교안에는 5-L이 bitmask와 combination 두개의 풀이가 있는것을 보았습니다. 신형으로 넘어오면서 combination풀이는 삭제된 것을 알 수 있었는데, 어떤 의도가 있어서 삭제 하셨을거 같아서 문의 드립니다. 답변 미리 감사합니다. 수강자 드림.
공유 소스 보기 (acmicpc.net) if (index != 'a'-'a' && index != 'n'-'a' && index != 't'-'a' && index != 'i'-'a' && index != 'c'-'a') { ret = max(ret, go(index+1, k, mask)); } ret=max(~)이게 무슨 의미인지 모르겠습니다 ㅠㅠ 어떤 재귀 구조인지 그림을 못 그리겠습니다
http://boj.kr/df8629bfbd4f4bd69ecbbb0fa031719a go 함수를 통해 서로 국경선을 공유하는 영역끼리 1로 표시하고 연결된 컴포넌트 문제로 만들기 dfs 함수를 통해 영역별로 각각 접근하면서 A[r][c] 값 평균화 이 아이디어로 접근했는데 무엇이 잘못된건지 모르겠습니다.. 아예 틀린 생각인가요..??
강사님 안녕하세요!! 이번에 기업 코딩테스트를 보게 되었는데 예상치 못한 문제가 나와 매우 당황했었습니다.... 제가 평소에 풀던 괄호 문제는 대괄호, 중괄호, 소괄호 순서 상관없이 제대로 여는 괄호, 닫는 괄호가 정확하게 되어있다면 문제를 풀 수 있었던 유형이었습니다. ex) { ( [ [ ] ] ) } <-이건 스택으로 풀면 len(stack)==0 이 나와 answer=YES 가 되는 식의 문제였는데.... 이번 코딩테스트에서는 세상에... 여는 괄호, 닫는 괄호가 정확히 되어있는 조건에 + 무조건 대괄호 , 중괄호, 소괄호 이 순서를 유지해야한다는 조건이 있었습니다. 한마디로 ex) { ( [ [ ] ] ) } <- 이건 중괄호가 제일 바깥에 있고 소괄호 안에 대괄호가 있으니 성립하지 않고 [ [ { { ( ) } } ] ] <- 이런 식으로 괄호가 유지되어야만 성립이 되는 문제라고 하더군요..... 결국 코딩테스트 탈락의 고배를 마시게 되었는데... 저 상황이라면 어떤식으로 접근을 해야하는 걸까요? 지원자들의 후기를 들어보니 해쉬 셋으로 풀면 된다고 했지만 그 코드를 어떻게 작성해야할지 몰라 매우 난감한 상황입니다..
선생님이 풀어주신 코드는 한번 더 확인하는 과정을 거쳐서 board의 수만큼 시간 복잡도가 그만큼 더 늘어나는 것 같아서 익지 않은 토마토의 개수를 세어서 그 수만큼 익으면 days를 반환하는 코드를 짰는데 왜 타임에러가 발생하는지 궁금합니다. 제가 놓치고 있는 부분이 무엇일까요?.. package testSection8; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Point{ int x,y; Point(int x, int y){ this.x = x; this.y = y; } } public class Main{ static int n,m,days=0,total=0,cnt; static int[][] board; static int[] dx = {-1,0,1,0}; static int[] dy = {0,1,0,-1}; static Queue<Point> q = new LinkedList<>(); public int BFS(){ while (!q.isEmpty()){ days++; int size = q.size(); for(int i=0; i<size; i++){ Point point = q.poll(); for(int j=0; j<4; j++){ int nx = point.x+dx[j]; int ny = point.y+dy[j]; if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny] == 0){ if(++cnt == total) return days; board[nx][ny] = 1; q.offer(new Point(nx,ny)); } } } } return -1; } public static void main(String[] args) { MainT = new Main(); Scanner sc = new Scanner(System.in); m = sc.nextInt(); n = sc.nextInt(); board = new int[n][m]; for(int i=0; i<n; i++){ for (int j=0; j<m; j++){ board[i][j] = sc.nextInt(); if(board[i][j] == 1) q.offer(new Point(i,j)); else if(board[i][j] == 0) total++; } } System.out.println(T.BFS()); } }
안녕하세요. 해설 코드 중에 질문이 있습니다. go 함수에서 void go(int here, int cnt) { if (cnt > 3 || cnt >= ret) return; if (check()) { ret = min(ret, cnt); return; } for (int i = here; i <= h; i++) { for (int j = 1; j < n; j++) { if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue; visited[i][j] = 1; go(i, cnt + 1); visited[i][j] = 0; } } } for (int j = 1; j < n; j++) j 에 대한 for문을 제 생각에는 n을 포함하지 않아야 한다고 생각합니다. 그렇게 돌리면 정답으로 처리가 되기도 하고요. 그런데 n을 포함하면 N번째 세로선에서 오른쪽으로 이동하는 가로선이 추가될 수 있는건데 실제로 그렇게 추가할 수 없잖아요? 그럼에도 불구하고 n을 포함하여 코드를 실행해도 왜 정답처리 되는건지 궁금증이 생겼습니다. 예를 들어 가능한 반례로써 for문에서 j = n 인 경우 N번째 세로선과 가상의 N+1 번째 세로선 사이에 가로선이 2개만 추가되어도 check에서 true를 반환할 것인데 이런 반례가 존재하는 경우는 전부 가로선을 전혀 추가하지 않아도 되는 경우뿐이라 cnt = 0에서 바로 끝나서 그런게 아닌가 합니다. j 를 n보다 큰 수 까지 가능하게 범위를 설정해서 돌리면 실제로 틀리지는 않고 시간초과만 뜨긴 합니다. 결과적으로 j = n 까지 가능하게 하는것이 답을 계산하는데는 틀리지는 않지만 조금 비효율적이지 않나 싶습니다. 이론적인 실제 범위인 j를 n - 1까지로 설정하면 시간이 33%정도 줄어들기도 하고요. 이부분에 대해 어떻게 생각하시는지 질문드립니다.
