까만 창에 개발 블로그

# DP(Dynamic Programming)DP는 이해하는데 어려운 개념은 아니다. 문제에 적용하는 방법이나 방식, 점화식을 찾는데 어려움이 있다. 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 궁긍적인 문제를 해결할때 사용하는 문제푸는 방법의 패러다임이라고 볼 수 있다. 풀어서 설명하자면, 꺼내서 사용하기 쉬운 자료구조에 작은 문제에 대한 해결값을 담아둔뒤에 그 자료구조에서 꺼내어서 풀고자 하는 문제를 풀어나아가는 것이다.# LIS(Longest Increasing Subsequence)DP에서 가장 많이 등장하는 문제로 배열이 주어지면 만들 수 있는 증가하는 가장 긴 수열을 만드는 것이다. 사람의 직관으로 풀면 어렵지 않다. 하지만 컴퓨터는 어떻게 풀어야할까? 컴퓨터가 dp를..

📋 개요  🧩 문제https://www.acmicpc.net/problem/1753 📝  형식 📥 입력📤 출력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으..

📋 개요 골드문제를 도전해보려고 한다. 맨날 S5~S1만 푸니깐 전체적인 알고리즘을 모르고 학습하는거 같다. 그래프 이론이나 조합, BFS, DFS는 골드 수준에서 자주 나오는거 같다. 그리고 내 백준 레벨에 맞는 문제를 풀어야지 레벨이 빨리오르겠지!!! 인프런 인강으로 아주 쉬운문제도 2문제씩 풀며 뇌를 말랑말랑하게 하고 골드문제를 풀고 있다🧩 문제https://www.acmicpc.net/problem/14502📝  형식 📥 입력📤 출력첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다...

📋 개요문제를 풀때 항상 2시간을 잡고 푸는데 2시간이 넘을때까지 풀지 못했다. 부동소수점의 문제인거같아 문자열로 형변환을 해서 풀이를 했지만, 어떤 이유인지 모르게 실패가 되었다... 질문게시판의 모든 반례도 넣어줬는데... 그래서 답안에 대한 복기를 해볼까한다.🧩 문제https://www.acmicpc.net/problem/1206📝  형식 📥 입력📤 출력첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 각 문항의 평균 점수가 주어진다. N은 50보다 작거나 같은 자연수이고, 평균 점수는 0보다 크거나 같고, 10보다 작거나 같은 소수이다. 항상 소수점 셋째자리 까지 주어진다.첫째 줄에 설문조사에 참여한 사람의 수를 출력한다. 만약, 가능한 정답이 여러가지라면, 가장 작은 값을 출력한다.?..

📋 개요 백준 문제를 다시 풀기 시작했다. S1부터 다시 풀고 포스팅 할 예정이다. 이번 문제는 dfs를 활용해서 풀었다. 재귀에서 발생하는 call stack이 동작 원리를 이해하고 푸는것이 필요하 🧩 문제https://www.acmicpc.net/problem/1189 📝  형식 📥 입력📤 출력첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.첫 줄에 거리가 K인 가짓수를 출력한다.💡  예제🔢 번호📥 입력📤 출력13 4 6.....T......4 🥲  내 코드 및 정답코드HTML 삽입미리보기할 수 ..

📋 개요 잠깐 건강 이슈와 취준 이슈로 포스팅을 쉬었다. 하지만 알고리즘 문제는 꾸준히 풀었고 풀면서 복기하고 다시 문제를 되돌아보는것이 중요하다고 느꼈다. 포스팅을 꾸준히 이어나갈 예정이다. 기술적인 고민보다는 Raw하게 개발과 CS를 더 집중한다. 🧩 문제 https://www.acmicpc.net/problem/1389 📝 형식 📥 입력 📤 출력 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한..

📋 개요 이번문제는 hash map {key:value}의 빠른 검색으로 문제를 풀 수 있다. 처음에 구현으로 생각하고 문제를 풀었는데 "시간 초과"가 나서 hash map을 안 사용하고 vector로 풀었다. map의 빠른 검색시간을 활용해서 풀어야하는 문제로 파악하고 바로 코드를 수정했다. 🧩 문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 📝 형식 📥 입력 📤 출력 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈..

📋 개요 이번 문제도 풀면서 살짝 해매다가 2시간이 넘어버렸지만, 거의 답에 가까워졌다. 문제는 그리 어렵지 않았다. 좋은 구간의 조건을 알고 있다면 풀기 쉬운 문제다. 🧩 문제 https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 📝 형식 📥 입력 📤 출력 첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다. 첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다. 💡 예제 🔢 번호 📥 입력 📤 출력 1 4 1 7 14 10 2 4 2 5 4 8 13 24 30 10 5 3 5 10 20 30 40..

📋 개요 이어서 포스팅할 글은 난이도가 실4이다. 문제를 읽고 어떻게 풀지 아이디어가 떠오르지 않아서 결국 2시간을 다 소진하고 말았는데 답을 보니깐 크게 고민해야될 문제는 아니였다..... 앞으로 더 노력해야겠다ㅠㅠ 2024.02.27 - [Algorithm/Problem] - [BOJ]1380 귀걸이(S5, C++) [BOJ]1380 귀걸(S5, C++) 📋 개요 하루정도 휴식기를 갖고 감잡기 문제 Silver문제를 풀기로 했다. 일단 낮은 난이도의 단계부터 천천히 올라가야겠다. 저번에 푼 브1문제 이후로는 막힘없이 풀고 있다. 이번 풀이에도 걸 blaj2938.tistory.com 🧩 문제 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하..

📋 개요 하루정도 휴식기를 갖고 감잡기 문제 Silver문제를 풀기로 했다. 일단 낮은 난이도의 단계부터 천천히 올라가야겠다. 저번에 푼 브1문제 이후로는 막힘없이 풀고 있다. 이번 풀이에도 걸린 시간은 30min 정도였다. 이번에는 문자열과 구현 문제였다. cin으로 개행문자(\n)인 제거하기 부터 공백있는 문자열 받기와 같은 입력과 같은 문제도 나왔다. 🧩 문제 https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net 📝 형식 📥 입력 📤 출력 입..