본문 바로가기

알고리즘/📌백준14

[Dijkstra] 파티 📌 문제 문제 링크 : https://www.acmicpc.net/problem/1238 문제 유형 : 다익스트라 문제 난이도 : 골드3 문제 : N개의 마을이 있다. 각 마을에는 1명의 사람이 산다. 마을 한 곳에서 파티를 한다. ( 파티를 하는 곳 : X ) N명의 사람은 X에서 모이고, X에서 다시 각자 집으로 돌아간다. 사람들은 이동시간이 최소로 걸리는 경로로 움직인다. 경로는 모두 단방향으로 주어진다. 이 때, 가장 시간이 오래 걸리는 사람의 값을 출력하라. 📌 문제 풀이 전형적인 다익스트라 문제 길찾기를 두번 한다. 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 예제의 값처럼 마을이 N=4, X=2로 주어졌다고 해보자. 그러면 1->2 2->2.. 2022. 1. 4.
[Two Pointer] 용액 📌 문제 문제 링크 : https://www.acmicpc.net/problem/2467 문제 유형 : 투 포인터 문제 난이도 : 골드5 📌 문제 풀이 양쪽 끝에서 시작하는 투 포인터를 잡는다. 왼쪽에서 오른쪽으로 가는 것은 증가를 의미, 오른쪽에서 왼쪽으로 가는 것은 감소를 의미한다. 이 때, 왼쪽에서 오른쪽으로 움직이는 증가폭이 0에 더 가깝게 만들어 주는지, 오른쪽에서 왼쪽으로 움직이는 감소폭이 0에 더 가깝게 만들어주는지 알 수 없다. 즉, 증가하는 분과 감소하는 분 중 누가 더 0에 가깝게 만들어주는 지 알 수 없다. 그래서 왼쪽 이동후의 값과 오른쪽 이동후의 값을 비교해서 더 작은 쪽으로 움직인다. ▸ 그림 설명 위의 예에서 현재 arr[left] + arr[right] 의 값은 -8이다. 이.. 2021. 12. 23.
[Two Pointer] 수 들의 합2 📌 문제 문제 링크 : https://www.acmicpc.net/problem/2003 문제 유형 : 투 포인터 문제 난이도 : 실버3 문제 요약 구간 합 M을 만족하는 배열의 구간이 몇 개나 있는가? 단 O(n)으로 풀어야 한다. 📌 문제 풀이 간단하게 생각해서는, O(n^2) 으로 풀 수 있다. for loop를 두번 돌려서, 만족하는 구간을 찾아주면 된다. 그러나 해당 문제는 O(n)으로 풀어야 한다. 해당 문제는 투포인터를 이용해서 시간 복잡도를 줄일 수 있다. left 와 right으로 구간을 잡는다. 포인터의 이름대로 범위는 left 2021. 12. 22.
색종이 만들기 문제 문제 유형 : 분할정복 색종이를 절반씩 나누어서, 같은 영역이 될때까지 나눈다. 같은 영역이 됐다면 count+1을 해준다. 문제 풀이 대표적인 분할정복 문제이다. 로직은 다음과 같다. 1. n값과 시작위치를 입력값으로 받는다. 2. 맵이 시작위치부터 n까지 전부 같은 값으로 이루어져있는지 확인한다. 2-1). 만약 전부 같은 값으로 이루어졌다면, 1인지 0인지 확인하고 해당 숫자를 1증가시켜준다. 3. 사방으로 나누어서 함수를 재귀 호출한다. 이 때, 넘기는 n의 값은 n/2이다. → 맵이 전부 같은 지 확인하는 부분을 두 방법으로 풀었다. 1번 방법 ) for(int i=0;i 2021. 12. 16.
백준: 16236번 아기상어 🏆 문제 정보 문제 난이도 : 중상 문제 유형 : 시물레이션 / BFS 📌 문제 처음 아기상어 크기 ->2 상하좌우 크기가 같으면 이동 가능 . 잡아먹기는 불가능 잡아먹은 수만큼 크기가 커진다. 더 이상 먹을 게 없다면 stop 먹을 수 있는게 둘 이상이면, 거리 최소 -> 칸의 수 가장 위부터. 위가 똑같으면 왼쪽 📌 생각 1. 이동한 거리 -> BFS 이용 2. 로직 움직일 수 있으면 움직이고, 상하좌우로 이동할 때마다 count를 센다. 움직인 칸이 해당 shark의 size보다 작다면 eatList에 넣어준다. eatList가 비어있다면 더이상 먹을 것이 없다는 것이므로 끝낸다. eatList는 가장 가까운 기준, 가까운 것이 많다면 x 기준, x가 똑같다면 y기준이다. 그래서 Comparator.. 2021. 8. 25.
백준: 영식이와 친구들 🏆 문제 정보 문제 난이도 : 하 문제 유형 : 구현 📌 문제 배열의 해당 값이 짝수이면 우측으로, 홀수면 좌측으로 L 만큼 움직인다. 해당 배열의 값이 M이면 멈추라. 📌 생각 오른쪽으로 이동할 때, 배열의 값이 배열 범위를 벗어난다 -> %N 한 나머지 값을 index로 넣어주면 된다. 왼쪽으로 이동할 때, 배열의 값이 배열 범위를 벗어난다 -> %N한 나머지 값인데, 만약 index - move 의 값이 0보다 작다면, N을 더해준다. // 좌측으로 이동의 경우 public class Main { public static void main(String[] args) { int[] arr = {1,2,3,4,5,6}; int move = 16; // 나와야 하는 결과값 5 int index = 2; .. 2021. 8. 21.
백준: 단어뒤집기 2 🏆 문제 정보 문제 난이도 : 하 문제 유형 : 구현 / 문자열 📌 문제 tag를 만났을 시 그대로 hello my name 등의 단어를 만났을 시 단어단위로 뒤집기 -> olleh ym eman 📌 생각 tag가 있을 경우와 tag가 없을 경우로 나누어서 생각했다. ⚡️1. tag가 있을 경우 어차피 가 있을 것이므로 를 만날 때까지 전진한다. >를 만나면 멈추고, 해당 값까지 StringBuilder에 더해준다. 이 때, 해당 index가 있는 첫 시작자리를 기억해줘야 하므로 해당 index 자리를 저장해주는 temp 변수를 이용한다. ⚡️2. tag가 없을 경우 마지막 index를 벗어나거나, 해당 다음 값이 < 이거나, 해.. 2021. 8. 21.
백준: 알파벳 - ( permuation 방문처리 ) 🏆 문제 정보 문제 유형 : 백트랙킹 / DFS 문제 난이도 : 중 📌 문제 https://www.acmicpc.net/problem/1987 시작위치는 (0,0) . 알파벳은 지나갔었던 알파벳을 지날 수 없을 때, 지날 수 있는 최대 count를 구하라. 📌 생각 문제 자체는 일반적인 dfs이지만, 지나간 것을 어떻게 표시할 지가 문제였다. 첫번째로 생각했던 것은 List를 선언해서 지나갈 때마다 List에 담고, 매 재귀호출마다 해당 list와 paramter인 r,c를 확인해서 겹치면 return 하고, 겹치지 않으면 진행하는 식으로 하려고 했다. 여기에는 2가지 문제가 있었다. ⚡️1. 방문처리 permutation을 먼저 생각해보자. 해당 count=3 일 때, v[i] = true 다음 함수 .. 2021. 8. 20.

티스토리툴바