🖥️Computer Science/알고리즘

백준🔗 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 간단 풀이 사실 오늘 DP 연습하려고 DP 분류에서 문제를 선택해서 풀기 시작했다. 그런데 문제를 읽으면서 아무리 생각해봐도 DFS밖에 떠오르지 않아서 일단 DFS로 구현해서 통과했다. DFS 구현 자체는 문제에서 주어진 상황을 그대로 따라서 구현하면 되기 때문에 어려울 것은 없는 것 같다. 현재 파이프의 방향에 따라 분류를 나누고, 이동하고자 하는 방향으로 이동 가능한지 여부를 따져서 이동한다. (배열이 벗어나지 않아야 하고..

백준🔗 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 문제 간단 풀이 오늘 들은 알고리즘 특강에서 '트라이' 자료구조에 대해 배웠다. 그래서 트라이를 연습해볼 수 있는 문제를 풀어봤다. 우선, 트라이는 문자열 집합을 관리하는 트리이다. 정점마다 알파벳이 하나씩 대응되어 들어있고, 접두사와 접미사 관련한 문제에서 많이 사용되는 자료구조라고 한다. 단어가 많을수록 앞이 겹치는 단어들이 많아지기 때문에 이를 효율적으로 탐색할 수 ..

백준🔗 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 간단 풀이 구현하고 나니 코드 길이는 짧은데 풀이 과정은 쉽지 않았다.. 행렬은 입력으로 주어진 순서를 바꾸면 안되기 때문에 주어진 순서에서 어떤 행렬끼리 먼저 계산할 것인지 선택만 할 수 있다. 그러나 어떤 방식으로 선택해 나가야 할 것인지, 중간중간 계산값은 어떻게 저장해야 할 지 감이 잘 오지 않았다. 어찌됐든 행렬 곱셈을 반복적으로 수행하기 때문에 dp배열을 사용해보자 생각을 했다. 처음에는 1차원 배열을 생각해서 dp[i] : i..

백준🔗 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 간단 풀이 2023.07.03 - [알고리즘/백준] - [백준/JAVA] 1182_부분수열의 합 ☝️이 문제를 풀어보려다 감이 잘 오지 않아서 "부분수열의 합"을 먼저 풀고 왔다. 두 문제는 얼핏 보면 똑같은 문제처럼 보이지만 한 가지 다른 점이 있다. N의 범위가 최대 40으로 2배가 된 것인데 이게 어떤 의미를 가지는지 먼저 생각해 보았다. 원소가 N개인 수열은 2^N개의 부분수열을 갖는다. N이 20일 때..

백준🔗 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 간단 풀이 "1208_부분수열의 합 2" 문제를 풀려다가 감이 잘 잡히지 않아서 이 문제부터 먼저 풀어 보았다. 수열의 원소 개수인 N이 최대 20이기 때문에 부분 수열은 최대 2^20개가 있을 수 있다. 2^20 = (2^10)*(2^10) => 대략 100만 정도.. (정확한 계산값은 2^20 = 1,048,576) 하나의 부분 순열에 대해 원소의 합을 구하는 데는 최대 N만큼이 든다고 하면 최대 O(N*2^N..

백준🔗 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 간단 풀이 간단한 1차원 dp 문제이다. dp[i] : i원을 만들 때 사용하는 동전의 개수 위와 같이 정의하고, 주어진 n가지 동전 각각을 쓰거나 or 쓰지 않거나의 경우를 모두 비교해서 최소 개수로 k원을 만드는 경우를 찾는다. 한 가지 주의해야 할 점은, 처음에 dp배열을 Integer.MAX_VALUE로 초기화 했는데, 계산 과정에서 dp[i - coin[j]] + 1 이렇게 1을 더하게 되기 때문에 Integ..

백준🔗 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 간단 풀이 요새 백준 문제집 '삼성 SW 역량 테스트 기출 문제'에 있는 문제들을 푸는 중이다. 아무래도 구현 문제가 많은 것 같은데, 오늘 문제도 문제에서 주어진 조건에 따라 차근차근 구현해 나가니 쉽게 풀 수 있었다. 그래서 따로 풀이를 적을 내용은 없는 것 같지만, 한 가지만 얘기해보자면 문제에서 입력 부분에 '방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 ..

백준🔗 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 간단 풀이 문제 상황 자체는 쉬웠는데 안쪽에 있는 공간과 바깥에 있는 공간을 어떻게 구분해야 할 지 고민이 됐다. 그래서 생각해낸 풀이는 1) BFS를 수행하며 치즈 바깥 공간을 -1로 바꾼다. 2) 가장자리에 있는 치즈를 찾아서 2로 바꾼다. (2차원 배열을 전부 탐색하며 상하좌우로 -1이 하나라도 있으면 가장자리 치즈라고 판단) 3) 다시 한 번 전체 탐색을 하며 2를 -1로 바꾸면서(가장자리에 있는 치즈 녹이기) 1인 개수를 세서 남은 치즈 조각을 카운트한다. 4..