Algorithm, Problem Solving62

• 

  [프로그래머스][Java] 다단계 칫솔 판매 1. 문제 정보 https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 : 레벨 3 유형 : DFS 2. 문제 풀이 이 문제에서 핵심적인 부분은 3개이다. 숫자가 아닌 문자열로 되어있는 인덱스 정보로 그래프 노드끼리 어떻게 연결시킬까? 그래프 탐색 시 종료 조건은? 판매 정보에 중복이 있을 수 있다. 1. 문자열 정보로 그래프 노드 매핑 굳이 문자열을 숫자로 따로 매핑하는 과정을 거치지 않아도 간단히 그래프를 그릴 수 있다. 해쉬맵을 이용하여 .. Algorithm, Problem Solving/프로그래머스 2024. 3. 22.

• 

  [백준][Java] 1744 - 수 묶기 문제 정보 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 난이도 : G4 유형 : DP 시간 : O(N), 정렬시간 제외 해결 방법 모든 수는 최대 한 번만 묶일 수 있다. 연속이 아닌 부분 수열의 합을 구하는 것이므로 수열의 원소의 위치가 변경돼도 상관없다. -> 정렬 가능 1. 직관적으로 큰 수끼리 곱해야 더 큰 수가 나오므로 주어진 수열을 정렬한다. 2. 오름차 순으로 정렬 시 왼쪽에서부터 오른쪽으로 진행 3. 탐색하면서 매 순간 dp.. Algorithm, Problem Solving/백준(boj) 2024. 3. 20.

• 

  [백준][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] 2799 - 블라인드 목차 문제 정보 https://www.acmicpc.net/problem/2799 2799번: 블라인드 첫째 줄에 M과 N이 공백으로 구분해서 주어진다. (1 ≤ M, N ≤ 100) 다음 줄에는 현재 건너편 아파트의 상태가 주어진다. 모든 창문은 문제 설명에 나온 것 처럼 4*4 그리드로 주어진다. 또, 창문과 www.acmicpc.net 난이도 : S4 유형 : String, Implementation 시간 : O(N * M) 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { final.. Algorithm, Problem Solving/백준(boj) 2023. 12. 9.

• 

  [백준][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] 6907 - Floor Plan 목차 문제 정보 https://www.acmicpc.net/problem/6907 6907번: Floor Plan The floor plan of a house shows rooms separated by walls. This floor plan can be transferred to a grid using the character I for walls and . for room space. Doorways are not shown. Each I or . character occupies one square metre. In this diagram, there are www.acmicpc.net 난이도 : S1 유형 : BFS, 정렬 시간 : O(N x M) 문제 풀이 매우 기초적인 bfs문제 추가적으로.. Algorithm, Problem Solving/백준(boj) 2023. 10. 19.

• 

  [백준][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.