potato's devlog

🟠 문제링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 🟠 문제 풀이 아이디어 가장 기초적인 dp 문제중 하나였다. 하지만 가장 중요한것은, 생각을 반대로해야한다는 것이었다. "처음부터 계단을 어떻게 올라가지?" 생각보다는, "최종 도착지기준으로 봤을때, 어디서 올라왓찌?"를 고려해봐야한다는 것이다. 연속으로 3칸의 계단을 밟을 수가 없기 때문에, 도착지 기준으로 올라올 수 있는 방법은 아래 그림처럼 딱 두가지 방법이다. 이렇게 dp 점화식을 유도해냈..

🟠 문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 🟠 문제 풀이 아이디어 가장 기초적인 dp문제로 이미 풀어봤던 문제라 어렵게 생각하지 않았다. dp 에는 현재위치의idx-1 까지의 합과 해당 arr[idx] 값을 비교해본 후 최대값을 넣어준다. 앞에서부터 차례대로 차곡차곡 더해진 값에 현재값을 더하는게 더 큰지, 현재값만 바라보는게 더 큰지 확인하는 것이다! 🟠 전체 소스코드 https://github.com/deslog/Algorithm..

✅ 문제 링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net ✅ 문제 풀이 아이디어 문제가 굉장히 난해하게 생겼기 때문에 ,,,, 처음엔 BFS 문제인지 감이 안잡혔다. 인터넷을 찾아보니, 이 문제의 핵심은 다음과 같았다. 가운데 구멍뚫린 부분은 신경쓰지 않아도 된다. 어차피 BFS 로 탐색을 (0,0)부터 시작하게되면, 구멍으로 접근이 불가능하다. 외부 공기자리부터 탐색을 시작하면 어차피 구멍 내부로 접근할 수 없기떄문!! 가장자리는 항상 외부공기로 둘러쌓여있..

✅ 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ✅ 문제 풀이 아이디어 기본적으로 연합국가인지 아닌지를 판단해야하기 때문에 BFS로 풀어야한다고 생각했다. 위의 출력예제를 보면, 점선이 생기는 위치가 다르다. 30과 40은 직접적인 연결은 아니지만, 어쨋든 연합국가이긴하다. 그렇기 때문에 초반에 어렵게만 생각되었던 "어디에 점선이생기는지 고려해야하는가"를 전혀 생각하지 않고 그냥 탐색하면서 연합국가에 같이 담아주면된..

🟣 문제 링크 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 🟣 문제 풀이 우선 문제를 이해하는데 어려웠다. 그림을 그리면서 + 그리고 인터넷을 찾아보면서 문제를 이해했다. 우선, '순환선 = 사이클'을 찾아야한다. 이 지하철 노선도로 보면, '신도림'역은 이미 순환선 (사이클) 내부에 있기 때문에 순환선까지의 거리가 0이다. 하지만 '까치산'역인 경우, 순환선이 아니라 지선에 속한다. 이 까치산역은 '순환선'까지 ..

💻 문제 링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 💻 풀이 BFS로 풀었다. 사실 시작점이 여러개인 BFS는 어떻게 풀어야할지 모르겠어서, 인터넷을 참고해서 풀었다ㅠㅠ m과 n을 입력받는다. 0, -1, 1이 들어있는 배열을 box로 입력받았다. day는 며칠이 지났는지 판단하기 위해서 만든배열이다. 뒤에서 보면 한칸한칸 익어나갈때마다 +1 을 해준다. let mn = readLine()!.split(separato..

💻 문제 링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 💻 문제 풀이 기본적이 BFS 문제이다. 미로를 가중치 없는 무방향 그래프로 본다면, 가중치없는 무방향 그래프에서 최단거리를 구하는 BFS 탐색 방법을 이용하면된다! 처음 입력받는 n과 m을 nm 배열로 입력받아서 nm[0], nm[1] 로 사용하였다. dx, dy 는 상하좌우 방향을 나타내는 방향키! 이다. arr는 입력받는 미로 visited는 미로에서 방문했는지 안했는지 T/F 로 나타내는 배열 distanc..

👉 문제링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💻 문제풀이 가장 기본적인 DFS문제 (BFS도 가능) 그래프로 입력 받은 후, 1인 곳을 전부 탐색 → 탐색하면서 해당 위치 방문처리 방문처리 된 곳들을 돌아다니다가 방문처리할 곳이 없으면 count += 1 최종적으로 count 출력 💻 소스코드 https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/4963_%EC%84%A..

💁🏻 문제링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 💻 문제 풀이 이런 문제를 만나면, 현재위치에서 위, 아래, 오른쪽, 왼쪽을 살펴보면서 연결이 되어있나? 를 판단해야한다. 위 그림을 보면, 현재 위치는 (0,0)일때 방향키로 움직일 수 있다. x좌표인 0에다가 dx[2]을 더하고, y에다가 dy[2]을 더해주면, (1,0)으로 한칸 아래로 이동할 것이다. 이처럼 이렇게 "연결된 1을 찾아 무언가를 찾는문제"라면, 이렇게 방향키를 생..

👉 문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🧑🏻‍💻 문제 풀이 이분그래프 이면 1, 이분그래프가 아니면 -1를 flag에 저장해주었다. 정점은 각각 1과 -1로 구별해주었다. 만약 인접한 정점이 둘다 1이거나, 둘다 -1이라면 이건 이분그래프가 아닌거다! 이 값들은 visited 에 넣어주었다. 아래 코드는 main으로 돌아가는 부분이다. 차례대로 설명을 작성해보자면 처음 입력받는 K 만큼 result가 출력되어야 하므로 모..