문제풀이
-
[백준]1766: 문제집 - JAVA문제풀이/백준 2021. 2. 15. 15:21
[백준]1766: 문제집 www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 어제 위상정렬 공부한 기념으로 위상정렬 문제를 풀어보았다. 이 문제는 위상정렬 문제를 풀 줄 안다면 기본적인 개념을 이해하는데 어렵지 않다. 그러나 여기서 중요한 점은 문제 풀 순서의 조건중 3번인 가능한 쉬운 문제부터 풀어야 한다는 점이다. 예를들어서 예제입력을 보면, 4 -> 2, 3 -> 1순서대로 문제를 풀어야하고 3, 4의 진입간선이 모두 0..
-
[프로그래머스]정수 삼각형 - JAVA문제풀이/프로그래머스 2021. 2. 15. 13:43
[프로그래머스]정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 DP문제 치고 쉬운 DP문제여서 어렵지 않게 접근했다! 위치별로 누적 값을 저장하여주기 위해 dp를 2차원 배열로 만들어 주었다. 그리고 마지막에 배열의 마지막줄에서 최댓값을 찾아 반환해 주었다. 우선 문제의 예제를 분석해 보았다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 예제에 따르면 매개변수인 triangle은 이러한 형태로 전달된다. 이때 각 항목별로 값을 계산해 나가는 과정을 써보았다. dp[0][0..
-
[백준]10026: 적록색약 - JAVA문제풀이/백준 2021. 2. 14. 18:03
[백준]10026: 적록색약 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 탐색 문제로 dfs, bfs로 둘다 풀어도 될 듯하다. 적록색약이 아닌 사람이 봤을 때의 구역의 수는 일반적인 dfs와 똑같고, 적록색약인 사람의 구역의 수를 구할 때는 R, G인 값을 같다고 생각하고 체크해주었다. 이정도는 이제 어렵지 않다! 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26..
-
[백준]1939: 중량제한 - JAVA문제풀이/백준 2021. 2. 14. 15:56
[백준]1939: 중량제한 - JAVA www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 풀이 이 문제는 이분탐색 문제이며 이전에 풀었던 프로그래머스의 징검다리 건너기 문제와 비슷했다. 처음에는 인접행렬을 사용해서 풀었더니 메모리 초과가 났다. 그래서 다시 인접리스트로 바꾸어 풀어주었다. 이런 문제는 항상 인접행렬로 풀다보니 인접리스트르 바꾸는데 시간이 오래 걸렸다. 인접행렬은 N*N의 메모리 공간을 사용하므로 ..
-
[프로그래머스]N-Queen - JAVA문제풀이/프로그래머스 2021. 2. 14. 13:51
[프로그래머스]N-Queen programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 풀이 순열을 사용하여 풀었다. 순열로 퀸의 순서를 뽑아준 후, 뽑은 퀸을 이전의 뽑았던 퀸의 위치와 비교하여 뽑을 수 있는 위치라면 재귀함수를 사용해 순환적으로 호출해주었고, 뽑을 수 없는 위치라면(행이 같거나 대각선 위치에 존재하거나) 퀸을 뽑지 않았다. 뽑을 때는 1차원 배열을 이용해 각 인덱스가 하나의 열을 나타내도록 하였다. ..
-
[백준]17136: 색종이 붙이기 - JAVA문제풀이/백준 2021. 2. 13. 17:10
[백준]17136: 색종이 붙이기 - JAVA www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 완전 탐색을 통해서 풀어야 하는 구현 문제이다. 이번 문제는 풀고나니 어렵지 않았는데 구현하면서 생각해 줘야 하는 조건들을 놓쳐 다시 구현하느라 시간이 오래 걸렸다. 구현 문제는 꼭꼭 문제를 정확히 읽고 조건을 하나라도 빠트리지 않는 것이 가장 중요하다! 탐색 방향은 오른쪽 아래로만 확인하면 되므로 탐색할 때 x, y좌표 값에 따라 이동 방향을 지정해..
-
[프로그래머스]가장 먼 노드 - JAVA문제풀이/프로그래머스 2021. 2. 13. 14:33
[프로그래머스]가장 먼 노드 - JAVA programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 최단경로로 이동하며 답을 찾아야 하는 문제이므로 BFS를 사용했다. 인접 행렬을 사용했는데, boolean이 아닌 int형으로 선언하면 메모리 초과가 난다. 인접 리스트로 구현하면 메모리 초과가 나지 않는다고 한다. 기본적인 BFS와 동일한데 중요한 점은 반환 값이 가장 멀리 떨어진 노드의 수 라는 점이다. 이를 위해 qSize로 큐의 크기를 저장해 마지막 큐의 크기를 반환하도록 구현하였다. 가장 멀..
-
[백준]2225: 합분해 - JAVA문제풀이/백준 2021. 2. 12. 17:01
[백준]2225: 합분해 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 (dp는 너무 어려워..휴우) dp함수를 이차원 배열을 사용하여 표현하였다. 각각의 인덱스는 dp[n][k]일때 0부터 n까지의 정수로 k를 표현할 수 있는 경우의 수를 저장하도록 하였다. 우선 예제입력인 20,2의 경우의 수를 모두 찾아 보았다. 0, 20 20, 0 1, 19 19, 1 2, 18 18, 2 3, 17 17, 3 4, 16 16, 4 5, 15 15, 5 6, 14 14, 6 7, 13 13, 7 8, 12 12, 8 9, 11 11, 9 10, 10 더하는 순서가 다르면 다른 경우로 계..