알고리즘 가보자고

백준 10430번 나머지 문제 링크 : https://www.acmicpc.net/problem/10430 나의 풀이 입력 받은 a, b, c를 조건에 따라 첫째줄부터 네번째줄까지 식에 대한 답을 출력하게 하면 된다! 결과 백준 2609번 최대공약수와 최소공배수 문제 링크 : https://www.acmicpc.net/problem/2609 ![](...

백준 1978번 소수 찾기 문제 링크 : https://www.acmicpc.net/problem/1978 나의 풀이 소수인지 아닌지 2부터 루트 N보다 작거나 같은 자연수로 나누어떨어지는지 여부로 판별하는 isPrime 메소드를 이용하여 입력 받은 t가 소수인 경우 count 변수를 증가시키고 마지막에 count를 출력시키게 구현하였다. 결과 19...

10872번 팩토리얼 문제 링크 : https://www.acmicpc.net/problem/10872 나의 풀이 재귀함수를 이용하여서 풀었다. 결과 1676번 팩토리얼 0의 개수 문제 링크 : https://www.acmicpc.net/problem/1676 나의 풀이 n을 5, 5의제곱, 5의 세

백준 9613번 GCD 합 문제 링크 : https://www.acmicpc.net/problem/9613 나의 풀이 2중 포문을 이용해서 각각의 정수 쌍 마다 gcd 함수를 호출하여 sum 변수에 그 결과값을 더해주면 모든 쌍의 GCD 합이 구해진다. 마지막에 sum을 출력시키면 테스트 케이스 마다의 GCD 합을 구할 수 있게 하였다. sum 변수는 ...

백준 1212번 8진수 2진수 문제 링크 : https://www.acmicpc.net/problem/1212 나의 풀이 2진수 8진수 문제를 응용해서 풀면 된다. 결과 백준 2089번 -2진수 문제 링크 : https://www.acmicpc.net/problem/2089 ![](https://velog.ve

백준 10828번 스택 문제 링크 : https://www.acmicpc.net/problem/10828 나의 풀이 스택 라이브러리를 사용해서 구현하였다. 결과 백준 9093번 단어 뒤집기 문제 링크 : https://www.acmicpc.net/problem/9093 ![](https://velog.velcd

백준 1406번 에디터 문제 링크 : https://www.acmicpc.net/problem/1406 나의 풀이 커서 기준 왼쪽에 있는 문자들을 담을 lstack과 커서 기준 오른쪽에 있는 문자들을 담을 rstack 2개의 스택을 생성한다. 그런 다음 명령어를 입력 받기 전에 있던 문자들은 모두 lstack에 push 해준다. for문을 돌면서 명령어...

백준 17413번 단어 뒤집기 2 문제 링크 : https://www.acmicpc.net/problem/17413 나의 풀이 문자열을 뒤집기 위해 스택을 사용하고, 태그에 해당하는 문자인지 아닌지를 구분하기 위해 flag 변수를 사용합니다. 문자열을 for문을 돌려서 태그의 시작인 경우 앞의 문자까지 뒤집어서 출력시켜줘야 하므로 스택에 있는 모든 문자...

백준 17299번 오등큰수 문제 나의 풀이 오큰수 풀이에서 해당 수가 얼마나 등장했는지 횟수를 세는 freq 정수 배열을 선언해줘서 입력 받은 수 마다 등장 횟수를 1 증가시켜주고 while문에서 비교할 때 등장횟수가 현재 값의 등장 횟수 보다 작은 경우 정답 배열에 오등큰수로 저장해주는 방식으로 구현하였다. 결과

백준 1935번 후위 표기식2 문제 나의 풀이 스택을 이용해서 문자가 알파벳인 경우는 스택에 피연산자로써 넣고, 연산자인 경우에는 스택에 있는 피연산자 두개를 pop해서 뽑고 계산해서 다시 스택에 push하는 방식으로 구현하였다. 결과 백준 1918번 후위 표기식 문제 ![](https://velog.velc

백준 10809번 알파벳 찾기 문제 나의 풀이 알파벳들의 위치를 나타낼 arr 변수를 생성하고 Arrays.fill 메소드를 통해 -1로 채워준다. 그런 다음 입력 받은 단어를 for문을 돌려서 단어상에서 문자의 위치를 arr 배열에 저장하고 이를 출력하도록 구현하였다. 결과 백준 10820번 문자열 분석 문

백준 10773번 제로 문제 나의 풀이 스택 자료 구조를 생성한뒤 입력 받은 수가 0인 경우 pop 메소드를 사용해서 가장 최근에 쓴 수를 제거하고, 아닌 경우는 push 메소드를 사용해서 입력 받은 수를 스택에 넣는다. 그런 다음 스택에 있는 수들을 sum 변수에 모두 더해서 출력시켜주면 된다. 결과 백준 249

백준 11655번 ROT13 문제 나의 풀이 문자열을 for문을 돌려서 문자가 대문자나 소문자인 경우 13을 더해주고 범위가 넘어가는 경우에는 26을 빼서 범위 안에 속하도록 하고 그렇게 계산된 문자를 출력시키게 구현하였다. 결과 백준 10824번 네 수 문제 ![](https://velog.velcdn.co

프로그래머스 폰켓몬 문제 나의 풀이 폰켓몬을 종류 중복 없이 저장할 HashSet을 생성한다. 그런 다음 이 set에 폰켓몬의 종류들의 배열의 요소를 추가시킨다. 그렇게 되면 중복 없이 폰켓몬 종류만 남게 된다. 가질 수 있는 폰켓몬 수 보다 이 set의 크기가 큰 경우는 가장 많은 종류의 수는 가질 수 있는 폰켓몬 수가 된다. 아무리 set이 크더라도...

프로그래머스 의상 문제 나의 풀이 해시맵을 생성해서 의상 종류별로 의상들을 구분해주어 저장한다. 그런 다음 map을 for문을 돌려서 key에 해당하는 갯수의 +1한 값을 answer에 곱해줘서 경우의 수를 구한다. 마지막에는 어떤 종류도 입지 않은 경우가 중복되었기 때문에 1을 빼주어 리턴해주면 된다. 결과 ![](https:/

프로그래머스 같은 숫자는 싫어 문제 나의 풀이 숫자를 저장할 스택을 생성한다. 그런 다음 배열을 for문을 돌려서 스택이 비어있는 경우에는 배열의 원소를 push해주고 비어있지 않는데 스택의 최상단에 있는 값과 배열의 i번째 원소가 같지 않다면 연속되는 숫자가 아니기 때문에 push 해준다. 그런 다음 answer에 stack에 있는 값을 넣어주고 리턴...

백준 1021번 회전하는 큐 문제 나의 풀이 2번 연산, 3번 연산을 보면 덱을 이용해야 하는 문제라는 것을 알 수 있다. LinkedList를 이용해서 덱을 생성해주고, 1부터 입력 받은 n까지 요소를 덱에 추가시켜준다. 그런 다음 뽑아내려하는 수들을 arr 배열에 저장시켜준다. 뽑아내려는 수의 개수만큼 for문을 돌리면서 indexOf 메소드의 매개...

백준 1463번 1로 만들기 문제 나의 풀이 D[N] = N을 1로 만드는 최소 연산 횟수 X가 3으로 나누어 떨어지면, 3으로 나눈다. 라는 1번 연산을 수행하는 연산 횟수는 N에서 N/3을 할 때 까지 1번과 N/3에서 1이 될때까지는 D[N/3]이므로 1 + D[N/3]이 된다. X가 2로 나누어 떨어지면, 2로 나눈다. 라는 2번 연산을 수행하...

백준 11052번 카드 구매하기 문제 나의 풀이 D[N] = 카드 N개를 구매하는 비용의 최대값이라고 한다. D[N] = max(D[N - i] + p[i]) 로 점화식을 세울 수 있다. i의 범위는 1 이상 N 이하이다. 결과 백준 16194번 카드 구매하기 2 문제 ![](https://velog.v

백준 10844번 쉬운 계단 수 문제 나의 풀이 DN = 길이가 N인 계단 수. 마지막으로 사용한 수가 L N-1번째에 올 수 있는 수는 L-1, L+1이다. 즉, 경우의 수는 DN-1 + DN-1이다. 하지만 L=0인 경우 L-1을 할 수 없고, L=9인 경우 L+1을 할 수 없기 때문에 예외 처리를 해야 한다. 결과 백준 2193번 이친수 문제 ...

백준 1912번 연속합 문제 나의 풀이 D[i] = i번째 수로 끝나는 가장 큰 연속합 경우의 수는 두가지다. i번째 수가 i-1번째와 연속일 때 D[i] = D[i-1] + A[i] i번째 수가 새로운 연속을 시작할 때 D[i] = A[i] 따라서, D[i] = max(D[i-1] + A[i], A[i])가 된다. 결과 백준 1699번 제곱...

백준 15988번 1,2,3 더하기 3 문제 나의 풀이 기존 1,2,3 더하기 문제에서 100000009으로 나누어주는 연산을 추가해준다. 결과 백준 1149번 RGB거리 문제 ![](https://velog.velcdn.com/images/rosesua318/post/90ba3302-99cb-418d-9ae

백준 11057번 오르막수 문제 나의 풀이 Di = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수 D1 = 1 Di += Di-1 (0 백준 9465번 스티커 문제 ![](https://velog.velcdn.com/images/rosesua

백준 1932번 정수 삼각형 문제 나의 풀이 어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것이다. Di = i행 j열이 선택되었을 때, 최대합 (i, j)가 선택되기 전에 선택된 수는 (i-1,j),(i-1,j-1)중 하나다. => Di = Max(Di-1, Di-1) + Ai 결과 ![](https://velog.ve...

백준 13398번 연속합 2 문제 나의 풀이 D[i] = i번째에서 끝나는 최대 연속합 D2[i] = i번째에서 시작하는 최대 연속합 이 값을 이용해서 A[i]를 제거했을 때 최대 연속합을 구할 수 있다. i번째 수를 제거하면 i-1번째 수와 i+1번째 수가 연속하게 된다. => D[i-1] + D2[i+1]이 i번째 수를 제거했을 때 i번째 수가 포...

자바 계단 오르기 문제 나의 풀이 D[i] = i번째 계단에 도착할 수 있는 방법의 수 한칸 또는 두칸을 오를 수 있기 때문에 D[i]에 오려면 D[i - 1]에서 오거나 D[i - 2]에서 오는 경우 뿐이다. 따라서 이 둘의 경우의 수를 합하면 D[i]의 값이 구해진다. 따라서, 점화식을 정리해보면 D[i] = D[i - 1] + D[i - 2] 이다...

프로그래머스 정수 삼각형 문제 나의 풀이 앞서 풀었던 백준 정수 삼각형과 똑같은 문제이므로 직접 입력 받는 게 아니라 triangle 매개변수를 이용해서 풀면 된다. 결과 프로그래머스 등굣길 문제 ![](https://velog.velcdn.com/images/rosesua318/post/bba1737d-63

백준 2309번 일곱 난쟁이 문제 나의 풀이 9명의 난쟁이 중에서 난쟁이가 아닌 2명을 찾으면 되기 때문에 경우의 수는, 9C2가 되고 36이다. 우선 난쟁이들의 키를 저장할 배열 a를 생성해서 난쟁이 키들을 입력 받아 저장시켜준다. 그와 동시에 sum 변수에 난쟁이들의 키의 합을 구해준다. 배열 a를 정렬하고 i를 0부터 8까지 for문을 돌리고 이중...

백준 14500번 테트로미노 문제 나의 풀이 1x4 블록 경우의 수 2가지, 2x2 블록 경우의 수 1가지, ㄴ 블록 경우의 수 8가지, ㄹ 블록 경우의 수 4가지, ㅜ 블록 경우의 수 4가지로 총 19가지의 블록이 있다고 가정할 수 있다. 어떤 테트로미노 블록을 선택할 것인지를 구하고, 어디에 놓을 것인지 정해야 한다. 총 경우의 수는 19 x N x...

백준 15649번 N과 M (1) 문제 나의 풀이 check 배열과 재귀를 이용해서 풀면 된다. 결과 백준 15650번 N과 M (2) 문제 나의 풀이 N과 M(1)과는 다르게 1부터 n까지의 수를 모두 for문을 돌리는 것이 아니라 start부터 n까지 for문을 돌려서 앞선 index에 채워진 값

백준 10972번 다음 순열 문제 나의 풀이 A[i-1] = i면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다. A[i-1]과 A[j]를 swap한다. A[i]부터 순열을 뒤집는다. 이런 단계를 거치는 다음 순열 함수를 구현해서 해결하면 된다. 결과 ![](https://velog.velcdn.com/images/rosesua318/po...

백준 10819번 차이를 최대로 문제 나의 풀이 배열을 정렬해주고 나서(첫순열인 오름차순을 구하기 위해), 순열을 모두 구하면서 그때마다 나오는 값 중에서 최대값을 구하면 된다. 결과 백준 10971번 외판원 순회 2 문제 ![](https://velog.velcdn.com/images/rosesua318/p

백준 1759번 암호 만들기 문제 나의 풀이 증가하는 순서를 위해 입력 받은 알파벳 배열을 정렬해줘야 한다. 만들어야 하는 암호의 길이 n, 사용할 수 있는 알파벳을 배열로 가지는 alpha, 현재까지 만든 암호 password, 사용할지 말지 결정해야 하는 알파벳의 인덱스 i를 매개변수로 가지는 go 함수를 구현한다. 1) 정답을 찾은 경우 pass...

백준 15661번 링크와 스타트 문제 나의 풀이 스타트와 링크 문제와 동일하게 index번째 사람을 어떤 팀에 넣을지 결정해야 하고, 1번팀과 2번팀에 속한 사람이 각각 first, second에 들어있는 세개의 매개변수로 이루어진 go 함수를 구현해야 한다. 1) 정답을 찾은 경우 index == n 2) 다음 경우 1번 팀 : go(index,...

백준 11723번 집합 문제 나의 풀이 명령문에 따라 적절한 비트연산을 처리해주면 된다. 결과 백준 1182번 부분수열의 합 문제

백준 13023번 ABCDE 문제 나의 풀이 인접행렬, 인접리스트, 간선리스트를 생성한다. 간선리스트를 통해 A->B, C->D를 찾는다. 그런 다음 인접행렬에서 B->C가 있는지 찾고 인접리스트를 이용해 D->E가 있는지 찾는다. 다 찾은 경우에는 1을 리턴해주면 된다. 결과 백준 1260번 DFS와 BFS

백준 2667번 단지번호붙이기 문제 나의 풀이 dfs 탐색을 통해서 단지 개수를 구한 뒤 단지번호마다 개수를 answer 배열을 통해 저장시켜서 이를 출력해주면 된다. 결과 백준 4963번 섬의 개수 문제 ![](https://velog.velcdn.com/images/rosesua318/post/6171e9

백준 7576번 토마토 문제 나의 풀이 bfs 탐색 최단거리 문제로, 미로탐색에서 풀이했던것과 유사하게 하면 된다. 즉, bfs 탐색을 하면서 거리를 재는 방식으로 진행하면 된다. 결과 백준 7562번 나이트의 이동 문제 ![](https://velog.velcdn.com/images/rosesua318/po

백준 16947번 서울 지하철 2호선 문제 나의 풀이 Two Dots 문제에서 했던 것 처럼 사이클을 찾고, 사이클을 찾은 경우 사이클의 시작점을 리턴하게 하고, 사이클을 찾기는 했으나 해당 정점이 사이클에 포함되지 않은 경우 -2를 리턴하게 하여 구분할 수 있도록 한다. 그런 다음 bfs 알고리즘을 통해서 거리를 구해주면 된다. 사이클에 포함되는 정점...

백준 1697번 숨바꼭질 문제 나의 풀이 dist[i] = i를 몇 번만에 방문했는지 여부를 표현한다. bfs 탐색을 통한 최단거리 구하는 방식으로 풀어주면 되는데 현재 정점에서 -1, +1, *2 가 가능한 경우들을 비교해주는 부분이 필요하다. 결과 백준 13913번 숨바꼭질 4 문제 나의 풀이

백준 13549번 숨바꼭질 3 문제 나의 풀이 숨바꼭질 문제와 유사하나, 순간이동 할때 0초가 걸린다는 점이 다르다. 덱을 다루어서 순간 이동은 덱의 앞에, 걷기는 덱의 뒤에 넣는 방법을 사용하면 된다. 결과 백준 1261번 알고스팟 문제 ![](https://velog.velcdn.com/images/ro

백준 1991번 트리 순회 문제 나의 풀이 dfs를 이용하여 전위 순회, 중위 순회, 후위 순회한 결과를 출력시킨다. 순회 방법은 출력문의 위치가 어디냐에 따라 전위 순회, 중위 순회, 후위 순회로 나누어진다. 결과 백준 2250번 트리의 높이와 너비 문제 ![](https://velog.velcdn.com/i

백준 1167번 트리의 지름 문제 나의 풀이 트리의 지름은 탐색 2번으로 구할 수 있다. 한 정점 s에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼거리인 정점은 u라고 한다. u에서 모든 정점까지의 거리를 구한다. 이때 가장 먼 거리인 정점 v를 구한다. u와 v사이의 거리가 트리의 지름이다. 즉, 한 정점 s에서 BFS 탐색을 시작해서 가장 거리...

백준 16928번 뱀과 사다리 게임 문제 나의 풀이 게임에서 뱀과 사다리의 구분은 중요하지만, 구현에서는 별로 중요하지 않다. x->y로 간다는 점만 중요하다. 새로운 배열 next[x]를 만들어서, x에 도착한 이후에 가야할 곳을 모두 기록한다. 뱀이나 사다리인 경우는 next[x] = y, 일반 칸인 경우는 next[x] = x로 구분한다. 결과 ...

백준 12886번 돌 그룹 문제 나의 풀이 돌의 개수들을 입력 받은 뒤, 이들의 합이 3으로 나누어 떨어지지 않으면 돌의 개수를 똑같이 만들 수 없다는 뜻이므로 바로 0을 출력시킨다. 그런 다음 dfs를 이용하여 해결한다. dfs에서는 그룹 1번의 x개, 그룹 2번의 y개에 대하여 방문했다는 것을 check 배열에 표시해준 뒤 for문을 통해서 돌들의 ...

백준 16954번 움직이는 미로 탈출 문제 나의 풀이 몇초가 흘렀는지에 대한 정보도 가지고 있어야 한다. (r-t,c)가 1인지 0인지를 보면 t초후에 벽인지 아닌지 알 수 있다. 그 이유는 t초 후에 (r,c)로 벽이 내려왔다면 그 벽은 (r-t,c)에 있던 벽이기 때문이다. 결과 백준 3055번 탈출 문제

백준 6087번 레이저 통신 문제 나의 풀이 거울을 설치한다는 것은 직선의 방향을 바꾸는 것이라고 볼 수 있다. 거울의 개수는 두 C를 연결하는 데 필요한 직선의 최소 개수에서 -1을 한 것이라고 볼 수 있다. BFS에서 다음 정점을 인접한 네 방향에 있는 점만 넣는 것이 아니고 네 방향에 있는 모든 점을 넣는 방식으로 바꿔서 해결하면 된다. 결과 !...

인프런 청소 문제 나의 풀이 결과

백준 11047번 동전 0 문제 나의 풀이 가장 큰 동전부터 나누어서 개수를 구해주면 된다. 동전의 가치가 배수이기 때문에 그리디로 풀 수 있다. 결과 백준 11399번 ATM 문제 ![](https://velog.velcdn.com/images/rosesua318/post/d9871a9f-7c1d-4216

백준 1202번 보석 도둑 문제 나의 풀이 각각의 가방에 들어갈 수 있는 가장 가격이 높은 보석을 조사하는 방식으로 구현한다. 보석과 가방을 하나로 합치고 무게를 기준으로 오름차순 정렬해서 가방이 나올 때 마다 앞에 있는 보석 중에서 가장 가격이 큰 보석을 정답에 더해주면 된다. 앞에 있는 보석들은 후보로 두게 되는데 이때 우선순위 큐를 이용한다. 결...

백준 1541번 잃어버린 괄호 문제 나의 풀이 최소가 되게 하기 위해선 -를 발견하면 그 뒤에 +가 있는 식들을 괄호로 묶으면 모두 -로 만들 수 있다. 해당 성질을 이용하여 해결해주면 된다. 결과 백준 1744번 수 묶기 문제 ![](https://velog.velcdn.com/images/rosesua3

백준 2875번 대회 or 인턴 문제 나의 풀이 한팀을 만드려면 여학생이 2명 이상이고, 남학생이 1명 이상, 남학생과 여학생의 합이 k에 3을 더한 값 보다 커야 하는 조건들을 만족해야 한다. M+N >= K+3 (팀은 3명이고 인턴은 k명이 해야하기 때문에) 따라서 while 문의 조건으로 m이 2이상이고 n이 1이상이며 m+n이 k+3보다 클때까지...

백준 12904번 A와 B 문제 나의 풀이 맨 마지막 글자가 A라는 것은 A연산을 수행한 것이고, 맨 마지막 글자가 B라는 것은 B연산을 수행한 것이다. T를 S로 만들 수 있는지 보는 문제로 변경해서 해결할 수 있다. 즉, 맨 마지막 글자가 A라면 A 글자를 삭제한다. 맨 마지막 글자가 B라면 B를 삭제하고 뒤집는다. 이렇게 길이가 S와 같아질 때 까...

이분 탐색을 이용하는 방법이기 때문에 다음을 모두 정해야 한다. 가능한 정답의 최솟값(left) 가능한 정답의 최댓값(right) 정답을 하나 결정했을 때, 이것이 문제의 조건에 맞는지 검사하는 방법(go 함수) 조건에 맞는 경우 정답을 더 크게 해야 하는지 작게 해야 하는지 결정 백준 1790번 수 이어 쓰기 2 문제 나의 풀이 N번째 수의 길이는...

백준 2022번 사다리 문제 나의 풀이 삼각형의 닮음을 이용하여 c = h1 x h2 / (h1 + h2)라는 식을 얻게 되고 이를 이용하여 이분 탐색을 한다. 결과 인프런 같은 빈도수 만들기 문제 ![](https://velog.velcdn.com/images/rosesua318/post/d57b18a6-ca

백준 2343번 기타 레슨 문제 나의 풀이 이분탐색으로 찾아야 하는 값은 블루레이의 크기이다. M개의 블루레이에 답을 수 있으면 크기를 작게, 담을 수 없으면 크기를 크게 해서 탐색을 하면 된다. 최소(left)는 레슨 크기의 최대값이고 최대(right)는 레슨 크기의 합이다. go 함수는 크기가 size인 블루레이로 녹화했을 때 M개 이하의 블루레이가...

백준 10815번 숫자 카드 문제 나의 풀이 입력 받은 숫자 카드를 이분 탐색을 통해서 상근이가 가진 카드 중에서 있는지 여부를 판별해서 있으면 1을 출력 없으면 0을 출력하도록 한다. 결과 백준 10816번 숫자 카드 2 문제 ![](https://velog.velcdn.com/images/rosesua318

백준 1780번 종이의 개수 문제 나의 풀이 (x, y)부터 가로로 n개, 세로로 n개의 종이 개수를 확인하는 함수인 solve() 재귀호출하여 해결한다. 부분 문제를 호출하기 전에 같은 수로 되어있는지를 확인해보고 그렇지 않으면 부분 문제를 호출하도록 구현한다. 결과 인프런 서로 다른 빈도수 만들기 문제 ![

인프런 음수가 있는 부분수열 문제 나의 풀이 결과 인프런 회장 선거 문제 나의 풀이 결과

백준 2751번 수 정렬하기 2 문제 나의 풀이 결과 백준 11650번 좌표 정렬하기 문제 ![](https://velog.velcd

백준 10825번 국영수 문제 나의 풀이 비교 함수에서 4가지에 대해서 비교를 해주면 된다. 결과 백준 10989번 수 정렬하기 3 문제 ![](https://velog.velcdn.com/images/rosesua318/post/95989d4c-e25e-4b8c-bccd-8bfc3c6f05b7/image.p

다 해봐야하는데 순서만 변경 가능한 상황에서 순열을 이용한다. 백준 2529번 부등호 문제 나의 풀이 결과 백준 14888번 연산자 끼워넣기 문제 ![](https://velog.velcdn.com/images/rosesua318/post/eddfea44-a39f-4bd6-be0f-1d38607247eb

백준 6603번 로또 문제 나의 풀이 각각의 수를 고른다와 고르지 않는다로 구분하여 모든 조합을 출력하면 된다. go 함수를 구현한다. 매개변수인 a는 입력으로 주어진 수, index는 선택할지 말지 결정해야 하는 인덱스, count는 현재까지 포함한 수의 개수를 뜻한다. 정답을 찾는 경우는 count가 6일 때고, 불가능한 경우는 c

백준 14500번 테트로미노 문제 나의 풀이 하나를 제외한 나머지 테트로미노는 임의의 한 칸에서 시작해서 3개의 칸을 연속해서 방문한 형태이다. 하나의 재귀 함수로는 할 수 없기 때문에 for문으로 살펴본다. 결과 백준 16197번 두 동전 문제 ![](https://velog.velcdn.com/images

백준 9663번 N-Queen 문제 나의 풀이 calc 함수는 row 행에 퀸을 어디에 놓을지 결정하는 함수다. row가 n일 때 모든 행에 퀸을 놓은 것이므로 정답을 1 추가한다. check_col[i] = i번 열에 퀸이 놓여져 있으면 true를 나타낸다. check_dig[i] = / 대각선에 퀸이 있으면 true를 나타낸다. check_dig2[...

인프런 피부과 문제 나의 풀이 결과

인프런 cpu 스케줄링 문제 나의 풀이 우선순위 큐를 이용해서 해결하면 된다. 결과

인프런 가장 많이 사용된 회의실 문제 나의 풀이 결과

인프런 이진수 정렬 문제 나의 풀이 결과 인프런 수열 찾기 문제 나의 풀이 nums에 남은 수 중에 가장 작은 값을 2배한 값을 둘 다 지워주는 것을 반복해서 원래 수열을 찾아준다. 반복하며 남은 수 중에 가장 작은 값들을 answer의 원소로 추가하면 된다. 결과 ![](https://vel

인프런 카드 가져가기 문제 나의 풀이 기본형인 int 배열로 하면 내림차순 정렬을 할 수 없기 때문에 Integer형 배열을 사용하였다. 결과 인프런 심사위원 문제 나의 풀이 점수를 오름차순 정렬하면 재귀를 이용하지 않아도 쉽게 풀 수 있는 문제다. 결과 ![](https://velog.v

인프런 두 배열 합치기 문제 나의 풀이 서로 다른 배열에 포인터들을 두어서 포인터를 증가시켜가며 푸는 전형적인 투 포인터 알고리즘을 이용해서 풀 수 있는 문제다. 결과 인프런 공통원소 구하기 문제 나의 풀이 먼저 두 배열을 오름차순 정렬을 시킨다. a의 p1이 가리키는 원소와 b의 p2가 가리키는 원

인프런 최소 회의실 개수 문제 나의 풀이 스케줄대로 회의가 진행될때 동시에 진행되는 회의가 가장 많은 순간의 회의 개수를 찾으면 된다. 그 개수가 최소 회의실 개수가 된다. 끝나는 시간과 시작하는 시간이 겹치는 경우에는 끝나는 시간을 먼저 처리해준다. 결과

인프런 침몰하는 타이타닉 문제 나의 풀이 정렬을 한 다음에 left는 0번째부터 right는 마지막부터 탐색을 해서 가장 가벼운 사람과 가장 무거운 사람의 합이 m 이하인지 확인한다. 이때 m이하이면 같이 타고 나가면 되므로 보트의 개수를 1 증가시킨다. 만약 m 보다 큰 경우 right이 가리키는 한명만 타고나가야 한다 보트의 개수를 1 증가시키고 r...

인프런 최대 매출 문제 나의 풀이 결과 인프런 이동 횟수 문제 나의 풀이 한번에 여러개를 옮길 수 있다고 되어있지만 실제로 제한사항을 보면 모든 물건의 무게가 2kg 이상 5kg 이하이므로 최대 5kg밖에 들지 못하기 때문에 모든 물건이 2kg더라도 최대 2개 밖에 옮기지 못한다. 즉, 타이타닉 문제에

인프런 스프링쿨러 문제 나의 풀이 line 배열에 a번 위치에서 물을 뿌리는 범위를 [a, a - b] [a, a + b] 이렇게 2차원으로 나타낸 것이다. line을 반복문으로 탐색하는데 이중 반복문으로 linei start인 경우는 반복문에서 빠져나오게되고 answer를 1 증가시켜서 현재 해당하는 스프링쿨러를 사용한다고 표시해준다. 그런 다음 s...

인프런 최대수입스케쥴 문제 나의 풀이 입력 받을 때 가장 큰 날짜를 max에 저장시키고나서 시간에 대해서 내림차순 정렬을 시킨다. 그런 다음 max 날짜에서부터 날짜가 감소하는 순으로 탐색한다. 탐색을 하면서 현재 날짜와 같은 기한인 강연들만 우선순위큐에 넣어주고 강연 마감 날짜가 현재 날짜보다 작아지면 멈춰서 우선순위 큐에서 원소를 꺼내주어 값을 an...

인프런 전투 게임 문제 나의 풀이 학생 번호, 팀, 공격력이 원소로 이루어진 3차원 배열을 만들어준다. 그리고 나서 공격력에 대해서 오름차순 정렬을 해준다. 해싱으로 자신의 팀이 있는지 확인하여 그만큼 빼줘서 점수를 구하도록 하는 것에 유의하며 구현한다. 결과

인프런 최대 인원수 문제 나의 풀이 sum[i] 는 i번역에서 그 다음 역으로 가기 위해 탈 수 있는 최대 인원수를 나타낸다. trains의 start 인덱스에 해당하는 sum에는 인원을 더해주고, end 인덱스에 해당하는 sum에는 인원을 빼준다. 그런 다음 sum[i] += sum[i-1]를 이용해서 합을 누적해준다. 그런 다음 bookings 배열...

인프런 가장 가까운 큰수 문제 나의 풀이 dfs 순열 문제다. n을 한자리씩 분리해서 배열 nums를 만들고 이를 오름차순 정렬한다. 그런 다음 DFS(0, 0)을 호출한다. DFS의 첫번째 매개변수는 레벨을 나타내고 두번째 매개변수는 만들어지는 숫자 number를 나타낸다. 함수 내부에서 nums에 있는 원소를 for문을 이용하여 하나씩 택하면서(ch...

인프런 줄다리기 문제 나의 풀이 7행 7열의 relation 배열을 만들어서 nums 정보에 있는 관계를 1로 표시해준다(양방향으로) DFS의 깊이가 7인 경우는 줄을 세운 경우의 수 하나가 완료된 것이므로 answer에 1을 증가시켜준다. 줄을 세워가는 과정에서 relation 값이 1인 경우는 그 뒤까지 만들 필요가 없기 때문에(만들면 안되는 줄이라...

인프런 바둑대회 문제 나의 풀이 조합을 이용하여 푸는 문제이다. n명에 n/2명을 뽑는 조합을 구현하면 된다. check배열이 체크되어있으면 A팀으로 인덱스담아주고 아니면 B팀으로 인덱스를 담아주면 된다. 결과

인프런 팰린드롬의 경우수 문제 나의 풀이 문자열 s를 해싱해서 빈도수 체크를 한다. 빈도수가 다 짝수인 경우는 팰린드롬을 무조건 만들 수 있게 된다. 빈도수가 홀수인 경우는 딱 한가지만 있어야 팰린드롬을 만들 수 있다. 만들 수 있는 경우에 재귀를 통해 팰린드롬을 만들도록 구현해야 한다. 팰린드롬을 만들어가는 tmp는 덱 자료구조를 사용한다. 재귀함수의...

인프런 IP 주소 문제 나의 풀이 DFS(i)는 s문자열의 i번 인덱스부터 시작해서 0부터 255까지 숫자를 만들 수 있는 경우의 수를 찾는 함수다. 결과

인프런 알파코드 문제 나의 풀이 DFS(i)는 i번 인덱스부터의 문자열 s를 알파벳으로 복원하는 경우의 수를 찾아서 반환하는 함수다. DFS(i)에 대한 결과값은 메모이제이션을 이용해서 배열에 저장해주어 효율적으로 하게 한다. 0으로 시작하는 문자열이면 더뻗을수없도록 컷하게 한다. 결과

인프런 타일 점프 문제 나의 풀이 BFS 탐색을 한다. Level 1이라면 1번만에 갈 수 있는 곳을 의미한다. 결과

인프런 집으로 이동 문제 나의 풀이 a를 이용하여 이동한 경우는 0을 순서쌍에 넣어주고 b를 이용하여 이동한 경우는 1을 순서쌍에 넣어주어 b를 두번연속 사용하지 못하게 구분해준다. check 배열도 2차원 배열로 만들어서 앞으로 점프해서 온 경우는 check0 = 1로 하고, 뒤로 점프해서 온 경우는 check1 = 1로 구분해준다. pool이 있는 ...

인프런 송아지를 잡자 문제 나의 풀이 송아지가 계속해서 움직이기 때문에 check 배열을 2차원 배열로 만들어서 check0에는 짝수 레벨을 체크하고 check1에는 홀수 레벨을 체크하게 한다. 결과

인프런 미로의 최단거리 통로 문제 나의 풀이 L은 nx, ny 값의 레벨 값이므로 L값을 먼저 1증가시켜서 for문으로 반복시킨다. 결과

인프런 집을 짓자 문제 나의 풀이 각 빌딩마다 bfs 탐색을 해서 빈땅에 L값을 누적시킨다. 결과

인프런 숲속의 기사 문제 나의 풀이 이중for문을 돌면서 2나 3이 발견되면 2가 발견되는 경우는 bfs탐색을 해서 dist배열에 L값을 누적해주면서 4까지 얼마나 걸리는지 최단거리를 구해준다. 3이 발견되는 경우도 bfs 탐색을 해서 dist배열에 L값을 누적해주면서 4까지 얼마나 걸리는지 최단거리를 구해준다. check배열은 두번 bfs탐색해야하므로...

인프런 최소 비행료 문제 풀이 가중치방향그래프를 인접리스트로 만든다. 환승횟수를 카운트해야하기 때문에 큐를 사용한 레벨탐색을 해야 한다.(다익스트라 x) costs[i]는 출발지점에서부터 i번째 도시로 가는 비행료의 최소비용이며 처음에는 무한대값으로 초기화해준다. 큐가 비어있지 않을때까지 레벨탐색을 하면서 레벨마다 반복이 끝났을 때는 L값을 1증가시켜주...

인프런 최소 환승 경로 문제 나의 풀이 최소 환승 횟수를 구하는 것이기 때문에 레벨을 환승 횟수로 이용하는 레벨 탐색 사용을 판단해야 한다. 백만개의 역번호를 정점으로 하는 인접리스트를 만든다면 메모리 낭비가 너무 심하기 때문에 해싱을 이용한다. routes를 탐색하여 역번호가 key이고, 호선들을 set 자료구조로 표현한 것을 value로 하는 gra...

인프런 방향 바꾸기 문제 나의 풀이 다익스트라를 이용해야 하므로 cost 배열을 처음에 큰값으로 초기화한다. costi는 0행 0열에서 i행 j열까지 가는 데 최소 방향을 몇번 바꿨는지를 나타내는 횟수다. dx,dy는 1,2,3,4 방향순대로 구성한다. 우선순위 큐에 (행, 열, 격자를 바꾼 횟수)를 넣어서 탐색을 시작한다. board에 적힌 것에서 1...

인프런 공 굴리기 문제 나의 풀이 간선 값이 일정하지 않고 다 다르고 간선 값이 다 양수이기 때문에 다익스트라를 이용해야 한다. cost 배열 값을 큰값으로 초기화 해준다 costi는 i행 j열까지 공이 가는 데 걸리는 최소 이동 거리를 뜻한다. 우선순위 큐에 (행, 열, 위치까지 가는 데 이동거리)인 공의 위치, 0을 넣어준다. 이렇게 탐색을 하면서 ...

인프런 교육 과정 문제 나의 풀이 전체적인 순서를 찾을 때 위상 정렬을 사용해야 한다. 위상 정렬은 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다. 주로 선후 관계가 있는 일련의 작업을 차례대로 수행하기 위해 순서를 정할 때 사용하는 알고리즘이다. 해시를 사용해서 과목 이름을 key로 하고 value값을 인덱스 번호로 만들어준다. course를...

백준 4781번 사탕 가게 문제 나의 풀이 냅색의 전형적인 문제다. dy[i]는 상근이가 i원을 가지고 얻을 수 있는 최대 칼로리를 뜻한다. 사탕 가격이 소수점이 있는데 부동소수점을 고려해야 하므로 100을 곱한 뒤에 round 메소드로 반올림을 해줘야 한다. 사탕의 정보를 탐색하면서 i가 사탕 가격 이상부터 dy[i]를 dy[i - 사탕가격] + 사탕...

백준 2073번 수도배관공사 문제 나의 풀이 P의 개수가 350이하로 많기 때문에 BFS를 이용해서 부분집합으로 풀면 안되고 DP를 이용해야 한다. 냅색 다이나믹을 이용한다. dy[i]는 i 길이의 수도관을 만들었을 때 최대 용량을 의미한다. 파이프의 개수가 각각 한개씩이기 때문에 dy 테이블을 앞에서부터가 아닌 뒤에서부터 적용해서 중복적용되지 않게 해...

백준 2579번 계단 오르기 문제 나의 풀이 계단의 개수가 300개이므로 경우를 하나하나 다 계산하는 것은 무리가 있기 때문에 다이나믹 프로그래밍을 사용해야 한다. dy[i]는 i번 계단까지 올랐을 때 얻을 수 있는 최대 점수를 나타낸다. dy[0]은 0으로 두고 시작한다. dy[1]은 경우의 수가 1개 뿐이므로 score[1]이다. i가 2일 때는 s...

백준 1994번 등차수열 문제 나의 풀이 만약 n이 1이라면 수열이 1개뿐이므로 그냥 1만 리턴해준다. 들어온 입력을 오름차순 정렬을 한다.(등차가 음수인 것은 고려해주지 않아도 됨. 등차가 음수인것을 오름차순 정렬하여 보면 등차가 양수가 되는 형태이므로) nums 배열에 1번 인덱스부터 입력 값들을 받아주어 정렬시킨다.(0번 인덱스는 0) dyi는 i...

백준 1695번 팰린드롬 만들기 문제 나의 풀이 입력받은 수들을 nums 1차원 배열에 1번 인덱스부터 넣어준다. dyi는 i번째 수부터 j번째 수까지의 부분수열을 팰린드롬으로 만들기 위해 끼워넣어야 할 수의 최소 개수를 나타낸다. 그렇기 때문에 정답은 dy1을 출력해주면 된다. 가장 최소 단위는 dyi인데 자기 자신 뿐이므로 0으로 냅두면 된다. dy...

백준 1823번 수확 문제 나의 풀이 입력 받은 벼들의 가치들을 nums배열에 1번 인덱스부터 저장시킨다. dyi는 i번째 벼부터 j번째벼까지를 수확했을 때 얻을 수 있는 최대 이익을 나타낸다. dyi를 구할 때 두가지 경우로 나뉘는데 첫번째 경우는 i번째를 제일 먼저 수확했을 때를 가정하는 경우고 이때는 dyi+1에 nums i번째부터 j번째 요소들의...