dfs

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS + 이분 탐색 필요 자료구조 - (문자열, 점수 저장하는 리스트) 저장하는 HashMap - DFS로 info가 포함될 수 있는 모든 경우의 수를 HashMap으로 만들어 map에 key로 넣고 점수를 value의 리스트의 값으로 넣어준다. - query를 key로 하는 value들을 가져와 이분 탐색한다. → 그래야 시간초과가 안 난다고 함 HashMap을 사용하는 이유 : 한 번에 바로 탐색하기 위해 💥 유의사항 - 시간 초과 주의 - 이분 탐색 전 HashMap의 val..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS 먼저, 문자열 expression을 숫자와 연산자로 나눠 각각 배열에 저장한다. - 숫자인 경우, 숫자를 나타내는 임시 문자열에 하나씩 값을 붙여둔다. - 연산자인 경우, 여태까지 구한 임시 문자열을 숫자로 변환해 숫자 리스트에 저장하고, 임시 문자열을 초기화한다. 그리고 연산자 리스트에도 현재 연산자를 추가한다. + 반복문이 끝나면 마지막으로 만들어진 문자도 따로 삽입해주는 것을 잊지 말자,, static List numList = new LinkedList(); // 숫자..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS 1. 각 손님이 주문한 단품메뉴들을 오름차순으로 정렬한다. (여기서 향상형 for문으로 orders 원소 값 받고 오름차순한 결과 저장하려다가 틀렸다....) for(int i = 0 ; i < orders.length ; i++) { char[] ch = orders[i].toCharArray(); Arrays.sort(ch); orders[i] = String.valueOf(ch); // 정렬 결과 저장 } 2. 각 주문을 기준으로 course 배열의 단품메뉴들의 갯수 길..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS (백트래킹) 필요 자료구조 - 1차원 int형 정답 배열 lion - 점수 차이가 최대일 때 라이언이 쏜 화살 수를 저장하는 1차원 int형 배열 arrows 백트래킹으로 n개를 뽑는 조합을 생성해 화살을 어디에 얼마나 맞추는지 구할 수 있다. 그런데 이 때 n = 10일 때 시간초과가 나므로, 백트래킹 메서드의 반복문에 가지치기(특정 조건 추가)해줘야 한다! 여기서 특정 조건은 과녁 i에 라이언이 임의의 점수에서 어피치에게 점수를 따내기 전까지 (arrows[i]

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • BFS / DFS 1. 입력받은 1차원 String형 배열을 2차원 int형 배열 grid에 값을 저장한다. - 'X'를 입력받은 경우, -1로 값을 설정한다. - 숫자를 입력받은 경우, 숫자를 저장한다. grid[i][j] = maps[i].charAt(j) - '0'; 2. 완전탐색을 통해 2차원 배열 grid를 돌며 방문한 적 없고, X가 아닌 칸 (=-1이 아닌 칸)에 대해 탐색을 수행하며 머물 수 있는 날짜의 수를 구하고, 이 수들을 리스트에 저장한다. 3. 만약 머물 수 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DFS 격자 위의 모든 점을 탐색하며 방문하지 않은 점에서 dfs를 실행한다. - 해당 칸에서 4방향 탐색을 통해 블럭을 이루고 있는 칸 수(currBlockNum)를 계산한다. - 계산한 블럭을 이루는 칸 수가 4개 이상이라면, 터지는 블럭 수(bombCnt)에 1을 더한다. - 그리고 현재 계산한 블럭을 이루는 칸 수와 여태껏 최대 블럭 크기를 비교해 최대 블럭 크기를 둘 중 더 큰 값으로 갱신한다. 💥 유의사항 격자에서 다음 방향으로 이동할 수 있는 조건 1) 격자 범위 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DFS (0, 0)에서부터 DFS 탐색을 시작한다. 해당 위치의 아래, 오른쪽 방향을 탐색하며 1) 격자 범위를 벗어나지 않고, 2) 방문한 적 없고, 3) 뱀이 없다면 해당 위치로 이동한다. (N -1, M -1) 위치를 방문한 적 없다면 0을, 방문하였다면 1을 출력하도록 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ..

📖 문제  1325번: 효율적인 해킹첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한www.acmicpc.net  💡  풀이 방식• BFS. 입력값을 입력받아 어떤 컴퓨터에게 해킹 당할 수 있는지 담는다. (A[a].add(b)). 각 노드마다 BFS를 수행해 노드별 해킹 컴퓨터 수를 저장한다. ⇒  a 노드를 탐색 시, a 노드가 아닌 a와 연결된 각 노드의 카운트를 올린다. (int형 카운트 배열 활용)   💥 유의사항시간 초과 주의   🔺 코드1234567891011121314151617181920212223242526272..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DFS 높이를 k를 1부터 100까지 설정해 찾아보며 안전 지대를 탐색한다. 높이가 k일 때, 해당 칸의 값이 k보다 크고, 방문한 적 없어야만 해당 칸을 DFS로 방문할 수 있다. 해당 NxM 배열에서 총 DFS 수행 횟수 = 안전 지대 수이며, 이 값을 최대 영역 수와 비교한다. 이 때 기존 최대 영역 수보다 더 크다면, 최대 영역 수를 현재 안전 지대 수로 변경하고, 높이의 값도 저장한다. 💥 유의사항 최대 영역 수를 초기화 할 때 0보다 더 작은 값으로 설정해야 한다. ..