아래와 같은 기존의 next_permutation 알고리즘을 이용하되 마지막 순열에서 넘어갈 때 조건 설정을 추가해주었다.
기본적인 방식은 Binary Search 방식을 사용하되 mid = (left+right)/2 인덱스 기준으로 왼쪽 혹은 오른쪽은 완전히 정렬되어 있다는 점을 이용하여 분기문을 달리하여 풀이하였다.
기본적인 방식은 Binary Search 방식을 사용하되 Target을 찾았을 경우에 범위를 찾기 위한 추가적인 Binary Search를 진행해주었다.
Back Tracking을 이용하여 풀이하였다. 직관적으로 candidates들을 하나씩 방문하며 각각 N번씩 더해주고 다음 인덱스로 넘어가는 방식으로 index == candidates.length일 때를 기저 조건으로 두고 모든 경우를 판별하였다.
Permutation을 recursive하게 구현하였다.
시간복잡도 : O(n^2)단순한 시뮬레이션 문제로 사각형 외곽부터 안으로 들어가며 90'회전시킨다.공간지각력이 점점 퇴화 하는듯..
문제 링크동적 계획법을 이용하여 풀이하였다.
알고리즘 문제 해결 전략 - 동적 계획법 문제 링크동적 계획법을 이용하여 풀이하였다.dp(x, y) : (x, y)에서 시작해서 맨 아래줄까지 내려가는 모든 경로 중 최대합.
알고리즘 문제 해결 전략 - 동적 계획법 문제링크 동적 계획법을 이용하여 풀이하였다.기본 LIS에서 확장이 필요하다.max(indexA, indexB) : AindexA, BindexB에서 시작하는 가장 긴 합친 증가 부분 수열 최대 길이라고 놓자.이 때 아래와 같은
정렬을 이용한 아이디어가 필요했다. intervals를 start를 기준으로 정렬한 후, for문을 통해 각 원소를 순회하는데 S, E를 두어 아래와 같은 룰을 적용하면 답을 구할 수 있다. 1) 현재 start가 E보다 작은경우 (머지하는 경우) E = max(현재
우선 생각할 점은 결과가 2\*10^9이 가능하다는 점에서 완전탐색으로 풀 수 없다는 것이다.특정 규칙을 찾거나 dp를 적용하는 것이 필요한데 아래와 같은 규칙으로 손쉽게 풀 수 있다.mapi = mapi-1 + mapi
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/PI동적 계획법을 이용하여 풀이하였다.아래와 같은 점화식을 이용하였다. solve(begin) : begin부터 시작하는 문자열의 최소 난이도 so
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/TILING2기본적인 동적 계획법 문제이다. 아래와 같은 점화식을 이용하였다. dp(n) = dp(n - 1) + dp(n-2)
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/SNAIL조금 생각이 필요한 동적 계획법 문제이다.백트레킹 + 메모이제이션을 이용하여 최적화가 필요하다아래와 같은 점화식을 이용하여 풀이하였다.cl
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/ASYMTILING동적 계획법 문제이다.메모이제이션을 이용하여 최적화가 필요하다아래와 같은 점화식과 생각을 이용하여 풀이하였다.비대칭 타일링 갯수
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/NUMB3RS동적 계획법 문제이다.우선 완전 탐색으로 접근하기 위해 가능한 모든 경우의 수를 계산하는 방법을 고려해보면 아래와 같은 발상을 할 수
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/NUMB3RS동적 계획법 문제이다.bottom-up방식으로 0/1 냅색 알고리즘을 구현하였다. 점화식은 다음과 같다.dpW : index 포함 이후
https://programmers.co.kr/learn/courses/30/lessons/60060?language=java단순하게 모든 쿼리에 대해 문자열 비교를 한다면 100,000^2 비교가 수행되므로 시간초과가 발생하게 된다.이분 탐색을 통해 비교 횟
https://www.acmicpc.net/problem/17267단순 BFS 문제이다. 하지만 함정이..아무 제약없이 단순히 1칸씩 움직이는 BFS 설계한 경우 92%에서 실패한다. (질문 참조) BFS 진행시 우선순위큐를 이용하여 남은 L, 남은 R이 많은
https://www.acmicpc.net/problem/3197최적화가 필요한 BFS 문제이다. (1500x1500 맵 크기)다음 2가지 bfs를 사용하여 풀이하였다.meltProcess() : 각 위치의 얼음이 몇일차에 녹는지 2차원 배열에 만들어준다.mo
https://www.acmicpc.net/problem/19237시뮬레이션 문제이다. 문제 설명대로 구현하면 되며 각 조건을 어떻게 모델링할지가 중요했다. 빈 칸에 여러 마리 상어가 동시 접근하는 조건 유의 필요.
https://www.acmicpc.net/problem/19236시뮬레이션 문제이다. dfs로 구현하였으며 dfs가 진행될 때 이전 상태를 저장하고 restore 해주는 부분에서 삽질을 많이했다... (자바에 좀 더 익숙해져야..)
https://www.acmicpc.net/problem/20061시뮬레이션 문제이다. 초록판에 블록을 떨어뜨리는 로직과, 파란판에 블록을 떨어뜨리는 로직에서 공통부분을 찾아 일반화를 시키는 것에 유의해서 구현하였다. 아래는 가장 구현에 신경을 썼던 블록을 떨
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/RESTORE동적 계획법 문제이다.문제 풀이는 다음과 같다. 특정 문자열에 포함되는 문자열들 제거해줌.solve(index, bitMask) : i
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/TICTACTOE동적 계획법 문제이다.풀이에 사용된 유틸 및 메인 함수는 다음과 같다 char isFinish(char map) : 현재 보드 상태
알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/NUMBERGAME동적 계획법 문제이다.우선 메모이제이션을 위해 보드의 상태를 아래와 같이 정의했다.cacheleft : 전체 보드(배열)을 기준으
문제 설명 알고리즘 문제 해결 전략 - 동적 계획법 https://algospot.com/judge/problem/read/SUSHI 문제 풀이 동적 계획법 문제이다. 우선 recursive한 구현으로 접근하면 메모이제이션을 위한 배열의 크기가 20억이 넘기 때문에 r
https://www.acmicpc.net/problem/16946BFS 문제이다. 이 문제에서 가장 신경써야할 부분은 각 벽을 부수고 빈칸을 세줄 때 다른 벽에 대해 특정 빈칸을 중복해서 세지 않아야 한다는 점이다. 각 벽에 대해 이동가능한 칸을 계산하기에
https://www.acmicpc.net/problem/1981BFS + 투포인터를 이용하여 풀이하였다. 단순 BFS로 풀이하여 모든 경우 수를 고려하는 경우 시간초과가 발생한다. 문제의 조건에서 나올 수 있는 최대값 - 최소값의 범위는 0~200이므로 (제
https://www.acmicpc.net/problem/2042세그먼트 트리 자료구조를 적용하면 바로 해결되는 문제이다.
https://www.acmicpc.net/problem/11066처음엔 순서를 마음대로 정할 수 있는 줄 알고 그리디 알고리즘으로 접근했으나 각 파일의 순서는 변경할 수 없어 다이나믹 프로그래밍으로 풀이하였다.문제 풀이에 사용된 점화식은 아래와 같다.
https://www.acmicpc.net/problem/11049다이나믹 프로그래밍으로 풀이하였다. (백준 11066번과 유사)문제 풀이에 사용된 점화식은 아래와 같다.
https://www.acmicpc.net/problem/1208투 포인터 알고리즘으로 풀이하였다. 문제에서 배열 길이가 40이라 부분 수열의 갯수는 2^40으로 정수의 범위를 초과한다.따라서, 배열을 2개의 배열로 나누어 각 배열에 대해 부분 수열을 모두 구
문제 설명 https://www.acmicpc.net/problem/12908 문제 풀이 다익스트라 알고리즘을 이용하여 풀이하였다. 텔레포트 노드 간의 거리를 구할때 점프와 텔레포트중 작은 값을 취해야 한다. 다익스트라 거리 계산 시 중간값이 int 범위를 넘을 수 있
https://www.acmicpc.net/problem/16957DP를 이용하여 풀이하였다.단순 DFS를 이용하면 시간초과가 나기때문에 DP배열에 DFS 진행 좌표마다 메모이제이션으로 최적화를 수행하였다.
https://www.acmicpc.net/problem/16971분류를 나누자면 브루트 포스로 풀이하였다. 중요한 점은 배열B의 합을 구할때 A배열에서 각 칸이 더해지는 횟수이다. 배열의 4개 꼭지점 : 1번씩 더해짐배열의 4개의 변 : 2번씩 더해짐배열의
https://www.acmicpc.net/problem/2056위상 정렬을 이용하였다. 사이클이 없는 방향 그래프이므로 사이클 탐지 로직은 넣지 않았다. 위상 정렬을 큐를 이용하여 구현하되 degree가 0일 때 큐에 넣을 때 이전 작업 중 가장 늦게 끝나는
https://www.acmicpc.net/problem/2252기본적인 위상 정렬 문제이다.문제 로직상 사이클이 없는 단방향 그래프이므로 유추가능하다.
https://www.acmicpc.net/problem/8111modular 연산의 성질과 BFS를 이용하여 풀이하였다.문제에서 0과 1로 구성된 숫자를 체크하여 mod N 값이 0인 숫자를 찾아야한다. 따라서 큐를 이용하여 1부터 현재 숫자x10 / 현재
https://www.acmicpc.net/problem/16952조금 구현이 복잡한 BFS 정도이다. bfs를 진행하며 가지치기를 위해 방문체크를 하였는데 체크에 사용된 배열 설명은 아래와 같다. chkx좌표y좌표현재 도달한 번호 = 말 바꾼 횟수 방문 체크
https://www.acmicpc.net/problem/1385벌집을 구현하는 것이 조금 어려운 BFS이다. (bfs알고리즘은 단순)벌집 구현 하기벌집은 2차원 행렬로 표현이 가능하다. 벌집을 구현하기 위한 메모리 크기 고려 \- 6가지 방향 중 한 방향을
https://www.acmicpc.net/problem/1695펠린드롬 관련 문제가 좀 생소해서 헤맸다.. 다이나믹 프로그래밍 문제관련 점화식은 아래와 같다.DPa : 인덱스 a 부터 b까지 수열에 최소로 끼워 넣어야하는 숫자의 갯수arra == arrb 일
문제 설명 https://www.acmicpc.net/problem/1089 문제 풀이 우선 각 자리 수에 올수있는 숫자 여부를 판별하여 배열에 넣어준다 >boolean possiblen : n번 자리에 m숫자가 가능한지 여부 저장 이제 결과를 구하기 위해 전체합,
https://www.acmicpc.net/problem/11664이분 탐색을 좀 변형하여 풀이하였다.lo = A좌표, hi = B좌표로 둔 후에 이분탐색을 진행하되 아래 조건대로 진행하였다.(lo -> C거리) < (hi -> C 거리) 일 경우 : h
https://www.acmicpc.net/problem/2110이분 탐색을 이용하여 풀이하였다.이분 탐색의 원리는 다음과 같다.instaill (int length) 특정 최소거리 n이 있을때 설치할 수 있는 공유기 갯수는 m개로 정해진다. 집 좌표 arr를
https://www.acmicpc.net/problem/1939우선 BFS를 이용해 풀이해 보았다. \- 방문탐색으로 해당 노드에 방문할 수 있는 최대 중량 보다 작으면 진입 막음. \- 해당 방식을 이용하면 메모리 초과 및 시간 초과가 발생한다
https://www.acmicpc.net/problem/1300이분탐색을 이용하여 풀이하였다. 이분탐색의 대상은 몇번째인지가 아닌 어떤 수인지이며 해당 수를 이용하여 다음을 판별하였다Count(int n) //해당 수보다 같거나 작은 수의 갯수 Count(
https://www.acmicpc.net/problem/1561이분탐색을 이용하여 풀이하였다. 이분탐색의 대상은 특정 시간에 마지막 아이를 태울 수 있는지 여부로 판별하였다.cal(long t) : 특정 시간에 해당 아이를 태우면 0, 이전에 태우면 -1,
https://www.acmicpc.net/problem/1981이분탐색을 이용하여 풀이하였다. 이분탐색의 대상은 최댓값과 최솟값의 차이의 크기이다.특정 차이에 대해 모든 가능한 최소, 최대값을 지정하고 BFS를 돌려 \- 가능하면 hi = mid (최댓
https://www.acmicpc.net/problem/5052trie 자료구조를 이용하여 풀이하였다. 우선 문자열들을 길이순으로 정렬해주어야한다. (길이가 짧은 문자열을 먼저 넣어야 판별가능)특정 문자열을 넣어줄때 마다 해당 문자열의 가능한 subStrin
https://school.programmers.co.kr/learn/courses/30/lessons/138475?language=java문제의 핵심은 start <= n <= end 인 n이 억억단에 등장하는 횟수는 n의 약수의 개수와 같다는 것
https://school.programmers.co.kr/learn/courses/30/lessons/136797?language=java해당 문제는 브루트포스를 이용할 경우 2^100000 경우의 수가 나오기 때문에 시간초과가 발생한다.다이나믹 프로그래밍을
https://www.acmicpc.net/problem/16934trie 자료구조를 이용하여 풀이하였다. trie insert 함수를 활용해서 insert시 해당 닉네임 별칭을 리턴하도록 구현하였다.Node의 isEnd 변수를 int로 놓고 해당 노드에서 i
https://school.programmers.co.kr/learn/courses/30/lessons/132266dijkstra로 풀어도 되고, 간선 가중치가 모두 1이므로 BFS로 풀어도 무방하다.문제의 핵심은 각 source로 부터 destination까
https://school.programmers.co.kr/learn/courses/30/lessons/131703?language=java브루트 포스로 풀이할 경우 시간초과 발생하진 않을 것 같지만..? 좀 더 효율적으로 풀이하였다.생각한 풀이는 다음과 같다
https://school.programmers.co.kr/learn/courses/30/lessons/131129처음엔 조건만 잘 구분하여 조건문으로 끝낼 수 있으려나 했지만 역시 쉽지 않았다.DP를 이용하여 풀이하였다.int\[] solve(int rema
https://school.programmers.co.kr/learn/courses/30/lessons/118669문제를 풀기 위해 사용했던 인사이트는 다음과 같다. 왕복을 구할 필요 없이 정상까지 편도 최소값을 구하면 된다. (시작점 -> 정상 최소값 <
https://school.programmers.co.kr/learn/courses/30/lessons/118668다이나믹 프로그래밍을 통해 풀이하였다.사용된 점화식은 다음과 같다.dp알고력코딩력 = 현재 알고력, 코딩력에서 모든 문제를 다풀기 위해 사용할 최
https://school.programmers.co.kr/learn/courses/30/lessons/92343DFS를 이용하여 풀이하였다.우선 노드간의 이동은 양방향이동을 전제로 하였다.DFS를 진행하며 2개의 방문체크를 해주었다.visitedN : 진행하
https://school.programmers.co.kr/learn/courses/30/lessons/92344구간합을 이용하여 풀이하였다. 우선 일반적으로 풀이한다면 시간 복잡도는 O(가로x세로x스킬갯수)가 되므로 시간초과가 발생한다.결국 스킬을 사용하며
https://school.programmers.co.kr/learn/courses/30/lessons/42628우선 순위큐 2개를 이용하여 풀이하였다. max heap 역할을 하는 큐를 하나 생성한다.각 명령어에 대한 로직인 다음과 같다. Insert일 경우
https://school.programmers.co.kr/learn/courses/30/lessons/43105간단한 다이나믹 프로그래밍 문제이다. dpx : x로우, y칼럼에서부터 바닥까지 경로의 합중 최대값
https://school.programmers.co.kr/learn/courses/30/lessons/42892기본 그래프 이론과 재귀를 이용해여 풀이하였다. 풀이 순서는 다음과 같다. 1\. 이진 트리 만들기 2\. 전위 순회, 후위 순회 결
https://school.programmers.co.kr/learn/courses/30/lessons/64062초기 접근은 배열의 최솟값을 전체에 빼주고 연속된 0의 갯수를 판별하여 가능 여부를 판별하였는데 이 방법은 최악의 경우 20만 x 20만으로 시간
https://school.programmers.co.kr/learn/courses/30/lessons/72413플로이드 워셜 알고리즘을 이용하여 풀이하였다.결과 도출을 위한 과정은 다음과 같다.플로이드 워셜 알고리즘을 이용해 모든 노드 사이의 최소 거리를 구
https://school.programmers.co.kr/learn/courses/30/lessons/64064간단한 DFS 문제였다. 배열의 길이가 최대 8밖에 되지 않기 때문에 ban id에 매칭되는 user id 맵을 만들어주고 dfs를 진행하며 각 b
https://school.programmers.co.kr/learn/courses/30/lessons/60063상세한 구현이 필요한 BFS 문제이다. 단순 상하 좌우 이동 외에 회전 이동이 있기 때문에 BFS에서 각 status를 다음과 같이 표시했다.Poi
https://school.programmers.co.kr/learn/courses/30/lessons/76503- 예상치 못한 함정으로 살짝 까다로웠던 문제였다.처음 접근은 특정 노드 부터 시작하여 DFS로 풀이하였다. 하지만 최악의 경우 DFS의 depth
https://school.programmers.co.kr/learn/courses/30/lessons/77486DFS로 풀이하였다. 크게 2가지 함정이 존재하였다.일반적인 DFS처럼 각 노드를 1번만 방문하도록 구현해서는 안된다. 특정 노드에 하위 2개의 노
https://school.programmers.co.kr/learn/courses/30/lessons/1832간단한 DFS + DP 문제였다Bottom-Up 방식으로 구현하였는데 그나마 특별한 점은 DP배열을 DPX가 아닌 DPX들어온방향으로 구성해줘야 한다
https://school.programmers.co.kr/learn/courses/30/lessons/42893문자열 핸들링 문제였다. 각각에 대해 url, 링크를 파싱해서 결과를 점수를 계산하면 된다.
https://school.programmers.co.kr/learn/courses/30/lessons/12920이분탐색으로 풀이하였다.시간을 기준으로 이분탐색으로 줄이고 늘려가며 마지막 작업이 진행되는 시간을 찾고 시간을 찾으면 마지막 작업을 수행하는 코어
https://school.programmers.co.kr/learn/courses/30/lessons/1837다이나믹 프로그래밍으로 풀이하였다. 점화식은 다음과 같다. DPN : 시간이 T이고 해당 노드가 N일때, 이후 목적지까지 최소 수정 갯수DPNT 모든
https://school.programmers.co.kr/learn/courses/30/lessons/1836- BFS로 풀이하였다. 시간복잡도 자체는 타이트하지 않아서 쉽게 생각했지만 구현이 조금은 복잡해서 잔실수가 많이 나왔다. 기억나는 실수들 \-
https://school.programmers.co.kr/learn/courses/30/lessons/150367DFS로 풀이 하였다. 문제는 크게 2단계로 구성된다. 특정수를 포화이진트리 크기에 맞게 이진수로 변경 (포화이진트리 이진수이라 명명)DFS로 포
https://school.programmers.co.kr/learn/courses/30/lessons/150366UNION-FIND 알고리즘을 이용하여 풀이하였다.병합된 노드는 최상단 부모 노드만 값을 가지도록 구현하였다.병합 해제시, 조심해야할 부분은 모든
https://school.programmers.co.kr/learn/courses/30/lessons/92345DFS를 이용하여 풀이하였다. 우선 DFS 결과값은 양수, 음수로 나뉘는데 결과값 기준은 다음과 같다.승리한 분기'가' 있으면 승리한 분기 중 가장
https://school.programmers.co.kr/learn/courses/30/lessons/17678직관적으로 이분 탐색을 이용하여 풀이하였다.콘의 도착시간을 기준으로 이분 탐색을 시행하고 탈 수 있는 시간의 최대값을 구한다. 이분 탐색에 앞서 각
https://school.programmers.co.kr/learn/courses/30/lessons/42579자료구조와 정렬을 이용하여 풀이하였다.크게 아래 2단계로 이뤄진다.Map<장르명, 총재생수>, Map<장르명, List<곡정보>>
https://school.programmers.co.kr/learn/courses/30/lessons/42895DP를 이용하여 풀이하였다.DPK = K자리로 만들 수 있는 수들을 모아논 리스트DP1 ~ DP8 까지 차례대로 구해보며 점화식을 도출해보자.DP1
https://school.programmers.co.kr/learn/courses/30/lessons/43163BFS를 이용하여 풀이하였다.각 단어의 인덱스를 번호로 두고 각 번호끼리 이동할 수 있는 Map을 만들어 준다. (한글자만 다른지 확인)begin에
https://school.programmers.co.kr/learn/courses/30/lessons/87694BFS를 이용하여 풀이하였다.문제의 풀이 순서는 간단하다격자를 만들고 직사각형에 해당하는 칸을 1로 치환해준다.시작점에서 BFS를 수행하되 다음칸에
https://school.programmers.co.kr/learn/courses/30/lessons/68646완전 탐색은 불가능 하다.문제의 조건에서 알 수 있는 사실은 특정 풍선 좌, 우측으로 해당 수보다 작은 수가 존재하면 해당 풍선은 마지막까지 존재할
https://school.programmers.co.kr/learn/courses/30/lessons/12942다이나믹 프로그래밍으로 풀이하였다.한가지 알아야할 사전지식은 행렬곱셈에서 결합법칙은 성립하지만 교환법칙은 성립하지 않는다는 것이다. (행렬의 순서는
https://school.programmers.co.kr/learn/courses/30/lessons/12987그리디스러운 아이디어가 필요한 문제이다.아이디어는 다음과 같다. (각 A원소에 대해 가장 가까운 큰 수 찾기)우선 A, B를 각각 정순으로 정렬한다
https://school.programmers.co.kr/learn/courses/30/lessons/67258투 포인터 알고리즘을 이용하여 풀이하였다. L, R을 배열의 인덱스 0으로 두고 다음 로직을 수행한다.R을 0 ~ N-1까지 반복한다. \- m
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/150365 문제 풀이 간단한 BFS로 문제였다. BFS로 진행하되 방문체크는 chkx[이동거리]로 진행한다. 이때,진행우선 순위는 사전순으로 (아래, 왼
https://school.programmers.co.kr/learn/courses/30/lessons/42861단순 최소 신장 트리 문제였다.크루스칼 알고리즘으로 풀이하였다.
https://school.programmers.co.kr/learn/courses/30/lessons/67259간단한 BFS로 문제였다. BFS로 진행하되 방문체크는 chkx들어온 방향으로 수행한다.들어온 방향에 따라 다음 3가지 케이스로 나누어 진행한다.
https://school.programmers.co.kr/learn/courses/30/lessons/49191DFS를 이용하여 풀이하였다.문제의 가장 큰 인사이트는 선수 간의 관계를 단방향 그래프로 나태냈을때, 그래프에서 특정 선수와 다른 모든 선수가 도달
https://school.programmers.co.kr/learn/courses/30/lessons/81303효율성 테스트가 까다로운 문제였다. 일반적으로 문자열에 대한 이해만 있다면 정확성 테스트는 쉽게 통과가 가능하다. 처음엔 결과 배열만 놓고 인덱스를
https://school.programmers.co.kr/learn/courses/30/lessons/60061구현이 조금 까다로운 문제였다. 구현을 간단히 하기 위해 크게 2가지 인사이트가 사용되었다. 설치와 삭제 가능 여부를 하나의 함수로 통일하였다.
https://school.programmers.co.kr/learn/courses/30/lessons/72414구간합을 이용하여 풀이하였다.문제는 다음과 같은 방향으로 풀이하였다. 시간 배열을 두고 각 시간에 시청자 수를 구한다. 가능한 범위를 순회하면서 특
https://school.programmers.co.kr/learn/courses/30/lessons/161988- 구간합, 투포인터 알고리즘을 이용하여 풀이하였다. 우선 brute force 사용시 50만 \* 50만 정도 복잡도로 시간초과가 발생한다.다음
https://school.programmers.co.kr/learn/courses/30/lessons/60062DFS, 비트마스킹을 이용하여 풀이하였다. 문제 풀이 방법은 다음과 같다. 모든 취약지점 간의 거리를 인접행렬로 정의 (시계, 반시계 한쪽 방향으로
https://school.programmers.co.kr/learn/courses/30/lessons/70130특정 숫자(num)를 교집합으로 하는 스타 수열의 집합 갯수는 아래처럼 구할 수 있다. a 배열의 길이와 동일한 chk 배열을 준비한다.a 배열을
https://school.programmers.co.kr/learn/courses/30/lessons/72415BFS, DFS(순열)을 이용하여 풀이하였다.순열을 이용한 전체적인 큰 틀은 다음과 같다. dfs(int ind, int tmpRes, int r,
https://school.programmers.co.kr/learn/courses/30/lessons/87391인사이트가 필요한 구현 문제였다.우선 생각 해야할 것은 완전탐색(DFS, BFS)으로 좌표 1개 단위로 풀이를 진행하면 무조건 시간초과가 난다는 점
https://school.programmers.co.kr/learn/courses/30/lessons/86053결정 함수 구현이 좀 복잡한 이분 탐색문제였다. 이분 탐색은 시간을 기준으로 동작시켰고 시간의 최소값은 0, 최대값은 20억(a+b의 최대값) \*
https://school.programmers.co.kr/learn/courses/30/lessons/133500트리를 이용한 DFS를 이용하여 풀이하였다. 우선 전체 노드 연결 상태를 루트가 1인 트리라고 생각한다. (사이클X)DFS 진행은 다음과 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/131702DFS를 이용하여 풀이하였다.우선 brute Force 사용하되 특정 아이디어가 필요하다. (단순하게 전체 경우의 수는 4^64)첫번째행의 각 칼
https://school.programmers.co.kr/learn/courses/30/lessons/1838구간합, BruteForce를 이용해 풀이하였다.풀이 순서는 다음과 같다. 가장 많이 겹치는 인원이 몇인지 확인 해당 인원에 대해 최대 거리로 배치하
https://school.programmers.co.kr/learn/courses/30/lessons/64063HashMap을 이용하여 풀이하였다. 가장 큰 문제는 방번호의 범위가 너무 크다는 점이다 (1조) 풀이는 다음과 같다. HashMap에 (key,
https://school.programmers.co.kr/learn/courses/30/lessons/42891이분 탐색을 이용하여 풀이하였다. 풀이의 아이디어는 다음과 같다. 이분 탐색의 기준은 원판의 회전 수이다. 구하고자하는 값은 특정 회전일때 K시간
https://school.programmers.co.kr/learn/courses/30/lessons/17685Trie를 이용한 트리 자료구조로 풀이하였다. 풀이는 다음과 같다. 기본 Trie를 변형하여 각 노드가 이전 노드를 기억하는 Trie에 모든 문자열
https://school.programmers.co.kr/learn/courses/30/lessons/49995누적합과 이분 탐색을 이용하여 풀이하였다. 우선 이중 for문으로 L과 R값을 정해준다. L,R이 정해지면 L~M, M+1~R을 나눌 M을 정해야하
https://school.programmers.co.kr/learn/courses/30/lessons/43236이분 탐색을 이용하여 풀이하였다. 이분 탐색의 대상은 돌 사이의 거리이다. 0 ~ distance 사이에서 이분 탐색을 진행하는데 특정 돌 사이의
https://school.programmers.co.kr/learn/courses/30/lessons/60060트라이를 이용하여 풀이하였다. 일반적인 트라이를 사용하되 단어의 정순, 역순 트라이를 각각 생성하여 가사를 insert할 때 각각 insert 해준
https://leetcode.com/problems/design-a-food-rating-system/description/해쉬맵 자료구조와 우선순위큐를 이용하여 풀이하였다.두가지 해쉬맵을 유지한다. Map<String, PriorityQueue> ty
https://leetcode.com/problems/design-a-food-rating-system/description/해쉬맵 자료구조와 우선순위큐를 이용하여 풀이하였다.두가지 해쉬맵을 유지한다. Map<String, PriorityQueue> ty
https://school.programmers.co.kr/learn/courses/30/lessons/12983DP를 이용하여 풀이하였다. 우선 HashSet 자료구조를 이용하여 후보 단어들을 저장하였다. (존재 여부 확인 O(1))후보 단어들의 길이가 1이
https://school.programmers.co.kr/learn/courses/30/lessons/42894구현 문제이다. 우선, 각 블록에 대해 모양을 특정하는 건 복잡하므로 특정 블록을 감싸는 직사각형의 ROW, COL 범위를 해당 블록 정보로 저장해
https://school.programmers.co.kr/learn/courses/30/lessons/67260복잡한 BFS 문제이다. 우선 BFS를 진행하기에 앞서 다음 초기화를 진행해준다. \- List<List<Integer>> map :
https://school.programmers.co.kr/learn/courses/30/lessons/12984두가지 풀이가 존재한다. 1)이분 탐색 2)쉬운 아이디어우선 문제에서 존재하는 블록의 높이의 범위를 min ~ max라고하고 블록을 n개로 맞추었을
https://school.programmers.co.kr/learn/courses/30/lessons/68937트리, BFS, 중간값에 대한 이해가 필요한 문제이다.중간값이란 세개의 수를 정렬했을 때 2번째 수를 뜻한다 (!=평균값)트리의 중요한 특징은 다음
https://school.programmers.co.kr/learn/courses/30/lessons/62050BFS, Heap을 이용하여 풀이하였다.풀이는 다음과 같다. BFS를 위한 Queue와 사다리를 설치할 후보를 넣어줄 높이 차이로 정렬된 Prior
https://school.programmers.co.kr/learn/courses/30/lessons/1843DP를 이용하여 풀이하였다. DP 배열의 정의는 다음과 같다.DPa0 : 숫자 배열의 인덱스 a~b 범위의 연산의 최소값DPa1 : 숫자 배열의 인덱
https://school.programmers.co.kr/learn/courses/30/lessons/72416DP를 이용하여 풀이하였다. 난이도가 꽤 있었던 문제..우선 전체 관계를 트리 형태로 정리한다. DP배열의 정의는 다음과 같다. DP노드 번호 :
https://school.programmers.co.kr/learn/courses/30/lessons/118670Deque는 이용했지만 아이디어에 한계의 부딪혀 풀이를 참조하였다.자료구조를 극한으로 활용하는 문제가 아닐까 싶다.다음 그림과 같이 행렬을 분해한
https://www.acmicpc.net/problem/2357세그먼트 트리를 이용하여 풀이하였다. 구간의 최대, 최소를 O(n)으로 탐색하며 풀면 당연히 시간초과가 발생한다. 구간의 최소값을 저장하는 세그먼트 트리와, 구간의 최대값을 저장하는 세그먼트 트리
https://www.acmicpc.net/problem/1016에라토스테네스의 체를 응용하여 풀이하였다.문제 풀이는 다음과 같다.min~max 값을 저장하는 배열을 생성한다. (최대 길이 10^6) 특정 숫자의 제곱수의 배수가 해당 범위 내에 있을 때, 그
https://www.acmicpc.net/problem/2263트리에서 인오더, 프리오더, 포스트오더의 성질을 이용하여 풀이하였다.인오더 순서의 특징은 루트 노드의 인덱스를 기준으로 왼쪽값들은 왼쪽 자식 트리, 오른쪽값들은 오른쪽 자식 트리가 된다.포스트오더
https://www.acmicpc.net/problem/6549세그먼트 트리 + 분할 정복을 이용하여 풀이하였다.우선 세그먼트 트리를 이용하여 특정 구간의 가장 높이가 낮은 지점의 인덱스를 저장한다.이제 전체 구간의 최대 넓이를 구해야 하는데 모든 구간을 반
https://www.acmicpc.net/problem/1562비트마스킹 + DP를 이용하여 풀이하였다. 문제에서 DP 최적 부분 구조를 구성할 때 메모이제이션 해야하는 요인은 다음 3가지이다. 현재 자리수 현재까지 0~9까지 숫자의 방문 여부 마지막 수 위
https://www.acmicpc.net/problem/1799최적화가 필요한 백트래킹 문제였다.우선 기본적인 알고리즘 개요는 백트래킹으로 이용하여 첫번째 칸부터 마지막까지 둘 것인지 안 둘 것 인지 정하고 가장 큰 값을 구하는 것이다.문제는 시간복잡도인데,
https://www.acmicpc.net/problem/2887최소 신장 트리를 사용하여 풀이하였다.우선 최소 신장 트리 알고리즘을 프림(N^2), 크루스칼(ElogE) 두가지가 존재한다.간선의 갯수를 고려해 시간복잡도가 낮은 알고리즘을 택해야 한다문제에서
https://www.acmicpc.net/problem/11003데크 자료구조를 이용하여 풀이하였다. 데크의 구조는 아래와 같다. deque<Integer, Integer> : 데크에 (인덱스, 값) 형태로 저장 deque0 : 구간 내 최소값 저장 d
https://www.acmicpc.net/problem/1517문제는 버블 소트의 SWAP 횟수를 필요로 하지만 버블소트를 사용하면 O(N^2) 시간복잡도로 시간초과가 발생한다. 문제는 O(NlogN)알고리즘인 머지소트를 진행하여 SWAP 횟수를 계산하여 풀
https://www.acmicpc.net/problem/2150SCC 문제의 선형시간 풀이를 위한 알고리즘인 코사라주, 타잔 알고리즘 중 타잔 알고리즘을 사용하였다.각 노드에 대해 DFS를 진행하되 스택에 노드를 넣어주고 DFS 진행 순으로 각 노드에 증가하
https://www.acmicpc.net/problem/2213다이나믹 프로그래밍으로 풀이하였다. 트리에서 DP를 사용하는 가장 대표적인 문제라고 볼 수 있다.점화식은 다음과 같이 구성된다.DPN : N번노드를 미포함하고 N번 노드를 루트로 하는 독립집합의
https://www.acmicpc.net/problem/14428기본적인 세그먼트 트리 문제이다. 세그먼트 트리 엘리먼트로는 (index, value)를 포함한 객체를 넣어준 후 문제 조건에 맞게 작은값으로 비교하는 연산을 거쳐 세그먼트 트리 로직을 수행한다
https://www.acmicpc.net/problem/5676기본적인 세그먼트 트리 문제이다. 곱 연산은 Long 자료형으로 저장하더라도 오버플로우가 날 수 있기 때문에 결과에 필요한 부호만 저장하는 로직을 사용해야 한다.
https://school.programmers.co.kr/learn/courses/30/lessons/1839생각이 필요한 BFS 문제이다. BFS의 큐대신에 대화시간이 작을수록 우선하는 우선순위큐를 이용해서 BFS를 진행한다.위 행위의 의미는 대화시간의 제
https://www.acmicpc.net/problem/1311우선 bruteforce로 풀기에는 20!의 경우의 수가 나오므로 불가능하다.비트마스킹을 이용한 DP를 이용하여 풀이하였다.DP테이블 정의는 다음과 같다. DP현재까지 선택한 일의 조합 : 현재
https://www.acmicpc.net/problem/12850BruteForce나 DP로 풀기에는 D의 최대값이 10억이기 때문에 불가하다.문제를 풀기 위해서는 아래와 같은 인사이트가 필요하다.문제의 노드간의 인접행렬을 표현하면 mapa는 a->b로 가는
https://www.acmicpc.net/problem/15644유서 깊은 복잡한 구현 + BFS 문제이다.구슬들의 위치, 횟수, 이동 루트를 큐에 넣어서 BFS를 진행한다.구슬들의 위치, 방향에 따라 빨간 구슬을 먼저 움직일지, 파란 구슬을 먼저 움직일지를
https://www.acmicpc.net/problem/2307다익스트라 알고리즘을 반복해서 수행하면 된다.우선 1 -> N까지 최단 경로를 구한 후, 주어진 edge들을 하나씩 소거하면서 최단 경로를 구해준 후 최대 지연 시간을 구하면 된다.
https://www.acmicpc.net/problem/17371그리디한 방식으로 BruteForce를 진행하면 된다.문제에서 가장가까운 거리, 가장 먼 거리의 평균을 구한다고 했는데 편의시설 지점을 정답 후보로 두게되면 가장가까운 거리는 0으로 소거가 가능
https://www.acmicpc.net/problem/1800그래프를 BFS로 탐색하며 DP를 사용해 풀이하였다.점화식은 아래와 같다 DPN : N번 노드까지 K개의 공짜 케이블을 썼을 때 비용 최소값 BFS로 탐색하며 현재 상태에서 공짜 케이블을 쓰는 케
https://www.acmicpc.net/problem/18500복잡한 시뮬레이션 문제이다. 풀이는 다음 과정으로 이뤄진다. 블록 제거 클러스터 생성 클러스터 떠있는지 판별 후 떨어뜨리기 클러스터 생성에는 BFS를 사용하였다.클러스터가 떠있는지 판별하기 위해
https://www.acmicpc.net/problem/4716정렬 및 그리디한 접근을 이용해 풀이하였다.문제에서 중요한 정렬의 조건의 경우 A와의 거리, B와의 거리 차이를 기준으로 내림차순 정렬을 진행하여 차이가 큰 것부터 가까운 풍선을 우선적으로 나르면
https://www.acmicpc.net/problem/16991외판원 순회 문제는 다이나믹 프로그래밍을 사용하는 것이 정석이다.DP현재노드위 배열을 통해 메모이제이션을 진행하며 BFS를 진행하여 풀이하였다.
https://www.acmicpc.net/problem/13392다이나믹 프로그래밍으로 풀이하였다.아래 점화식을 통해 메모이제이션하며 DFS를 진행했다.DPN : 이전 왼쪽 회전수가 정해져있을때, N번째 숫자부터 맞추기 위한 최소 회전값
https://www.acmicpc.net/problem/14908문제 조건에 맞게 그리디한 정렬을 이용하여 풀이하였다.작업을 정렬할 때 다음과 같은 비교 기준을 사용한다. 1번 작업과 2번작업을 비교할 때 다음을 기준으로 비교한다. \- T1 x S2 :
https://www.acmicpc.net/problem/2423Gold 1풀이때는 단순히 DP로 생각하여 풀었는데 풀고나니 다익스트라 알고리즘이라 놀랐다..다익스트라 알고리즘으로 접근할 수 있다.우선 격자의 모서리를 좌표로 고려하여 (0,0) -> (N,M)
https://www.acmicpc.net/problem/1450Gold 1문제는 일반적인 0/1 냅색으로 풀이할 수 없다. (공간복잡도가 너무큼)또한 완전 탐색은 2^30 가지수가 나오므로 시간복잡도를 초과한다. Meet in the middle(중간에서 만
https://www.acmicpc.net/problem/28707Gold 1다익스트라 알고리즘을 이용하여 풀이하였다.배열을 십진법 형태로 변환하여 int값을 가지는 노드라고 생각한다.시작 노드에서 마지막 노드(정렬된 값)까지의 최단 코스트를 구하면 된다. 자
https://www.acmicpc.net/problem/14570Gold 1단순 시뮬레이션 혹은 DFS 문제이다.문제에서 K값은 매우 크므로 한개씩 시뮬레이션은 불가하다.문제에서 K개 구슬이 특정 노드에 도착했을 때 시나리오는 다음과 같다.자식 노드가 없을때
https://www.acmicpc.net/problem/14578Gold 1DP를 이용하여 풀이하였다.1번 행부터 N번 행까지 파란 색을 선택하는 경우의 수 : N!파란색을 정해놓고 각 행이 서로 다른 열의 빨간색을 선택 하는 경우의 수 -> 교란 순열 DP
https://www.acmicpc.net/problem/2001Gold 1비트마스킹을 통한 BFS를 통해 풀이가 가능하다. 방문 체크는 아래 배열을 통해서 진행한다. visitedNbitmasking : N번 노드를 특정 보석 조합(bitmasking)을 들
https://www.acmicpc.net/problem/1766Gold 2풀이시간 : 10분 위상 정렬을 조금 변형한 문제이다. 위상 정렬에 사용할 큐를 문제 번호 기준 오름차순 정렬하는 우선순위 큐를 사용한다. 풀이 순서는 아래와 같다.진입 차수가 0인 노
https://www.acmicpc.net/problem/2923Gold 1풀이시간 : 25분 그리디한 접근과 투 포인터를 이용하여 풀이하였다.우선 문제에서 특정 두 집단의 합의 최대의 최소값을 구하려면 한 집단에서는 오름차순, 한 집단에서는 내림차순 정렬하여
https://www.acmicpc.net/problem/11779Gold 3풀이시간 : 25분 기본적인 다익스트라 알고리즘에 경로 역추적 문제이다.다익스트라 알고리즘을 사용하되 특정 노드에 이전 노드를 저장하는 배열을 두고 최종적으로 해당 배열을 탐색하며 경
https://www.acmicpc.net/problem/12738Gold 2풀이시간 : 20분 전통적인 다이나믹 프로그래밍이다. LIS 풀이는 O(N^2), O(NlogN)알고리즘이 존재하지만 이 문제에선 후자를 사용해야한다.각 방법별 풀이는 아래와 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/340210LV3풀이시간 : 55분 생소한 진법 문제였다. 알고리즘에 try, catch는 처음 쓰는듯..우선 2~9진법의 타당성 여부를 저장하기 위한 배열
https://www.acmicpc.net/problem/1516Gold 3소요 시간 : 16분위상 정렬을 이용하여 풀이하였다. 위상 정렬을 이용하되 특정 노드의 최대 시작 가능 시간(이전 건물 중 가장 마지막으로 건설을 끝낸 시간)을 배열로 두어 갱신해주며
https://www.acmicpc.net/problem/2352Gold 2소요 시간 : 12분LIS 문제이다. DP로 풀이하였다. 문제에서 N의 범위가 40000이므로 O(NlogN)알고리즘을 이용해야 한다. 이전 포스팅 설명 참조
https://www.acmicpc.net/problem/2099Gold 1소요 시간 : 40분지목된 상태 그래프를 인접행렬 형태로 나타내고 행렬의 거듭제곱을 사용해서 풀이하였다.우선 K <= 100만 이므로, 최대 19승까지 인접행렬 거듭제곱 값을 저장
https://www.acmicpc.net/problem/11437Gold 3소요 시간 : 11분 일반적인 LCA 문제이다. O(N) 알고리즘을 사용해도 괜찮아 보여서 사용했다. 풀이는 아래와 같다. 트리를 루트부터 DFS를 진행하여 각 노드의 깊이, 부모 노
https://www.acmicpc.net/problem/28707LV 2이분 탐색을 사용하였다. 0~10만까지 범위의 level 내에서 각 level이 valid한지를 판별하는 함수를 통해 이분탐색을 진행하면 풀이가 가능하다.
https://www.acmicpc.net/problem/7579Gold 3소요 시간 : 10분 냅색 문제이다. 결과가 최소 비용이라 직관적이지 않을 수 있지만 아래와 같이 dp테이블을 정의하면 냅색 문제가 된다.DPi : i번째 앱까지 j만큼 비용을 사용할
https://www.acmicpc.net/problem/2623Gold 3소요 시간 : 15분 위상 정렬을 이용하여 풀이하였다.입력에서 각 노드의 진입차수와 그래프(간선 : 이전가수->다음가수)를 정해준다. 해당 데이터를 바탕으로 위상정렬을 진행하되 결과의
https://www.acmicpc.net/problem/14554Gold 1소요 시간 : 30분 다익스트라 알고리즘과 DFS를 사용해 풀이하였다.우선 다익스트라 알고리즘을 이용해 S노드와 다른 노드 간의 최단거리를 모두 구해준다.DFS를 이용해 Top-dow
https://www.acmicpc.net/problem/10986Gold 3구간합 및 수학적 접근으로 풀이문제의 인사이트는 다음과 같다 \- 구간합 Si에 대해 (i,j) 구간합이 M으로 나눠지려면 (Sj - Si-1)%M = 0Sj%M = Si-1%M인
문제 설명 https://www.acmicpc.net/problem/10986 Gold 3 문제 풀이 구간합 및 수학적 접근으로 풀이 문제의 인사이트는 다음과 같다 구간합 S[i]에 대해 (i,j) 구간합이 M으로 나눠지려면 (S[j] - S[i-1])%M =
https://www.acmicpc.net/problem/1865Gold 3플로이드 워셜 알고리즘으로 모든 노드간의 최소 거리를 구해주었다.결과는 mapi < 0 인 노드가 있으면 분기해서 출력해주었다.
https://www.acmicpc.net/problem/1781Gold 2소요 시간 : 25분우선 입력을 배열로 만들고 데드라인 오름차순, 보상개수 내림차순으로 정렬한다.배열 앞에서 부터 컵라면 개수를 대상으로하는 우선순위 큐에 보상개수를 넣어주되 큐 사이즈
https://www.acmicpc.net/problem/1489Gold 1소요 시간 : 25분그리디하게 풀이하였다. 문제에서 특정 A가 특정 B를 이길 때 가장 근소한 차이로 이겨야만 이후 진행하는 A에 대해서 적은 영향을 줄 수 있다.위 인사이트를 기반으로
https://www.acmicpc.net/problem/2812Gold 3풀이시간 : 40분 그리디한 접근과 스택 자료구조를 이용하였다.먼저 특정 배열에서 1자리를 뺄 때 가장 큰 숫자를 만드는 방법은 맨 앞에서 부터 비교하며 처음 다음 자리수보다 작아지는
https://www.acmicpc.net/problem/1949Gold 2풀이 시간 : 40분 dfs를 이용한 DP문제이다. DP 테이블을 아래와 같이 두고 Top-down 방식의 재귀를 사용한다.DPi : i노드를 j 마을로 지정했을 때 하위 트리에서의 점
https://school.programmers.co.kr/learn/courses/30/lessons/214289문제를 단순화하지 않으면 복잡해질 수 있는 DP 문제이다. 기본적인 점화식은 다음과 같다. DPa : a분에 b온도를 맞추기 위한 최소 비용 문제