삼성 기출문제들을 풀면서 이전에 풀었던 실버I 두문제를 풀어보았다. 이전에는 풀지 못하고 답을 참고했던 기억이 나는데, 이번엔 상대적으로 쉽게 풀어서 나름 성장한것을(?) 느꼈다. 연산자 끼워넣기https://www.acmicpc.net/problem/14888 https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해당 문제와 유사한데, 프로그래머스 방식은 굉장히 복잡했던 기억이 있어 다시 풀어봐야겠다. 백준 문제는 수열을 앞에서 부터 순회하며, 4가지 연산에 따라서 모든 경우의 수를 구해서 계산해주면 되..

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방식(0,0)부터 (n-1, n-1)까지 도달한다고 할 때, 모든 경우의 수를 고려하는 것을 어떻게 할까? 가 첫번째 관문이였다.백트래킹을 떠올렸으나, 25 x 25인 경우엔 시간초과가 날 것이기 때문에 제외했다. boolean visited를 사용하여 코드를 짰지만, 당연히 하나의 최단경로만 탐색했다. 문제에서 원하는 것은 모든 경우의 수에서 최소 값이다. 따라서, int visited를 통해서 현재 값들을 배열에 저장해두고, 최소 비용이 갱신되..

https://www.acmicpc.net/problem/14891 접근 방법기존에 4개의 톱니바퀴를 어떤 자료구조로 저장할지 고민하고, 이동시키는게 상대적으로 편한 리스트를 고민했으나 다른 사람들의 풀이를 참고하여 2차원배열이 훨씬 편한것을 확인했다. 시계 방향, 반시계 방향도 생각보다 이동시키기 쉽다. 움직이는 톱니바퀴를 찾고, 해당 톱니바퀴의 왼쪽 및 오른쪽을 순회하며 움직이는 경우엔 현재 방향에서 -1을 곱해주고 아닌 경우엔 멈췄다는 의미이므로 탐색을 중지했다. 4개 톱니바퀴의 이동 방향을 저장해둔 다음에, 시계 방향 및 반시계 방향에 따라서 재배열을 진행하면 되는 문제였다. 코드import java.io.BufferedReader;import java.io.IOException;import ja..

https://www.acmicpc.net/problem/15683 접근 방식시간복잡도 최악의 케이스에는: 4^8 * 8 * 8으로, 1초에 충분히 풀어낼 수 있다. 문제를 풀며 헷갈렸던 것 두가지는, 어떻게 각 cctv 방향 경우의 수 만큼 백트래킹을 돌려주는 것과 board의 값들을 계속해서 업데이트 시켜주는 것이 헷갈렸다. 경우의 수는, 단순히 해당 cctv의 direction 경우의 수를 가져와서 for문을 돌면 해결되었고, 배열 복사같은 경우 문제가 되었다. int[][] tmp = copyBoard(board);public static int[][] copyBoard(int[][] board) { int[][] tmp = new int[n][m]; for(int i = 0; i 기..

https://www.acmicpc.net/problem/21939 접근 방법최근 본 코테와 비슷한 문제였다. 우선순위 큐에 [문제번호, 난이도] 형태로 값을 집어넣고 문제번호나 난이도 조건에 의해 정렬이 되어있다고 가정하자. 만약에, 이 때 무작위의 문제번호를 제거하라고 한다면 어떻게 할 것인가?코테에서도 그렇고, 이 문제를 처음 접근할 때 이 아이디어를 내지 못해서 틀렸다. 다른 사람의 아이디어를 참고하니 우선순위 큐 이외의 `해쉬맵`을 선언하여 접근한 것을 볼 수 있었다. 문제에서 recommend가 1과 -1일 때 각각 조건이 다른데, 어려운 문제를 우선적으로 뽑는 큐와 쉬운 문제를 우선적으로 뽑는 큐가 필요했다. 나는 max_pq, min_pq로 선언해서 각각의 조건에 맞게 세팅을 해주었다. ..

https://www.acmicpc.net/problem/13904 접근 방법public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); PriorityQueue pq = new PriorityQueue((a,b) -> { if (a[0] == b[0]) { return b[1] - a[1]; // 날짜가 같다면 큰 값 ..

인덱스를 쓰는 이유특정 조건을 만족하는 데이터를 빠르게 찾기 위해 일반적으로 Full Text 검색을 하게 되면 O(N)의 시간이 걸리는데, B-tree 기반 인덱스를 사용한다면 O(logN)까지 줄어들게 된다. 복합 인덱스에서 설정을 잘못했다고 가정하자. INDEX(a)라는 테이블이 있고 쿼리는 a = 95 and b = 70 이렇게 있다고 가정할 때, a를 찾는 과정은 이전과 동일하게 O(logN)일 것이다. 하지만, b에는 인덱스가 걸려있지 않기 때문에 테이블을 전체 다 조회해야하고 이 때의 시간복잡도는 O(n)이라 전체 탐색과 다를 것이 없다. 따라서, INDEX(a, b)를 설정해줘야 한다.복합 인덱스에서 column의 정렬 순서는 `a`, 그 다음에 `b` 를 정렬한다. 복합 인덱스 (a,b..

https://www.acmicpc.net/problem/2805 https://www.acmicpc.net/problem/1654 https://www.acmicpc.net/problem/10816 LG CNS 사전 코딩테스트 문제를 가벼운 마음으로 풀었는데, 두번째 문제를 테스트 케이스만 통과하고 전체 히든 케이스는 다 틀렸다. 나의 접근 방법이 아예 틀렸음을 깨닫고 구글링을 해서 유형을 찾아보니 up, lb 문제와 똑같았다. 이번 기회에 다시 복습을 해야겠다고 느꼈다.숫자카드 2해당 문제가 동일한데, 632101010-10-1073 이 문제에서 10의 등장 횟수를 구하려면 어떻게 해야할까? 배열을 순회하며 등장횟수를 계산해줄 수도 있지만, 더 간단하게 풀 수 있다. -10-10233671010..

https://www.acmicpc.net/problem/2295 유형해시이분 탐색 풀이방법int 배열에서 x + y + z = k가 존재할 때, k의 최대값을 찾는 문제다. (단, 인덱스는 중복 가능) 배열을 이중 탐색하며 x + y합을 HashSet에 저장한다. 이 때 배열의 마지막 값은 저장하지 않아도 된다. (정렬이 된 경우에)x + y를 이제 알았으니 k - z를 배열을 순회하며 확인한다. 배열을 이중으로 순회하며 arr[i] - arr[j]를 하게되면 모든 k - z의 순서쌍을 구할 수 있다. 이 때, 해당 값이 set에 존재한다면 k의 최댓값을 갱신해준다. (arr[i]를 통해) 이분 탐색을 통해서도 값을 탐색할 수 있는데 HashSet이 더 로직을 구현하기 편했던것 같다. 코드impor..

https://www.acmicpc.net/problem/18869 알고리즘 분류정렬값 / 좌표 압축 접근 방법처음에, 어떻게 각 우주들의 대소관계를 비교할지 애를 먹었다. 내가 처음에 떠올린 방법은Ai Ai = Aj → Bi = Bj 일 때 배열에 0 저장Ai > Aj → Bi > Bj 일 때 배열에 -1 저장 이런식으로 각 우주의 대소관계를 저장해주려고 했는데 모든 배열을 순회하는데만 O(N^2) * 100이라 시간초과가 발생한다. 문제에서 우주의 개수가 100개이고, 각 우주의 크기가 10,000이기 때문에 시간복잡도를 줄여야 한다. 고민해봐도 답을 떠올리지 못해 GPT한테 물어봤는데 정말 괜찮은 풀이를 알려줬다. [1, 3, 2] 라는 원래 배열이 있다고 가정하자.해쉬맵을 선언하여 [행성, 순서]..