취준/알고리즘
-
백준 1600번 자바 문제 풀이취준/알고리즘 2023. 7. 13. 13:06
1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 해석 1,1에 정점에서 h, w의 정점까지 이동하는데 k번만 체스판의 말과 같이 이동할 수 있고 그 외에는 인접한 정점으로만(상, 하, 좌, 우) 움직일 수 있을 때 h, w까지 이동하는 최소 경로수를 구하는 문제이다. 내가 푼것 처음에 문제를 보고 k번 말처럼 움직이고 그 외에는 인접한 좌표로 움직이면서 BFS 탐색을 하면 되겠구나! 싶었다. public static int[] horseMoveX = {-2,2,-1,1}; public s..
-
백준 10971번 자바 문제 풀이취준/알고리즘 2023. 7. 12. 11:45
10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 해석 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 arr [i][j]의 원소는 i -> j까지의 이동 경로의 값을 의미한다. arr [1][2]의 값은 10 인대 1->2로 이동할 때는 10이라는 의미가 된다. 하지만 arr[i][j]와 arr [j][i]의 값은 일치하지 않다. arr [2][1]의 값은 5인 것처럼 말이다. 출발하는 위치는 상관 없지만 반드시 출발했던 위치로 돌아와야 한다..
-
백준 1697번 JAVA 풀이취준/알고리즘 2023. 7. 11. 12:02
1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net N부터 K까지 이동할 때 -1,+1, *2 3가지 연산을 이용해 K까지 가장 먼저 도달하는 경우를 구하는 문제이다. 처음에는 DP로 풀어볼려고 접근을 했으나 K까지 최단 경로로 도달할 때 K 보다 큰 값이 포함되는 경우의 수가 포함되어 있어서 BFS로 접근하고자 했다. 처음에 BFS로 접근을 하기는 했지만 문제를 잘 읽지 못하고 경우의 수를 세심히 따져 보지 않았다. 항상 N < K가 아니라는 것이다. 즉 항상 수빈이가 동생 보다 뒤에..
-
백준 11724번 자바 풀이 정리취준/알고리즘 2023. 7. 10. 11:26
11724번: 연결 요소의 개수첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어www.acmicpc.net정점끼리 이어진 연결 요소의 갯수를 파악하는 문제이다. 문제는 방향 없는 무방향 그래프의 연결 요소를 구하는 것이기 때문에 간선이 존재하지 않는 정점도 연결 요소로 포함해서 갯수를 카운팅 해줘야 한다. 근데 문제가 연결 요소의 개수인대 연결 요소가 없는 정점 갯수는 왜구하는거지.. 풀이for(int i = 0;i
-
백준 2468번 JAVA 정리취준/알고리즘 2023. 7. 9. 19:33
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제를 이해하는데 꽤나 걸렸다. kt에이블 인적성 검사할 때도 그렇고 주말에 2개의 코테를 보고 나니 독해력이 정말 부족하구나 라는 점을 느껴서 책을 간간히 읽어야겠다는 생각이 들었다 1 2 2 3 3 2 1 1 3 배열의 원소는 어떤 지역의 높이 정보를 나타낸다. 문제에서 알고 싶은 것은 비가 올 경우 안전한 영역은 몇 개인지 알고 싶은 것이다. 비가 1만큼 오면 높이가 1인 지점이 물에 잠기고 2만큼 오면 높이가 1,2인 지점이 잠긴다고 가정한다. 비가 0만큼 올경..
-
백준 2667취준/알고리즘 2023. 7. 7. 13:01
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1은 집이 있는 곳을 의미하고 0은 집이 아닌 곳을 의미한다. 1을 집이라고 했을 때 집이 연결되어 있는 곳을 하나의 아파트 단지라고 한다. 이때 전체 단지의 갯수와 단지 내 집의 수를 오름차순으로 정렬하는 문제이다. 풀이 문제를 보고 BFS 문제를 해결해나가야 겠다는 큰 가닥을 잡았다. 전체 배열의 원소들을 탐색해나가면서 원소의 값이 1이고 아직 방문하지 않은 원소라면 방문하지 않은 아파트 단지라는 것이기 때문에 BFS 함수를 호출해서 인접한 연결된 아파트를 탐..
-
백준 2331취준/알고리즘 2023. 7. 6. 15:48
2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 시작 숫자가 주어지고 p의 값이 주어지면 숫자의 각 자릿수의 p제곱을 더한 값을 계속해 나가다가 보면 반복되는 구간이 발생한다. 이때 반복되는 구간을 제외한 수열의 개수를 구하면 된다. ex) 45 -> (4*4+5*5) 41 -> (4*4+1*1) 41 -> 41 -> 41... 시작 숫자가 45이고 p의 값이 2일경우 정답은 1이다. 풀이 문제가 간단하다. Collections에 계산되어 나온 값을 추가해 주고 만약 계산되어 나온 값이 Collections에 이미 존재한다면 해당 중복되어 나온 원소의 index가 곧 반복되지 않는 수열의 개수가 되기 때문에 중복되는 요..
-
백준 10451번취준/알고리즘 2023. 7. 5. 11:42
10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net index 1 2 3 4 5 6 7 8 9 수열 7 3 2 1 5 4 6 9 8 문제가 조금 헷갈려서 이해하는데 조금 시간이 걸렸다. 위와 같은 수열이 주어지면 index -> 수열은 연관관계가 있다고 생각하면 된다. 1부터 시작하면 1 -> 7 -> 6 -> 4 -> 1 2부터 시작하면 2 -> 3 -> 2 index와 주어진 수열은 하나의 그래프라고 생각하면 되고 수열로 이루어진 그래프는..