지민 개발 블로그

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net 다음 문제는 dfs와 bfs의 가장 기초적인 문제다.  문제 풀이법은 딱히 중요한건 아닌 것 같고, 이 문제를 사실 9개월 전에 한번 풀었다가 감이 죽은 지금 다시 한번 풀었는데 메모리랑 실행시간이 너무 크게 비교가 돼서...(물론 9개월 전 코드가 더 아름다웠다.) 마음이 아파서 왜 그런지 비교해보도록 하겠다. 9개월 전 똑똑했던 나의 코드#include #in..

대단히 쉬운 문제지만.. C언어 학습을 위해서 여러 방법으로 풀어보았다. => 근데 역시 매우 쉬운..문제임. 그러나 어디든 도움이 되겠지?! ① 단순 반복문으로 풀어가기 #include int main(void){ int N, ans = 1; scanf("%d",&N); for (int i = 1; i

https://www.acmicpc.net/problem/11047 11047번: 동전 0첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)www.acmicpc.net풀이과정①문제 바라보기기본적인 그리디 문제다.어렵게 낼 수 있다면 굉장히 어렵게 낼 수 있는 문제인데 이 문제의 경우에는 굉장히 기본기본기본적인 문제같다. ②아이디어 펼치기연산자 %와 //을 활용하면 간단히 풀릴 것이다.몫을 구해서 만약 1 이상이라면 남는 돈은 %한 값이 되는거고 빠져나간 동전의 개수는 //가 되는 것이다.이때 필요한 동..

https://www.acmicpc.net/problem/11724 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 풀이과정①문제 바라보기간단한 graph이론 문제다. DFS문제고, 이해를 위해서 문제에서 제시한 예제 2개를 간선과 노드로 표현해봤다.위의 그림을 보면 1,2,5가 연결되어있고 3,4,6이 연결되어있음을 확일할 수 있다.  따라서 출력값이 2가 되는 것이며,두번째 그림을 보면 1~6이 모두 어떻게든 연결되어있기에 출력값이 1이 됨을 확인할..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net풀이과정①문제 들여다보기이 문항은 앞전에 푼 11053문제에서 아주 살짝 업그레이드 된 버전의 문제이다.https://stopmin.tistory.com/46 [백준] 11053번 가장 긴 증가하는 부분수열 (Python)https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net풀이과정①문제 바라보기N으로 전체 수열의 길이를 받고, 다음줄에 array가 입력된다.array에서 몇 개의 수를 지움으로써 만들 수 있는 가장 긴 증가하는 수열의 길이를 인쇄하는 문제다. ②아이디어 열기이 문제는 동적계획법으로 해결이 된다.이중 for문을 활용하여서 해결되는 문제였다.현재 해당하는 위치의 숫자보다 앞에 있는..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net풀이과정①문제 바라보기DP문제임은 자명하다. 계단 오르기 문제랑 굉장히 유사하게 느껴졌다.더보기이것이 계단오르기다.https://stopmin.tistory.com/42 [백준] 2579번 계단오르기 (Python)https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www...

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net풀이과정①문제 바라보기DP문제인데 규칙을 발견해야한다고 생각했다. 0과 9의 경우 특별한 Case이기에 따로 분류해서 처리해야 한다. ②아이디어 펼치기아래는 수형도이다.N == 1일 경우, 0은 불가능하고 나머지 1~9는 모두 가짓수가 1개가 된다.N == 2일 때 부터 규칙이 발견이 되는데 편의상 N이 3~4일 때로 예시를 들었다. dp[4][0]으로 가기 위한 방법의 개수는 dp[3][1] 온전히 갖게 된다.dp[4][9]으로 가기 위한 방법의 개수는 dp[3][8] 온전히 갖게 된다.나머지 경우에서는 모두 양쪽..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net풀이 과정①문제 바라보기처음에 이 문제가 Greedy 문제인 줄 알았다. 그러나 알고보니 DP문제! 뭔가 greedy로 풀릴 것 같기도하다.이 문제도 메모이제이션 기법으로 풀릴 것이다. 문제에서 내가 할 수 있는 조치는 다음과 같다.X가 3으로 나누어  떨어지면 3으로 나눈다.X가 2로 나누어 떨어지면 2로 나눈다.1을 뺀다. ②아이디어 펼치기자명한 사실이 있다. N을 만드는 데 x번의 단계가 필요하다면 그냥 -1만 가능하다고 할 때, N+1은 x+1단계가 필요하다. 이 문제를 풀기 위해서는 dp 테이블이 필요하고 ..

https://www.acmicpc.net/problem/2579과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2579" data-og-url="https://www.acmicpc.net/problem/2579" data-og-image="https://blog.kakaocdn.net/dna/cbS18u/hyPBHwY36Z/AAAAAAAAAAAAAAAAAAAAAJUaaP6YR4uVkSVG4D_O0uat9zDAIRrvXGaDyzSwlKtg/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1756652399&allow_ip=&allow_referer=&signature=2hN0ekF92zvVyhgf4m%2F068E1aHc%3D