알고리즘/문제

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 📌- 풀이 입력받을 때 0이면 0, 1이면 -1, 2이면 0을 배열에 저장하고 2일 경우엔 해당 좌표를 Queue에 add 해당 좌표를 시작으로 4방향을 체크하면서 배열의 좌표값이 -1일 경우만 BFS를 하면서 해당 값에 depth를 추가하여 하나씩 거쳐갈 때마다 depth + 1 로 거리를 체크함 해당 문제는 별로 어렵지 않은 BFS 문제였는데, 시간..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 📌- 풀이 DP문제를 항상 어렵게 생각했는데 DP문제 치고는 생각보다 간단하게 풀었던 것 같음. 1. 값이 이렇게 들어온다고 생각할 때, 각각 값이 들어올때마다 최대값을 저장해주자라는 생각을 함 10부터 시작해서 10은 10 하나이므로 최댓값이 10이고, -4의 경우에는 10에다가 -4를 더하는 값이 최대기 때문에 -4를 더해서 이런 식의로 전의 값과 비교해서 최댓값을 저장하면서 진행을 한다. 진행을 하다가..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 토마토 문제는 BFS를 하다보면 가끔 비슷한 유형의 문제들이 나와서 한 번 풀어 봤는데 다시보니까 또 방법이 제대로 기억이 안나서 일단 생각나는대로 구현을 했는데 결과는 맞았지만 다른 사람들의 풀이와 내 풀이법을 비교해보니 나의 풀이가 좀 기괴?한 것 같아서 일단 다른 사람들의 풀이를 공부할 겸 리뷰를 적어보도록 한다. 📌 - 다른 사람들 풀이 graph와 visited의 2차원 ..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 처음에 문제를 읽으면서 이게 무슨 소린가 싶었는데, 하나씩 조건을 따지면서 보니까 할만하다 생각이 들었다. 문제를 보니까 메모리 부분은 아예 신경쓸 필요도 없을 뿐더러, 오히려 그냥 막 써도 되겠다 싶어서 일부러 학생 테이블을 2개 만들어서 하나는 입력받은 대로 학생과 그 학생이 좋아하는 학생의 숫자들을 student에 저장을 했고, 동시에 학생 번호를 순서대로 student2에 저장을..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📌 - 처음 생각한 풀이 방문 배열 -1로 초기화 방문 배열이 -1이거나 BFS로 탐색했을 때 방문한 배열의 값이 이전 값보다 작으면 교체 BFS를 통해서 시작 숫자부터 목표 숫자까지 -1, +1 , *2 반복 해당 번호에 도착하면 종료 및 출력 - 시간 복잡도는 따로 생각하지 않고 일단 로직이 맞는지 확인하고 싶어서 시간초과가 난다 생각하더라도 구현 함 - ..

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 배열을 ..