끄적끄적

https://school.programmers.co.kr/learn/courses/30/lessons/67257# 1. 입력 문자열 expression으로 부터, 수와 연산자를 파싱해 list에 저장한다. 2. 연산자 우선순위 배열을 하드코딩한다.경우의 수는 3! = 6개로, 순열로 뽑는 것 보다 나은 방법이었다. 3. 재귀로 각 경우의 값을 구한다.nums[i] 와 nums[i+1]를 opers[i]로 연산하여 다시 nums[i]에 집어넣는다.결국엔 opers.size() == 0일 때, nums.get(0)이 최종 연산 값이 된다. 항상 연산자의 개수는 수의 개수 -1임이 보장되므로, 인덱스 처리만 유의하면 오류가 나지 않는다. 4. 모든 값 중 절댓값이 최대인 경우를 출력한다. + StringBu..

https://school.programmers.co.kr/learn/courses/30/lessons/72411 1. orders를 오름차순으로 정렬한다. 2-1. 모든 orders[i] 에 대해, course[j] 개의 원소를 뽑은 수열 (조합)을 도출한다.2-2. 뽑은 수열들을 map에 merge한다.2-3. 동시에, 가장 높은 value를 mapMax로 놓는다. 3. map을 순회하며, value가 mapMax인 key를 list에 넣는다. 4. list를 정렬하고 배열로 바꿔 리턴한다. import java.util.*;class Solution { int O, C, mapMax; Map map = new HashMap(); List total = new ArrayList(); ..

https://school.programmers.co.kr/learn/courses/30/lessons/64065 문자열 파싱 + 누적합 1. 파싱s = "{{2},{2,1},{2,1,3},{2,1,3,4}}" 1-1. {{, }} 제거s = "2},{2,1},{2,1,3},{2,1,3,4" 1-2. },{를 기준으로 split하여 String 배열로 변경s[] = [[2] [2,1], [2,1,3], [2,1,3,4]]* }와 {는 정규식에서 특수 문자로 인식되므로, 이스케이프 처리하기 위해 \\},\\{로 써야 한다. 1-3. ,를 기준으로 split하여 int 배열로 변경 2. 누적합 초기화 문제의 입력은 다음과 같이 size 순서로 주어지지 않는 케이스가 있다."{{4,2,3},{3},{2,3,4..

https://school.programmers.co.kr/learn/courses/30/lessons/92343#그래프 탐색에서의 비트마스킹 문제다. 문제 특성상 완전 탐색 형태를 이뤄야 하며, 백트래킹을 해도 시간초과다.(카카오 공식 해설에서는 백트래킹 풀이를 작성했다고 하는데, 이 역시 최악의 경우엔 시간초과라고 한다.) 핵심은, 탐색이 가능하다면 탐색 순서는 중요하지 않으므로 비트마스킹을 통해 방문한 정점만 기록하여중복 탐색 경우의 수를 없얘는 것이다.e.g. 1 -> 2 -> 3 == 1 -> 3 -> 2  (둘 다 0b111로 기록) 문제를 어렵게 풀고 BaaaaaaaarkingDog님의 코드를 참고해서 다시 한 번 배웠다. 그 차이를 기록하려 한다.https://blog.encrypted.g..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 일반적인 그래프 탐색 문제다. import java.util.*;class Solution { public int[] solution(String[] maps) { List ans = new ArrayList(); int R = maps.length; int C = maps[0].length(); char[][] map = new char[R][C]; boolean[][] vst = new boolean[R][C]; int dr[] = {0,0,-1,1}; int dc[] = {-1,1,0,0}; ..

https://school.programmers.co.kr/learn/courses/30/lessons/77886  1. 모든 "110" 제거주어진 문자열에서 "110"을 모두 추출한다. 111100 과 같이 하나의 "110"을 추출했을 때 나머지가 다시 "110"을 이룰 수 있으므로,StringBuilder을 Stack처럼 활용한다.(괄호 유효성 검사 문제로 빗대면, "11"을 "{"로, 0을 "}"로 놓는다.) 2. 사전 순으로 앞서게 배치?경우의 수를 생각해보면, "110"은 "111"인 부분을 replace할 때만 사전 순으로 앞선다.000 ~ 101인 부분을 대체한다면 사전 순을 늦추기만 한다. 3. 반례2번 논리로만 접근하면 반례가 있다.입력 : 111000오답 : 110100정답 : 1001..

https://school.programmers.co.kr/learn/courses/30/lessons/68646  생전 처음보는 유형이었다. 그리디하게 풀 수 있다. 인접한 풍선을 계속 터트렸을 때, n번째 풍선이 남을 수 있는 경우의 수를 출력하는 문제다.단, 항상 인접한 풍선 중 숫자가 큰 것을 터트려야 하며, [딱 한번 숫자가 작은 것을 터트릴 수 있다.] 배열 사이즈는 최대 100만이므로 완전 탐색은 할 수 없다.그러므로 약간 dp적 사고?를 하려했고 dp[i][2]로 놓아 각각 예외를 사용했을 경우와 안했을 경우의 최적 값으로 놓으려했다. 적용하려 하니 쉽지 않았다.  그래서 사고를 바꿨다. 1. 왼쪽/오른쪽 부터 탐색했을 때 최솟값을 담은 2개의 배열을 초기화한다.e.g. l[3] = (id..

https://school.programmers.co.kr/learn/courses/30/lessons/77486 특별한 알고리즘은 없는 단순 구현문제였다. 각 판매원을 Node로 치환하고 map으로 관리하면 쉬웠다.문제 설명이 엄청 길어서 center라는 루트 노드가 존재함을 놓치지 말아야 한다. import java.util.*;class Node { Node parent; int money = 0; Node(Node parent) { this.parent = parent; }}class Solution { public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount..

https://school.programmers.co.kr/learn/courses/30/lessons/132266 일단 희소그래프 이므로 인접리스트로 구현했다. 풀이 1 - BFS + cost 배열(dp) BFS를 사용하므로, destination에 도착하면 항상 최단 거리임이 보장된다.큐가 비어있는데도 destination에 도착하지 못한다면 -1을 넣는다. 단, BFS만 사용하면 시간초과가 발생하므로노드 at에서 destination까지 가는 비용을 적은 cost[at]이 이미 존재한다면 사용하고 탐색을 마친다. import java.util.*;class Solution { public int[] solution(int n, int[][] roads, int[] sources, int des..

https://school.programmers.co.kr/learn/courses/30/lessons/1619881. DP 점화식 세우기 어떤 수를 사용했는가는 관심사가 아니므로, i번째에 이룰 수 있는 최댓값만 기록 dp[i][0] = i번째가 1 *  sequence[i]일 때 이룰 수 있는 최댓 값dp[i][1] = i번째가 -1 * sequence[i]일 때 이룰 수 있는 최댓 값 2. 최댓 값 산정 방식 dp[i][0] = Math.max(dp[i-1][1], 0) + sequence[i]; dp[i][1] = Math.max(dp[i-1][0], 0) - sequence[i]; i-1 이 음수라면 i번 째 값을 낮추기만 하므로 최댓 값 해에 포함하지 않는다. 3. 출력 dp[dp.length..