Algorithm14

• 

  [백준][Java] 6129 - Obstacle Course 목차 문제 정보 https://www.acmicpc.net/problem/6129 6129번: Obstacle Course The cow must make at least 2 turns: For example, the cow may start by facing south, move south, turn to face west, move west, move west, then turn to face south, and finally move south into the B square. www.acmicpc.net 난이도 : G4 유형 : 다익스트라, BFS 문제 풀이 우선순위 큐를 이용한 다익스트라 기법을 활용하여 풀었다. (0-1 BFS라고도 봐도 무방하다) 우선순위 큐에 들어 있는 데이터는 '회전 횟수.. Algorithm, Problem Solving/백준(boj) 2023. 12. 11.

• 

  [백준][Java] 17175 - 피보나치는 지겨웡~ 목차 문제 정보 https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 난이도 : S3 유형 : DP 시간 : O(N) 문제 풀이 fibonacci 함수가 호출된 횟수를 구해야 한다. fibonacci의 정의를 생각해 보자 fibonacci[i] = fibonacci[i - 2] + fibonacci[i - 1] ( i return i) 피보나치함수 인자가 0 혹은 1 일 때 값을 리턴하고 종료하며 예외의 상황일 때 위의 식처럼 재귀문의 .. Algorithm, Problem Solving/백준(boj) 2023. 12. 7.

• 

  [백준][Java] 20920 - 영단어 암기는 괴로워 목차 문제 정보 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 난이도 : S3 유형 : 정렬, 해쉬 문제 풀이 문자들을 우선순위에 따라 정렬하는 것이 이 문제의 핵심이다. 일단 해쉬맵을 이용하여 문자열을 처리해야한다. 해쉬맵의 getOrDefault() 메소드를 활용하여 개수를 처리 해쉬맵의 데이터를 리스트로 전달하고 구현한 정렬로직을 통하여 리스트를 정렬하면 된다. 정렬로직.. Algorithm, Problem Solving/백준(boj) 2023. 10. 26.

• 

  [백준][Java] 5107 - 마니또 목차 문제 정보 https://www.acmicpc.net/problem/5107 5107번: 마니또 N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와 www.acmicpc.net 난이도 : S1 유형 : Cycle Disjoint-Set, DFS, Hash 문제 풀이 해쉬맵을 이용하여 입력으로 주어지는 사람 이름에 고유한 번호를 부여해 준다. 사람이름 두 개가 입력될 때마다 고유한 번호 두 개를 얻어낸 다음 연결하여 그래프를 구성하면 된다. 방문하지 않은 곳을 차례대로 DFS 탐색을 진행한다. 만약 탐색 로직 실행 중 이미 탐색했던 곳을 만난다면 순열을 이루는.. Algorithm, Problem Solving/백준(boj) 2023. 10. 15.

• 

  [백준][Java] 23288 - 주사위 굴리기 2 목차 문제 정보 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 난이도 : G3 유형 : 시뮬레이션, BFS, 해쉬 문제 풀이 [핵심] 1. 매번 주사위가 움직일 때마다 주사위의 6면 상태를 관리 2. 매번 이동 방향의 인덱스(dirIdx)를 알맞게 조정 [최적화] 매번 점수를 구할 때 항상 탐색을 하면 비효율적이다. 해쉬맵을 이용하여 BFS 탐색 종료 후 탐색되었던 곳들을 하나의 그룹번호로 묶고 해당 그룹의 총점수를 해쉬맵에.. Algorithm, Problem Solving/백준(boj) 2023. 10. 12.

• 

  [백준][Java] 17128 - 소가 정보섬에 올라온 이유 목차 문제 정보 https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 $N$과 욱제가 장난칠 횟수 $Q$가 주어진다. 둘째 줄에 $N$마리 소들의 품질 점수 $A_i$가 순서대로 주어진다. 셋째 줄에 욱제가 장난칠 $Q$개의 소의 번호 $Q_i$가 순서대 www.acmicpc.net 난이도 : S2 유형 : 누적합 시간 : O(N + Q) 문제 풀이 전체합 S는 부분합 N개로 구성된다. 각 부분합은 1~4 , 2 ~ 5... 등 연속된 4개의 수의 곱이다. 쿼리로 주어진 소의 번호를 기준으로 하위 연속된 숫자 4개에 해당하는 부분합에 각각 -1을 곱해준 뒤 전체합에 두 번 더해주면 된다. 두 번 더해주는 이유 : 기존값.. Algorithm, Problem Solving/백준(boj) 2023. 10. 11.

• 

  [백준][Java] 15240 - Paint bucket 목차 문제 정보 https://www.acmicpc.net/problem/15240 15240번: Paint bucket One of the most time-saving operations when drawing on a computer (for example using Photoshop) is the “bucket fill” operation. When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color www.acmicpc.net 난이도 : S1 유형 : BFS, DFS 문제 풀이 상하좌우로 같은 문자를 탐색하면서 치환해 주면 된다. 여기서 주.. Algorithm, Problem Solving/백준(boj) 2023. 10. 10.

• 

  [백준][Java] 12524 - Twibet (Large) 목차 문제 정보 https://www.acmicpc.net/problem/12524 12524번: Twibet (Large) The first line of the input gives the number of test cases, T. T test cases follow. Each one starts with a line containing a single integer N. The next line contains N space-separated integers F1, F2, ..., FN. Monk 1 follows monk F1. Monk 2 fol www.acmicpc.net 난이도 : S2 유형 : DFS, BFS 문제 풀이 수도승과 추종자들을 단방향 간선으로 연결시켜 준다. 그리고 수도승마다.. Algorithm, Problem Solving/백준(boj) 2023. 10. 10.

• 

  [백준][Java] 5081 - Constellations 목차 문제 정보 https://www.acmicpc.net/problem/5081 5081번: Constellations One night, while camping out in the wide open spaces, Big Ed was looking at the stars. Now Ed never bothered to learn his constellations, but decided that grouping the stars was a reasonable thing to do after all. But Big Ed was going to do it in a sensibl www.acmicpc.net 난이도 : Gold 5 유형 : Union-find, 브루트포스 문제 풀이 [핵심] 1. 별마다 번호부.. Algorithm, Problem Solving/백준(boj) 2023. 4. 28.

• 

  [백준][Java] 14397 - 해변 목차 문제 정보 https://www.acmicpc.net/problem/14397 14397번: 해변 단위 정육각형 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하시오. 해변은 정육각형의 변 중에서 한 쪽은 물인데, 한 쪽은 땅인 곳을 의미한다. www.acmicpc.net 난이도 : Silver 4 유형 : BFS, 그래프 탐색 문제 풀이 사각형을 다루는 일반적인 인접행렬과 달리 이 문제는 '육각형'이다. 그러므로 이동하는 방향이 6가지이며 또한 홀수, 짝수 줄마다 이동하는 방향이 다르다. ( 육각형들이 붙어 있지 않고 상하좌우로 정렬되어 있다고 생각해 보자) 홀수줄 : (-1,-1), (-1,0), (0,1), 그림처럼 짝수, 홀수줄마다 이동하는 방향이 다르다는 것을 알 .. Algorithm, Problem Solving/백준(boj) 2023. 4. 22.

• 

  [codeforces][Kotlin] 1360B - Honest Coach 목차 문제 정보 https://codeforces.com/problemset/problem/1360/B Problem - 1360B - Codeforces codeforces.com 난이도 : B 유형 : Greedy, Sort 시간 : O(T *(N + NlogN)) 문제 풀이 운동선수들을 A, B 집단으로 나눠야하고 나누는 기준은 운동선수들 마다 가지고 있는 힘의 정도이다. "A집단의 운동선수들의 힘 중 가장 큰값 - B집단의 운동선수들의 힘 중 가장 작은 값"을 구해야 한다. 정렬 후 양 옆의 힘의 값의 차이가 제일 작은 값이 답이다. 이해를 위해 아래 표를 보자. [정렬 전] 2 1 3 2 4 3 [정렬 후] 1 2 2 3 4 4 입력값들을 오름차 순으로 정렬하고 왼쪽은 A집단, 오른쪽은 B집단으.. Algorithm, Problem Solving/codeforces 2023. 4. 20.

• 

  [codeforces][Kotlin] 1624A - Plus One on the Subset 목차 문제 정보 https://codeforces.com/problemset/problem/1624/A Problem - 1624A - Codeforces codeforces.com 난이도 : A 유형 : greedy, Math 시간 : O(nlogn) 문제 풀이 1. 배열을 오름차순으로 정렬 2. 마지막 원소와 첫번째 원소의 차이가 답 코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer fun solution() = with(BufferedReader(InputStreamReader(System.`in`))) { var sb = StringBuilder() var t = read.. Algorithm, Problem Solving/codeforces 2023. 4. 5.