알고리즘

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 📌 - 처음 생각한 풀이 도시와의 거리 = 시작지점을 제외하고는 전부 int 최댓값 초기화 , 이전도시 정보 배열 초기화 인접리스트를 이용해서 리스트에 인접한 도시와 비용을 객체로 추가 bfs로 도시들을 방문 - 비용이 최소일 때만 업데이트 - 업데이트 할 때 그 비용은 dp배열에 저장하고 해당도시를 방문하기 전 도시를 result배열에 저장 result 배열을 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📌- 풀이 빙산 문제에서 빙산이 녹는 방식처럼 1초마다 먼지를 퍼뜨린다. 공기 청정기의 화살표 방향으로 밀어서 먼지를 없앤다. 단순 구현으로 문제를 해결할 수 있다. 방법이 여러가지가 있겠지만 내가 푼 방식은 먼지들을 미는 느낌으로 문제를 해결하는 것이 아니라 공기청정기에서 역으로 먼지를 당긴다고 생각하고 풀었다. 공기청정기로 시작해서 다시 공기청정기인 [-1]이 나올때까지 무한루프를 돌면서 청..

https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 📌 - 처음 생각한 풀이 예상 등수를 정렬 1씩 증가하면서 예상 등수랑 차이를 더함 - 풀이가 분명히 맞다고 생각해서 제출을 했는데 틀림 - 숫자를 보니 50만까지 증가할 수 있는데 최악의 경우 에상등수와 실제 등수의 차이가 최대치로(ex - 예상등수 50만등, 실제 1등) 날 경우가 50만개 있는 경우 int타입을 벗어나서 틀리게 됨 📌- 풀이 예상 등수를 정렬 1씩 증가하면서 에쌍 등수랑 차이를 더 ..

https://www.acmicpc.net/problem/12785 12785번: 토쟁이의 등굣길 인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다. www.acmicpc.net - 처음엔 간단하게 생각해서 BFS로 구현을 했었는데, 풀고나니 메모리 초과가 발생해서 다시 dp로 풀었다. 📌 - 풀이 이 문제는 결국 출발점 -> 토스트 집의 경로 * 토스집의 경로 -> 도착점까지를 구하는 문제인데 DP를 이용해서 해당하는 경로까지의 경우의 수를 업데이트 해주고 경로의 수를 곱해주면 결과값이 나온다. 🔥 - java code package DP.S1_12785..

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 코딩테스트 언어를 python에서 java를 바꾸는 과정에서 문제들의 유형들을 여러가지 풀어봐야할 것 같아서 DFS 문제로 정하고 문제를 품 📌 - 처음 생각한 풀이 DFS로 완전탐색을 하면서 부등호에 맞는 모든 경우의 수를 List에 저장 list의 크기가 N+1이 됐을 때, 리스트에 있는 모든 값들을 str에 순차적으로 저장 str을 long으로 형변환 하면서 크기 비교 -> 최솟값과 최댓값 비교해서 저장..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 📌 - 로봇 청소기 DFS, BFS 문제로 풀어야 하는지 고민했는데, 단순 구현으로 풀어도 시간복잡도가 초과되진 않아서 단순 구현으로 품 이동, 방향전환 함수를 따로 만들어서 로봇 청소기의 움직임을 조금 더 보기쉽도록 구현함 구현문제는 주어진대로 구현만 하면 되는데, 로봇 청소기는 문제를 이해하는데 생각보다 조금 오래 걸렸던 것 같다. 현재 위치 ..