알고리즘 문제풀이
1.[LeetCode] 31. Next Permutation
아래와 같은 기존의 next_permutation 알고리즘을 이용하되 마지막 순열에서 넘어갈 때 조건 설정을 추가해주었다.
2.[LeetCode] 33. Search in Rotated Sorted Array
기본적인 방식은 Binary Search 방식을 사용하되 mid = (left+right)/2 인덱스 기준으로 왼쪽 혹은 오른쪽은 완전히 정렬되어 있다는 점을 이용하여 분기문을 달리하여 풀이하였다.
3.[LeetCode] 34. Find First and Last Position of Element in Sorted Array
기본적인 방식은 Binary Search 방식을 사용하되 Target을 찾았을 경우에 범위를 찾기 위한 추가적인 Binary Search를 진행해주었다.
4.[LeetCode] 39. Combination Sum
Back Tracking을 이용하여 풀이하였다. 직관적으로 candidates들을 하나씩 방문하며 각각 N번씩 더해주고 다음 인덱스로 넘어가는 방식으로 index == candidates.length일 때를 기저 조건으로 두고 모든 경우를 판별하였다.
5.[LeetCode] 46. Permutations
Permutation을 recursive하게 구현하였다.
6.[LeetCode] 48. Rotate Image
시간복잡도 : O(n^2)단순한 시뮬레이션 문제로 사각형 외곽부터 안으로 들어가며 90'회전시킨다.공간지각력이 점점 퇴화 하는듯..
7.[AlgoSpot] 외발뛰기
문제 링크동적 계획법을 이용하여 풀이하였다.
8.[AlgoSpot] 삼각형 위의 최대 경로
알고리즘 문제 해결 전략 - 동적 계획법 문제 링크동적 계획법을 이용하여 풀이하였다.dp(x, y) : (x, y)에서 시작해서 맨 아래줄까지 내려가는 모든 경로 중 최대합.
9.[AlgoSpot] 합친 LIS
알고리즘 문제 해결 전략 - 동적 계획법 문제링크 동적 계획법을 이용하여 풀이하였다.기본 LIS에서 확장이 필요하다.max(indexA, indexB) : AindexA, BindexB에서 시작하는 가장 긴 합친 증가 부분 수열 최대 길이라고 놓자.이 때 아래와 같은
10.[LeetCode] 56. Merge Intervals
정렬을 이용한 아이디어가 필요했다. intervals를 start를 기준으로 정렬한 후, for문을 통해 각 원소를 순회하는데 S, E를 두어 아래와 같은 룰을 적용하면 답을 구할 수 있다. 1) 현재 start가 E보다 작은경우 (머지하는 경우) E = max(현재
11.[LeetCode] 62. Unique Paths
우선 생각할 점은 결과가 2\*10^9이 가능하다는 점에서 완전탐색으로 풀 수 없다는 것이다.특정 규칙을 찾거나 dp를 적용하는 것이 필요한데 아래와 같은 규칙으로 손쉽게 풀 수 있다.mapi = mapi-1 + mapi
12.[AlgoSpot] 원주율 외우기
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/PI동적 계획법을 이용하여 풀이하였다.아래와 같은 점화식을 이용하였다. solve(begin) : begin부터 시작하는 문자열의 최소 난이도 so
13.[AlgoSpot] 타일링 방법의 수 세기
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/TILING2기본적인 동적 계획법 문제이다. 아래와 같은 점화식을 이용하였다. dp(n) = dp(n - 1) + dp(n-2)
14.[AlgoSpot] 달팽이
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/SNAIL조금 생각이 필요한 동적 계획법 문제이다.백트레킹 + 메모이제이션을 이용하여 최적화가 필요하다아래와 같은 점화식을 이용하여 풀이하였다.cl
15.[AlgoSpot] 비대칭 타일링
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/ASYMTILING동적 계획법 문제이다.메모이제이션을 이용하여 최적화가 필요하다아래와 같은 점화식과 생각을 이용하여 풀이하였다.비대칭 타일링 갯수
16.[AlgoSpot] 두니발 박사의 탈옥
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/NUMB3RS동적 계획법 문제이다.우선 완전 탐색으로 접근하기 위해 가능한 모든 경우의 수를 계산하는 방법을 고려해보면 아래와 같은 발상을 할 수
17.[AlgoSpot] 여행 짐 싸기
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/NUMB3RS동적 계획법 문제이다.bottom-up방식으로 0/1 냅색 알고리즘을 구현하였다. 점화식은 다음과 같다.dpW : index 포함 이후
18.[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 가사 검색
https://programmers.co.kr/learn/courses/30/lessons/60060?language=java단순하게 모든 쿼리에 대해 문자열 비교를 한다면 100,000^2 비교가 수행되므로 시간초과가 발생하게 된다.이분 탐색을 통해 비교 횟
19.[백준] 17267번 상남자
https://www.acmicpc.net/problem/17267단순 BFS 문제이다. 하지만 함정이..아무 제약없이 단순히 1칸씩 움직이는 BFS 설계한 경우 92%에서 실패한다. (질문 참조) BFS 진행시 우선순위큐를 이용하여 남은 L, 남은 R이 많은
20.[백준] 3197번 백조의 호수
https://www.acmicpc.net/problem/3197최적화가 필요한 BFS 문제이다. (1500x1500 맵 크기)다음 2가지 bfs를 사용하여 풀이하였다.meltProcess() : 각 위치의 얼음이 몇일차에 녹는지 2차원 배열에 만들어준다.mo
21.[백준] 19237 어른 상어
https://www.acmicpc.net/problem/19237시뮬레이션 문제이다. 문제 설명대로 구현하면 되며 각 조건을 어떻게 모델링할지가 중요했다. 빈 칸에 여러 마리 상어가 동시 접근하는 조건 유의 필요.
22.[백준] 19236 청소년 상어
https://www.acmicpc.net/problem/19236시뮬레이션 문제이다. dfs로 구현하였으며 dfs가 진행될 때 이전 상태를 저장하고 restore 해주는 부분에서 삽질을 많이했다... (자바에 좀 더 익숙해져야..)
23.[백준] 20061번 모노미노도미노2
https://www.acmicpc.net/problem/20061시뮬레이션 문제이다. 초록판에 블록을 떨어뜨리는 로직과, 파란판에 블록을 떨어뜨리는 로직에서 공통부분을 찾아 일반화를 시키는 것에 유의해서 구현하였다. 아래는 가장 구현에 신경을 썼던 블록을 떨
24.[AlgoSpot] 실험 데이터 복구하기
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/RESTORE동적 계획법 문제이다.문제 풀이는 다음과 같다. 특정 문자열에 포함되는 문자열들 제거해줌.solve(index, bitMask) : i
25.[AlgoSpot] 틱택토
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/TICTACTOE동적 계획법 문제이다.풀이에 사용된 유틸 및 메인 함수는 다음과 같다 char isFinish(char map) : 현재 보드 상태
26.[AlgoSpot] 숫자게임
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/NUMBERGAME동적 계획법 문제이다.우선 메모이제이션을 위해 보드의 상태를 아래와 같이 정의했다.cacheleft : 전체 보드(배열)을 기준으
27.[AlgoSpot] 회전초밥
문제 설명 알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/SUSHI 문제 풀이 동적 계획법 문제이다. 우선 recursive한 구현으로 접근하면 메모이제이션을 위한 배열의 크기가 20억이 넘기 때문에 r
28.[백준] 16946번 벽 부수고 이동하기4
https://www.acmicpc.net/problem/16946BFS 문제이다. 이 문제에서 가장 신경써야할 부분은 각 벽을 부수고 빈칸을 세줄 때 다른 벽에 대해 특정 빈칸을 중복해서 세지 않아야 한다는 점이다. 각 벽에 대해 이동가능한 칸을 계산하기에
29.[백준] 1981번 배열에서 이동
https://www.acmicpc.net/problem/1981BFS + 투포인터를 이용하여 풀이하였다. 단순 BFS로 풀이하여 모든 경우 수를 고려하는 경우 시간초과가 발생한다. 문제의 조건에서 나올 수 있는 최대값 - 최소값의 범위는 0~200이므로 (제
30.[백준] 2042번 구간 합 구하기
https://www.acmicpc.net/problem/2042세그먼트 트리 자료구조를 적용하면 바로 해결되는 문제이다.
31.[백준] 11066번 파일 합치기
https://www.acmicpc.net/problem/11066처음엔 순서를 마음대로 정할 수 있는 줄 알고 그리디 알고리즘으로 접근했으나 각 파일의 순서는 변경할 수 없어 다이나믹 프로그래밍으로 풀이하였다.문제 풀이에 사용된 점화식은 아래와 같다.
32.[백준] 11049번 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049다이나믹 프로그래밍으로 풀이하였다. (백준 11066번과 유사)문제 풀이에 사용된 점화식은 아래와 같다.
33.[백준] 1208번 부분수열의 합2
https://www.acmicpc.net/problem/1208투 포인터 알고리즘으로 풀이하였다. 문제에서 배열 길이가 40이라 부분 수열의 갯수는 2^40으로 정수의 범위를 초과한다.따라서, 배열을 2개의 배열로 나누어 각 배열에 대해 부분 수열을 모두 구
34.[백준] 12908번 텔레포트 3
문제 설명 https://www.acmicpc.net/problem/12908 문제 풀이 다익스트라 알고리즘을 이용하여 풀이하였다. 텔레포트 노드 간의 거리를 구할때 점프와 텔레포트중 작은 값을 취해야 한다. 다익스트라 거리 계산 시 중간값이 int 범위를 넘을 수 있
35.[백준] 16957번 체스판 위의 공
https://www.acmicpc.net/problem/16957DP를 이용하여 풀이하였다.단순 DFS를 이용하면 시간초과가 나기때문에 DP배열에 DFS 진행 좌표마다 메모이제이션으로 최적화를 수행하였다.
36.[백준] 16971번 배열 B의 값
https://www.acmicpc.net/problem/16971분류를 나누자면 브루트 포스로 풀이하였다. 중요한 점은 배열B의 합을 구할때 A배열에서 각 칸이 더해지는 횟수이다. 배열의 4개 꼭지점 : 1번씩 더해짐배열의 4개의 변 : 2번씩 더해짐배열의
37.[백준] 2056번 작업
https://www.acmicpc.net/problem/2056위상 정렬을 이용하였다. 사이클이 없는 방향 그래프이므로 사이클 탐지 로직은 넣지 않았다. 위상 정렬을 큐를 이용하여 구현하되 degree가 0일 때 큐에 넣을 때 이전 작업 중 가장 늦게 끝나는
38.[백준] 2252번 줄 세우기
https://www.acmicpc.net/problem/2252기본적인 위상 정렬 문제이다.문제 로직상 사이클이 없는 단방향 그래프이므로 유추가능하다.
39.[백준] 8111번 0과 1
https://www.acmicpc.net/problem/8111modular 연산의 성질과 BFS를 이용하여 풀이하였다.문제에서 0과 1로 구성된 숫자를 체크하여 mod N 값이 0인 숫자를 찾아야한다. 따라서 큐를 이용하여 1부터 현재 숫자x10 / 현재
40.[백준] 16952번 체스판 여행2
https://www.acmicpc.net/problem/16952조금 구현이 복잡한 BFS 정도이다. bfs를 진행하며 가지치기를 위해 방문체크를 하였는데 체크에 사용된 배열 설명은 아래와 같다. chkx좌표y좌표현재 도달한 번호 = 말 바꾼 횟수 방문 체크
41.[백준] 1385번 벌집
https://www.acmicpc.net/problem/1385벌집을 구현하는 것이 조금 어려운 BFS이다. (bfs알고리즘은 단순)벌집 구현 하기벌집은 2차원 행렬로 표현이 가능하다. 벌집을 구현하기 위한 메모리 크기 고려 \- 6가지 방향 중 한 방향을
42.[백준] 1695번 펠린드롬 만들기
https://www.acmicpc.net/problem/1695펠린드롬 관련 문제가 좀 생소해서 헤맸다.. 다이나믹 프로그래밍 문제관련 점화식은 아래와 같다.DPa : 인덱스 a 부터 b까지 수열에 최소로 끼워 넣어야하는 숫자의 갯수arra == arrb 일
43.[백준] 1167번 트리의 지름
문제 설명 https://www.acmicpc.net/problem/1089 문제 풀이 우선 각 자리 수에 올수있는 숫자 여부를 판별하여 배열에 넣어준다 >boolean possiblen : n번 자리에 m숫자가 가능한지 여부 저장 이제 결과를 구하기 위해 전체합,
44.[백준] 11664번 선분과 점
https://www.acmicpc.net/problem/11664이분 탐색을 좀 변형하여 풀이하였다.lo = A좌표, hi = B좌표로 둔 후에 이분탐색을 진행하되 아래 조건대로 진행하였다.(lo -> C거리) < (hi -> C 거리) 일 경우 : h
45.[백준] 2110번 공유기 설치
https://www.acmicpc.net/problem/2110이분 탐색을 이용하여 풀이하였다.이분 탐색의 원리는 다음과 같다.instaill (int length) 특정 최소거리 n이 있을때 설치할 수 있는 공유기 갯수는 m개로 정해진다. 집 좌표 arr를
46.[백준] 1939번 중량제한
https://www.acmicpc.net/problem/1939우선 BFS를 이용해 풀이해 보았다. \- 방문탐색으로 해당 노드에 방문할 수 있는 최대 중량 보다 작으면 진입 막음. \- 해당 방식을 이용하면 메모리 초과 및 시간 초과가 발생한다
47.[백준] 1300번 K번째 수
https://www.acmicpc.net/problem/1300이분탐색을 이용하여 풀이하였다. 이분탐색의 대상은 몇번째인지가 아닌 어떤 수인지이며 해당 수를 이용하여 다음을 판별하였다Count(int n) //해당 수보다 같거나 작은 수의 갯수 Count(
48.[백준] 1561번 놀이 공원
https://www.acmicpc.net/problem/1561이분탐색을 이용하여 풀이하였다. 이분탐색의 대상은 특정 시간에 마지막 아이를 태울 수 있는지 여부로 판별하였다.cal(long t) : 특정 시간에 해당 아이를 태우면 0, 이전에 태우면 -1,
49.[백준] 1981번 배열에서 이동
https://www.acmicpc.net/problem/1981이분탐색을 이용하여 풀이하였다. 이분탐색의 대상은 최댓값과 최솟값의 차이의 크기이다.특정 차이에 대해 모든 가능한 최소, 최대값을 지정하고 BFS를 돌려 \- 가능하면 hi = mid (최댓
50.[백준] 5052번 전화번호 목록
https://www.acmicpc.net/problem/5052trie 자료구조를 이용하여 풀이하였다. 우선 문자열들을 길이순으로 정렬해주어야한다. (길이가 짧은 문자열을 먼저 넣어야 판별가능)특정 문자열을 넣어줄때 마다 해당 문자열의 가능한 subStrin
51.[프로그래머스] 억억단을 외우자
https://school.programmers.co.kr/learn/courses/30/lessons/138475?language=java문제의 핵심은 start <= n <= end 인 n이 억억단에 등장하는 횟수는 n의 약수의 개수와 같다는 것
52.[프로그래머스] 숫자 타자 대회
https://school.programmers.co.kr/learn/courses/30/lessons/136797?language=java해당 문제는 브루트포스를 이용할 경우 2^100000 경우의 수가 나오기 때문에 시간초과가 발생한다.다이나믹 프로그래밍을
53.[백준] 16934번 게임 닉네임
https://www.acmicpc.net/problem/16934trie 자료구조를 이용하여 풀이하였다. trie insert 함수를 활용해서 insert시 해당 닉네임 별칭을 리턴하도록 구현하였다.Node의 isEnd 변수를 int로 놓고 해당 노드에서 i
54.[프로그래머스] 부대복귀
https://school.programmers.co.kr/learn/courses/30/lessons/132266dijkstra로 풀어도 되고, 간선 가중치가 모두 1이므로 BFS로 풀어도 무방하다.문제의 핵심은 각 source로 부터 destination까
55.[프로그래머스] 2차원 동전 뒤집기
https://school.programmers.co.kr/learn/courses/30/lessons/131703?language=java브루트 포스로 풀이할 경우 시간초과 발생하진 않을 것 같지만..? 좀 더 효율적으로 풀이하였다.생각한 풀이는 다음과 같다
56.[프로그래머스] 카운트 다운
https://school.programmers.co.kr/learn/courses/30/lessons/131129처음엔 조건만 잘 구분하여 조건문으로 끝낼 수 있으려나 했지만 역시 쉽지 않았다.DP를 이용하여 풀이하였다.int\[] solve(int rema
57.[프로그래머스] 등산코스 정하기
https://school.programmers.co.kr/learn/courses/30/lessons/118669문제를 풀기 위해 사용했던 인사이트는 다음과 같다. 왕복을 구할 필요 없이 정상까지 편도 최소값을 구하면 된다. (시작점 -> 정상 최소값 <
58.[프로그래머스] 코딩 테스트 공부
https://school.programmers.co.kr/learn/courses/30/lessons/118668다이나믹 프로그래밍을 통해 풀이하였다.사용된 점화식은 다음과 같다.dp알고력코딩력 = 현재 알고력, 코딩력에서 모든 문제를 다풀기 위해 사용할 최
59.[프로그래머스] 양과 늑대
https://school.programmers.co.kr/learn/courses/30/lessons/92343DFS를 이용하여 풀이하였다.우선 노드간의 이동은 양방향이동을 전제로 하였다.DFS를 진행하며 2개의 방문체크를 해주었다.visitedN : 진행하
60.[프로그래머스] 파괴되지 않은 건물
https://school.programmers.co.kr/learn/courses/30/lessons/92344구간합을 이용하여 풀이하였다. 우선 일반적으로 풀이한다면 시간 복잡도는 O(가로x세로x스킬갯수)가 되므로 시간초과가 발생한다.결국 스킬을 사용하며
61.[프로그래머스] 이중우선순위큐
https://school.programmers.co.kr/learn/courses/30/lessons/42628우선 순위큐 2개를 이용하여 풀이하였다. max heap 역할을 하는 큐를 하나 생성한다.각 명령어에 대한 로직인 다음과 같다. Insert일 경우
62.[프로그래머스] 정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105간단한 다이나믹 프로그래밍 문제이다. dpx : x로우, y칼럼에서부터 바닥까지 경로의 합중 최대값
63.[프로그래머스] 길 찾기 게임
https://school.programmers.co.kr/learn/courses/30/lessons/42892기본 그래프 이론과 재귀를 이용해여 풀이하였다. 풀이 순서는 다음과 같다. 1\. 이진 트리 만들기 2\. 전위 순회, 후위 순회 결
64.[프로그래머스] 징검다리 건너기
https://school.programmers.co.kr/learn/courses/30/lessons/64062초기 접근은 배열의 최솟값을 전체에 빼주고 연속된 0의 갯수를 판별하여 가능 여부를 판별하였는데 이 방법은 최악의 경우 20만 x 20만으로 시간
65.[프로그래머스] 합승 택시 요금
https://school.programmers.co.kr/learn/courses/30/lessons/72413플로이드 워셜 알고리즘을 이용하여 풀이하였다.결과 도출을 위한 과정은 다음과 같다.플로이드 워셜 알고리즘을 이용해 모든 노드 사이의 최소 거리를 구
66.[프로그래머스] 불량 사용자
https://school.programmers.co.kr/learn/courses/30/lessons/64064간단한 DFS 문제였다. 배열의 길이가 최대 8밖에 되지 않기 때문에 ban id에 매칭되는 user id 맵을 만들어주고 dfs를 진행하며 각 b
67.[프로그래머스] 블록 이동하기
https://school.programmers.co.kr/learn/courses/30/lessons/60063상세한 구현이 필요한 BFS 문제이다. 단순 상하 좌우 이동 외에 회전 이동이 있기 때문에 BFS에서 각 status를 다음과 같이 표시했다.Poi
68.[프로그래머스] 모두 0으로 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/76503- 예상치 못한 함정으로 살짝 까다로웠던 문제였다.처음 접근은 특정 노드 부터 시작하여 DFS로 풀이하였다. 하지만 최악의 경우 DFS의 depth
69.[프로그래머스] 다단계 칫솔 판매
https://school.programmers.co.kr/learn/courses/30/lessons/77486DFS로 풀이하였다. 크게 2가지 함정이 존재하였다.일반적인 DFS처럼 각 노드를 1번만 방문하도록 구현해서는 안된다. 특정 노드에 하위 2개의 노
70.[프로그래머스] 보행자 천국
https://school.programmers.co.kr/learn/courses/30/lessons/1832간단한 DFS + DP 문제였다Bottom-Up 방식으로 구현하였는데 그나마 특별한 점은 DP배열을 DPX가 아닌 DPX들어온방향으로 구성해줘야 한다
71.[프로그래머스] 매칭 점수
https://school.programmers.co.kr/learn/courses/30/lessons/42893문자열 핸들링 문제였다. 각각에 대해 url, 링크를 파싱해서 결과를 점수를 계산하면 된다.
72.[프로그래머스] 선입 선출 스케줄링
https://school.programmers.co.kr/learn/courses/30/lessons/12920이분탐색으로 풀이하였다.시간을 기준으로 이분탐색으로 줄이고 늘려가며 마지막 작업이 진행되는 시간을 찾고 시간을 찾으면 마지막 작업을 수행하는 코어
73.[프로그래머스] GPS
https://school.programmers.co.kr/learn/courses/30/lessons/1837다이나믹 프로그래밍으로 풀이하였다. 점화식은 다음과 같다. DPN : 시간이 T이고 해당 노드가 N일때, 이후 목적지까지 최소 수정 갯수DPNT 모든
74.[프로그래머스] 리틀 프렌즈 사천성
https://school.programmers.co.kr/learn/courses/30/lessons/1836- BFS로 풀이하였다. 시간복잡도 자체는 타이트하지 않아서 쉽게 생각했지만 구현이 조금은 복잡해서 잔실수가 많이 나왔다. 기억나는 실수들 \-
75.[프로그래머스] 표현 가능한 이진트리
https://school.programmers.co.kr/learn/courses/30/lessons/150367DFS로 풀이 하였다. 문제는 크게 2단계로 구성된다. 특정수를 포화이진트리 크기에 맞게 이진수로 변경 (포화이진트리 이진수이라 명명)DFS로 포
76.[프로그래머스] 표 병합
https://school.programmers.co.kr/learn/courses/30/lessons/150366UNION-FIND 알고리즘을 이용하여 풀이하였다.병합된 노드는 최상단 부모 노드만 값을 가지도록 구현하였다.병합 해제시, 조심해야할 부분은 모든
77.[프로그래머스] 사라지는 발판
https://school.programmers.co.kr/learn/courses/30/lessons/92345DFS를 이용하여 풀이하였다. 우선 DFS 결과값은 양수, 음수로 나뉘는데 결과값 기준은 다음과 같다.승리한 분기'가' 있으면 승리한 분기 중 가장
78.[프로그래머스] 셔틀버스
https://school.programmers.co.kr/learn/courses/30/lessons/17678직관적으로 이분 탐색을 이용하여 풀이하였다.콘의 도착시간을 기준으로 이분 탐색을 시행하고 탈 수 있는 시간의 최대값을 구한다. 이분 탐색에 앞서 각
79.[프로그래머스] 베스트앨범
https://school.programmers.co.kr/learn/courses/30/lessons/42579자료구조와 정렬을 이용하여 풀이하였다.크게 아래 2단계로 이뤄진다.Map<장르명, 총재생수>, Map<장르명, List<곡정보>>
80.[프로그래머스] N으로 표현
https://school.programmers.co.kr/learn/courses/30/lessons/42895DP를 이용하여 풀이하였다.DPK = K자리로 만들 수 있는 수들을 모아논 리스트DP1 ~ DP8 까지 차례대로 구해보며 점화식을 도출해보자.DP1
81.[프로그래머스] 단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163BFS를 이용하여 풀이하였다.각 단어의 인덱스를 번호로 두고 각 번호끼리 이동할 수 있는 Map을 만들어 준다. (한글자만 다른지 확인)begin에
82.[프로그래머스] 아이템 줍기
https://school.programmers.co.kr/learn/courses/30/lessons/87694BFS를 이용하여 풀이하였다.문제의 풀이 순서는 간단하다격자를 만들고 직사각형에 해당하는 칸을 1로 치환해준다.시작점에서 BFS를 수행하되 다음칸에
83.[프로그래머스] 풍선 터트리기
https://school.programmers.co.kr/learn/courses/30/lessons/68646완전 탐색은 불가능 하다.문제의 조건에서 알 수 있는 사실은 특정 풍선 좌, 우측으로 해당 수보다 작은 수가 존재하면 해당 풍선은 마지막까지 존재할
84.[프로그래머스] 최적의 행렬 곱셈
https://school.programmers.co.kr/learn/courses/30/lessons/12942다이나믹 프로그래밍으로 풀이하였다.한가지 알아야할 사전지식은 행렬곱셈에서 결합법칙은 성립하지만 교환법칙은 성립하지 않는다는 것이다. (행렬의 순서는
85.[프로그래머스] 숫자 게임
https://school.programmers.co.kr/learn/courses/30/lessons/12987그리디스러운 아이디어가 필요한 문제이다.아이디어는 다음과 같다. (각 A원소에 대해 가장 가까운 큰 수 찾기)우선 A, B를 각각 정순으로 정렬한다
86.[프로그래머스] 보석 쇼핑
https://school.programmers.co.kr/learn/courses/30/lessons/67258투 포인터 알고리즘을 이용하여 풀이하였다. L, R을 배열의 인덱스 0으로 두고 다음 로직을 수행한다.R을 0 ~ N-1까지 반복한다. \- m
87.[프로그래머스] 미로 탈출 명령어
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/150365 문제 풀이 간단한 BFS로 문제였다. BFS로 진행하되 방문체크는 chkx[이동거리]로 진행한다. 이때,진행우선 순위는 사전순으로 (아래, 왼
88.[프로그래머스] 섬 연결하기
https://school.programmers.co.kr/learn/courses/30/lessons/42861단순 최소 신장 트리 문제였다.크루스칼 알고리즘으로 풀이하였다.
89.[프로그래머스] 경주로 건설
https://school.programmers.co.kr/learn/courses/30/lessons/67259간단한 BFS로 문제였다. BFS로 진행하되 방문체크는 chkx들어온 방향으로 수행한다.들어온 방향에 따라 다음 3가지 케이스로 나누어 진행한다.
90.[프로그래머스] 순위
https://school.programmers.co.kr/learn/courses/30/lessons/49191DFS를 이용하여 풀이하였다.문제의 가장 큰 인사이트는 선수 간의 관계를 단방향 그래프로 나태냈을때, 그래프에서 특정 선수와 다른 모든 선수가 도달
91.[프로그래머스] 표 편집
https://school.programmers.co.kr/learn/courses/30/lessons/81303효율성 테스트가 까다로운 문제였다. 일반적으로 문자열에 대한 이해만 있다면 정확성 테스트는 쉽게 통과가 가능하다. 처음엔 결과 배열만 놓고 인덱스를
92.[프로그래머스] 기둥과 보 설치
https://school.programmers.co.kr/learn/courses/30/lessons/60061구현이 조금 까다로운 문제였다. 구현을 간단히 하기 위해 크게 2가지 인사이트가 사용되었다. 설치와 삭제 가능 여부를 하나의 함수로 통일하였다.
93.[프로그래머스] 광고 삽입
https://school.programmers.co.kr/learn/courses/30/lessons/72414구간합을 이용하여 풀이하였다.문제는 다음과 같은 방향으로 풀이하였다. 시간 배열을 두고 각 시간에 시청자 수를 구한다. 가능한 범위를 순회하면서 특
94.[프로그래머스] 연속 펄스 부분 수열의 합
https://school.programmers.co.kr/learn/courses/30/lessons/161988- 구간합, 투포인터 알고리즘을 이용하여 풀이하였다. 우선 brute force 사용시 50만 \* 50만 정도 복잡도로 시간초과가 발생한다.다음
95.[프로그래머스] 외벽 점검
https://school.programmers.co.kr/learn/courses/30/lessons/60062DFS, 비트마스킹을 이용하여 풀이하였다. 문제 풀이 방법은 다음과 같다. 모든 취약지점 간의 거리를 인접행렬로 정의 (시계, 반시계 한쪽 방향으로
96.[프로그래머스] 스타 수열
https://school.programmers.co.kr/learn/courses/30/lessons/70130특정 숫자(num)를 교집합으로 하는 스타 수열의 집합 갯수는 아래처럼 구할 수 있다. a 배열의 길이와 동일한 chk 배열을 준비한다.a 배열을
97.[프로그래머스] 카드 짝 맞추기
https://school.programmers.co.kr/learn/courses/30/lessons/72415BFS, DFS(순열)을 이용하여 풀이하였다.순열을 이용한 전체적인 큰 틀은 다음과 같다. dfs(int ind, int tmpRes, int r,
98.[프로그래머스] 공 이동 시뮬레이션
https://school.programmers.co.kr/learn/courses/30/lessons/87391인사이트가 필요한 구현 문제였다.우선 생각 해야할 것은 완전탐색(DFS, BFS)으로 좌표 1개 단위로 풀이를 진행하면 무조건 시간초과가 난다는 점
99.[프로그래머스] 금과 은 운반하기
https://school.programmers.co.kr/learn/courses/30/lessons/86053결정 함수 구현이 좀 복잡한 이분 탐색문제였다. 이분 탐색은 시간을 기준으로 동작시켰고 시간의 최소값은 0, 최대값은 20억(a+b의 최대값) \*
100.[프로그래머스] 등대
https://school.programmers.co.kr/learn/courses/30/lessons/133500트리를 이용한 DFS를 이용하여 풀이하였다. 우선 전체 노드 연결 상태를 루트가 1인 트리라고 생각한다. (사이클X)DFS 진행은 다음과 같다.
101.[프로그래머스] 고고학 최고의 발견
https://school.programmers.co.kr/learn/courses/30/lessons/131702DFS를 이용하여 풀이하였다.우선 brute Force 사용하되 특정 아이디어가 필요하다. (단순하게 전체 경우의 수는 4^64)첫번째행의 각 칼
102.[프로그래머스] 몸짱 트레이너 라이언의 고민
https://school.programmers.co.kr/learn/courses/30/lessons/1838구간합, BruteForce를 이용해 풀이하였다.풀이 순서는 다음과 같다. 가장 많이 겹치는 인원이 몇인지 확인 해당 인원에 대해 최대 거리로 배치하
103.[프로그래머스] 호텔 방 배정
https://school.programmers.co.kr/learn/courses/30/lessons/64063HashMap을 이용하여 풀이하였다. 가장 큰 문제는 방번호의 범위가 너무 크다는 점이다 (1조) 풀이는 다음과 같다. HashMap에 (key,
104.[프로그래머스] 무지의 먹방 라이브
https://school.programmers.co.kr/learn/courses/30/lessons/42891이분 탐색을 이용하여 풀이하였다. 풀이의 아이디어는 다음과 같다. 이분 탐색의 기준은 원판의 회전 수이다. 구하고자하는 값은 특정 회전일때 K시간
105.[프로그래머스] [3차] 자동완성
https://school.programmers.co.kr/learn/courses/30/lessons/17685Trie를 이용한 트리 자료구조로 풀이하였다. 풀이는 다음과 같다. 기본 Trie를 변형하여 각 노드가 이전 노드를 기억하는 Trie에 모든 문자열
106.[프로그래머스] 쿠키 구입
https://school.programmers.co.kr/learn/courses/30/lessons/49995누적합과 이분 탐색을 이용하여 풀이하였다. 우선 이중 for문으로 L과 R값을 정해준다. L,R이 정해지면 L~M, M+1~R을 나눌 M을 정해야하
107.[프로그래머스] 징검다리
https://school.programmers.co.kr/learn/courses/30/lessons/43236이분 탐색을 이용하여 풀이하였다. 이분 탐색의 대상은 돌 사이의 거리이다. 0 ~ distance 사이에서 이분 탐색을 진행하는데 특정 돌 사이의
108.[프로그래머스] 가사 검색
https://school.programmers.co.kr/learn/courses/30/lessons/60060트라이를 이용하여 풀이하였다. 일반적인 트라이를 사용하되 단어의 정순, 역순 트라이를 각각 생성하여 가사를 insert할 때 각각 insert 해준
109.[LeetCode] 2353. Design a Food Rating System
https://leetcode.com/problems/design-a-food-rating-system/description/해쉬맵 자료구조와 우선순위큐를 이용하여 풀이하였다.두가지 해쉬맵을 유지한다. Map<String, PriorityQueue> ty
110.[LeetCode] 2353. Design a Food Rating System
https://leetcode.com/problems/design-a-food-rating-system/description/해쉬맵 자료구조와 우선순위큐를 이용하여 풀이하였다.두가지 해쉬맵을 유지한다. Map<String, PriorityQueue> ty
111.[프로그래머스] 단어 퍼즐
https://school.programmers.co.kr/learn/courses/30/lessons/12983DP를 이용하여 풀이하였다. 우선 HashSet 자료구조를 이용하여 후보 단어들을 저장하였다. (존재 여부 확인 O(1))후보 단어들의 길이가 1이
112.[프로그래머스] 블록 게임
https://school.programmers.co.kr/learn/courses/30/lessons/42894구현 문제이다. 우선, 각 블록에 대해 모양을 특정하는 건 복잡하므로 특정 블록을 감싸는 직사각형의 ROW, COL 범위를 해당 블록 정보로 저장해
113.[프로그래머스] 동굴 탐험
https://school.programmers.co.kr/learn/courses/30/lessons/67260복잡한 BFS 문제이다. 우선 BFS를 진행하기에 앞서 다음 초기화를 진행해준다. \- List<List<Integer>> map :
114.[프로그래머스] 지형 편집
https://school.programmers.co.kr/learn/courses/30/lessons/12984두가지 풀이가 존재한다. 1)이분 탐색 2)쉬운 아이디어우선 문제에서 존재하는 블록의 높이의 범위를 min ~ max라고하고 블록을 n개로 맞추었을
115.[프로그래머스] 트리 트리오 중간값
https://school.programmers.co.kr/learn/courses/30/lessons/68937트리, BFS, 중간값에 대한 이해가 필요한 문제이다.중간값이란 세개의 수를 정렬했을 때 2번째 수를 뜻한다 (!=평균값)트리의 중요한 특징은 다음
116.[프로그래머스] 지형 이동
https://school.programmers.co.kr/learn/courses/30/lessons/62050BFS, Heap을 이용하여 풀이하였다.풀이는 다음과 같다. BFS를 위한 Queue와 사다리를 설치할 후보를 넣어줄 높이 차이로 정렬된 Prior
117.[프로그래머스] 사칙연산
https://school.programmers.co.kr/learn/courses/30/lessons/1843DP를 이용하여 풀이하였다. DP 배열의 정의는 다음과 같다.DPa0 : 숫자 배열의 인덱스 a~b 범위의 연산의 최소값DPa1 : 숫자 배열의 인덱
118.[프로그래머스] 매출 하락 최소화
https://school.programmers.co.kr/learn/courses/30/lessons/72416DP를 이용하여 풀이하였다. 난이도가 꽤 있었던 문제..우선 전체 관계를 트리 형태로 정리한다. DP배열의 정의는 다음과 같다. DP노드 번호 :
119.[프로그래머스] 행렬과 연산
https://school.programmers.co.kr/learn/courses/30/lessons/118670Deque는 이용했지만 아이디어에 한계의 부딪혀 풀이를 참조하였다.자료구조를 극한으로 활용하는 문제가 아닐까 싶다.다음 그림과 같이 행렬을 분해한
120.[백준] 2357번 최솟값과 최댓값
https://www.acmicpc.net/problem/2357세그먼트 트리를 이용하여 풀이하였다. 구간의 최대, 최소를 O(n)으로 탐색하며 풀면 당연히 시간초과가 발생한다. 구간의 최소값을 저장하는 세그먼트 트리와, 구간의 최대값을 저장하는 세그먼트 트리
121.[백준] 1016번 제곱ㄴㄴ수
https://www.acmicpc.net/problem/1016에라토스테네스의 체를 응용하여 풀이하였다.문제 풀이는 다음과 같다.min~max 값을 저장하는 배열을 생성한다. (최대 길이 10^6) 특정 숫자의 제곱수의 배수가 해당 범위 내에 있을 때, 그
122.[백준] 2263번 트리의 순회
https://www.acmicpc.net/problem/2263트리에서 인오더, 프리오더, 포스트오더의 성질을 이용하여 풀이하였다.인오더 순서의 특징은 루트 노드의 인덱스를 기준으로 왼쪽값들은 왼쪽 자식 트리, 오른쪽값들은 오른쪽 자식 트리가 된다.포스트오더
123.[백준] 6549번 히스토그램에서 가장 큰 직사각형
https://www.acmicpc.net/problem/6549세그먼트 트리 + 분할 정복을 이용하여 풀이하였다.우선 세그먼트 트리를 이용하여 특정 구간의 가장 높이가 낮은 지점의 인덱스를 저장한다.이제 전체 구간의 최대 넓이를 구해야 하는데 모든 구간을 반
124.[백준] 1562번 계단 수
https://www.acmicpc.net/problem/1562비트마스킹 + DP를 이용하여 풀이하였다. 문제에서 DP 최적 부분 구조를 구성할 때 메모이제이션 해야하는 요인은 다음 3가지이다. 현재 자리수 현재까지 0~9까지 숫자의 방문 여부 마지막 수 위
125.[백준] 1799번 비숍
https://www.acmicpc.net/problem/1799최적화가 필요한 백트래킹 문제였다.우선 기본적인 알고리즘 개요는 백트래킹으로 이용하여 첫번째 칸부터 마지막까지 둘 것인지 안 둘 것 인지 정하고 가장 큰 값을 구하는 것이다.문제는 시간복잡도인데,
126.[백준] 2887번 행성 터널
https://www.acmicpc.net/problem/2887최소 신장 트리를 사용하여 풀이하였다.우선 최소 신장 트리 알고리즘을 프림(N^2), 크루스칼(ElogE) 두가지가 존재한다.간선의 갯수를 고려해 시간복잡도가 낮은 알고리즘을 택해야 한다문제에서
127.[백준] 11003번 최솟값 찾기
https://www.acmicpc.net/problem/11003데크 자료구조를 이용하여 풀이하였다. 데크의 구조는 아래와 같다. deque<Integer, Integer> : 데크에 (인덱스, 값) 형태로 저장 deque0 : 구간 내 최소값 저장 d
128.[백준] 1517번 버블 소트
https://www.acmicpc.net/problem/1517문제는 버블 소트의 SWAP 횟수를 필요로 하지만 버블소트를 사용하면 O(N^2) 시간복잡도로 시간초과가 발생한다. 문제는 O(NlogN)알고리즘인 머지소트를 진행하여 SWAP 횟수를 계산하여 풀
129.[백준] 2150번 Strongly Connected Component
https://www.acmicpc.net/problem/2150SCC 문제의 선형시간 풀이를 위한 알고리즘인 코사라주, 타잔 알고리즘 중 타잔 알고리즘을 사용하였다.각 노드에 대해 DFS를 진행하되 스택에 노드를 넣어주고 DFS 진행 순으로 각 노드에 증가하
130.[백준] 2213번 트리의 독립집합
https://www.acmicpc.net/problem/2213다이나믹 프로그래밍으로 풀이하였다. 트리에서 DP를 사용하는 가장 대표적인 문제라고 볼 수 있다.점화식은 다음과 같이 구성된다.DPN : N번노드를 미포함하고 N번 노드를 루트로 하는 독립집합의
131.[백준] 14428번 수열과 쿼리16
https://www.acmicpc.net/problem/14428기본적인 세그먼트 트리 문제이다. 세그먼트 트리 엘리먼트로는 (index, value)를 포함한 객체를 넣어준 후 문제 조건에 맞게 작은값으로 비교하는 연산을 거쳐 세그먼트 트리 로직을 수행한다
132.[백준] 5676번 음주 코딩 (java)
https://www.acmicpc.net/problem/5676기본적인 세그먼트 트리 문제이다. 곱 연산은 Long 자료형으로 저장하더라도 오버플로우가 날 수 있기 때문에 결과에 필요한 부호만 저장하는 로직을 사용해야 한다.
133.[프로그래머스] 튜브의 소개팅
https://school.programmers.co.kr/learn/courses/30/lessons/1839생각이 필요한 BFS 문제이다. BFS의 큐대신에 대화시간이 작을수록 우선하는 우선순위큐를 이용해서 BFS를 진행한다.위 행위의 의미는 대화시간의 제
134.[백준] 1311번 할 일 정하기1
https://www.acmicpc.net/problem/1311우선 bruteforce로 풀기에는 20!의 경우의 수가 나오므로 불가능하다.비트마스킹을 이용한 DP를 이용하여 풀이하였다.DP테이블 정의는 다음과 같다. DP현재까지 선택한 일의 조합 : 현재
135.[백준] 12850번 본대 산책2
https://www.acmicpc.net/problem/12850BruteForce나 DP로 풀기에는 D의 최대값이 10억이기 때문에 불가하다.문제를 풀기 위해서는 아래와 같은 인사이트가 필요하다.문제의 노드간의 인접행렬을 표현하면 mapa는 a->b로 가는
136.[백준] 15644번 구슬탈출3
https://www.acmicpc.net/problem/15644유서 깊은 복잡한 구현 + BFS 문제이다.구슬들의 위치, 횟수, 이동 루트를 큐에 넣어서 BFS를 진행한다.구슬들의 위치, 방향에 따라 빨간 구슬을 먼저 움직일지, 파란 구슬을 먼저 움직일지를
137.[백준] 2307번 도로검문
https://www.acmicpc.net/problem/2307다익스트라 알고리즘을 반복해서 수행하면 된다.우선 1 -> N까지 최단 경로를 구한 후, 주어진 edge들을 하나씩 소거하면서 최단 경로를 구해준 후 최대 지연 시간을 구하면 된다.
138.[백준] 17371번 이사
https://www.acmicpc.net/problem/17371그리디한 방식으로 BruteForce를 진행하면 된다.문제에서 가장가까운 거리, 가장 먼 거리의 평균을 구한다고 했는데 편의시설 지점을 정답 후보로 두게되면 가장가까운 거리는 0으로 소거가 가능
139.[백준] 1800번 인터넷 설치
https://www.acmicpc.net/problem/1800그래프를 BFS로 탐색하며 DP를 사용해 풀이하였다.점화식은 아래와 같다 DPN : N번 노드까지 K개의 공짜 케이블을 썼을 때 비용 최소값 BFS로 탐색하며 현재 상태에서 공짜 케이블을 쓰는 케
140.[백준] 18500번 미네랄2
https://www.acmicpc.net/problem/18500복잡한 시뮬레이션 문제이다. 풀이는 다음 과정으로 이뤄진다. 블록 제거 클러스터 생성 클러스터 떠있는지 판별 후 떨어뜨리기 클러스터 생성에는 BFS를 사용하였다.클러스터가 떠있는지 판별하기 위해
141.[백준] 4716번 풍선
https://www.acmicpc.net/problem/4716정렬 및 그리디한 접근을 이용해 풀이하였다.문제에서 중요한 정렬의 조건의 경우 A와의 거리, B와의 거리 차이를 기준으로 내림차순 정렬을 진행하여 차이가 큰 것부터 가까운 풍선을 우선적으로 나르면
142.[백준] 외판원 순회3
https://www.acmicpc.net/problem/16991외판원 순회 문제는 다이나믹 프로그래밍을 사용하는 것이 정석이다.DP현재노드위 배열을 통해 메모이제이션을 진행하며 BFS를 진행하여 풀이하였다.
143.[백준] 13392번 방법을 출력하지 않는 숫자 맞추기
https://www.acmicpc.net/problem/13392다이나믹 프로그래밍으로 풀이하였다.아래 점화식을 통해 메모이제이션하며 DFS를 진행했다.DPN : 이전 왼쪽 회전수가 정해져있을때, N번째 숫자부터 맞추기 위한 최소 회전값