맞는데 왜 틀림

문제 설명입력으로 테스트 케이스 C가 주어진다.C의 갯수만큼 자연수 N이 주어진다.각 테스트 케이스마다 0,0에서 보이는 점의 갯수를 출력한다.문제 풀이사용하는 알고리즘 설명이 문제는 누적합(Prefix Sum)의 개념과 동적 프로그래밍(Dynamic Programming)의 개념이 같이 들어가있는 문제이다.보통 누적합과 동적 프로그래밍은 같이 사용하는 경우가 많다고 한다. 이전 DP 문제들에서 i번째 값은 i-1번째 값과 i번째 값 중 최대값 이런식으로 작은 것부터 계산해서 올라온 것을 기억할 것이다.이 방식이 누적합 방식이다. 예시이 문제도 예를 들어 설명하겠다.2,2를 구하려면1,1의 점의 수는 3이다.1,2의 점의 수는 4이다.2,1의 점의 수는 4이다.그렇다면 2,2의 점의 수는 1,2의 점의 ..

문제 설명테스트 케이스 T가 주어진다.테스트 케이스별로 가로 세로의 블럭 수를 C와 R로 주어진다.C*R의 갯수만큼 블럭이 각각 칸에 몇 개가 쌓여있는지 주어진다.블럭에 가려지지 않은 보이는 면을 모두 구하여 출력한다.주의사항블럭에 가려진 면만 뺀다.다시 말해서 바닥면은 가려진 것으로 치지 않는다.문제 풀이가로 세로의 갯수만큼 입력을 받은 후 블럭끼리 가려진 면을 빼는 문제이다.기하학에 구현의 알고리즘으로 바로 구현하였다. 우선 위 예시 입력을 통해 설명해보겠다.423121010001여기서 1,1 인덱스인 1의 경우를 살펴보겠다우선 1개의 블럭이므로 총 면의 수는 1*4 + 2로 총 6면을 가지고 있다. 그리고 이웃 면들을 검사해보자.이웃면이 0,1 인덱스의 2개 블럭, 1,0 인덱스의 2개 블럭이 존재..

문제 설명총 등산 거리 L, 휴식 지점 갯수 N, 1m 가는데 존이 걸리는 시간 rF, 1m 가는데 베시가 걸리는 시간 rB가 주어진다.다음 줄부터 각 휴식지점의 거리 xi와 풀의 맛 ci가 주어진다.최대로 얻을 수 있는 풀의 맛을 출력한다.조건존에게 추월당하면 안된다.문제 풀이그리디 알고리즘(Greedy Algorithm)으로 푸는 문제이다.그리디 알고리즘(Greedy Algorithm)이란?각 단계에서 그 순간에 최적이라고 생각되는 선택을 반복하여 최종적인 해답에 도달하는 알고리즘 설계 기법이다.탐욕 알고리즘으로도 불린다. 따라서 각 단계에서 최적의 선택을 할 것인데, 여기서는 뒤에서부터 탐색을 하였다.문제의 예제 입력과 출력으로 설명을 해보겠다. 입력10 2 4 37 28 1출력15 최대 맛을 가지..

저번과 이어서 DP 문제를 연습하기 위해 가져왔다.이번에는 AI의 도움 없이 혼자 풀이하였다.문제 설명미로의 크기인 1차원 배열의 크기 N과 미로의 정보인 Ai가 주어진다.미로의 정보에는 이동할 수 있는 칸의 수가 쓰여져있다.N번째 칸으로 갈 때 최소 점프 수를 구하여라.문제 풀이문제를 보자마자 저번 포스트에서 다룬 11053 문제의 접근법이 떠올랐다.같은 DP문제로 점화식을 통해 작은 문제서부터 큰 문제를 해결해나가는 방식을 똑같이 사용해보겠다.for i for j if (i-j)(두 칸 사이의 거리) result[i] = Min(result[i], result[j] + 1)(i가 최종 목적지일 경우 최소 이동 거리)여기서 Min으로 작은 값을 찾기 위해서는 result를 0으로 초기화 하면 안되고 예..

문제 설명첫째 줄에 수열 크기 A 입력둘째 줄에 수열 입력수열에서의 증가하는 부분이 가장 긴 부분의 길이를 출력문제 풀이처음에는 DP라서 점화식을 구해서 재귀로 푸는 문제로 이해했다.따라서 최대값과 그 이전의 값(최대값보다 작은 최대값)을 저장해서 인접 행렬을 순차적으로 탐색하였다.이 방법은 자기보다 작은 수를 만났을 때 초기화해서 다시 탐색해서 비교해야 하는 부분에서 잘못된 방법이라는 것을 느꼈다. AI한테 도움을 받아 접근 방식에 대한 아이디어를 받은 부분은 다음과 같이 접근하였다.수열을 제일 작은 수열에서부터 하나씩 크기를 키워 증가하는 부분이 가장 길 때의 길이를 비교하는 방식이다.예를 들면 아래와 같다.예시 입력값610 20 10 30 20 50위와 같이 입력을 받은 경우A1 = [10]A2 =..

문제 설명입력 첫번째 줄로 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 번호 X가 주어짐두번째 줄부터 M개의 줄로 A B의 형태로 A->B로 가는 간선 정보가 주어짐X로부터 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력, 없는 경우 -1 출력문제 풀이이전과 동일하게 bfs 알고리즘의 문제이다. 따라서 Queue 자료형과 방문기록을 위한 코드를 사용했다. 아래는 최종 코드다.더보기using System;using System.Collections.Generic;using System.Linq;namespace StudyCS{ class Program { public class Vertex { public Vertex() ..

문제 설명영어로 되어있지만 문제 해석을 하자면 데이터 셋의 갯수인 K, 부서진 수도관의 갯수 n, 수리트럭의 이동속도 v와 부서진 수도관의 정보들인 좌표 x,y 그리고 누수가 될 시간 t, 누수량 r이 주어졌을 때 누수량이 최소로 되게 하는 경로를 찾아서 최소 누수량을 출력하는 문제이다. 문제에 쓰이는 알고리즘 파악이 문제는 백트래킹으로 구분되어 있다.백트래킹이란?브루트포스 알고리즘과 dfs(깊이 우선 탐색) 알고리즘과 유사하지만 해당 경로가 답을 찾을 가능성이 없으면 마지막으로 기록해둔 정점으로 돌아가는 로직이 추가된 방법이다. 문제 풀이아래는 코드이다.더보기using System;using System.Collections.Generic;namespace StudyCS{ public struct..

백준 온라인 코딩 문제풀이https://www.acmicpc.net/ Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net단계별로 풀어보기 - 그래프와 순회 단계 - 24479번 알고리즘 수업 - 깊이 우선 탐색 1 문제이다.우선 깊이 우선 탐색(dfs)를 처음 풀어보기 때문에 어떤 방식으로 구현이 되어야 하는지 알아보겠다 깊이 우선 탐색(dfs)란깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리에서 한 경로를 따라 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 알고리즘이다. 이 과정에서 재귀 함수나 스택 자료구조를 사용해 구현할 수..

백준 온라인 코딩 문제풀이https://www.acmicpc.net/ Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net기하학 1002번 터렛 문제좌표 (x1, y1), (x2, y2)와 한 점까지의 거리를 각각 r1, r2로 주어졌을 때 몇개의 점이 겹치는지를 구하는 문제다. 우선 다음과 같이 접근해보았다결국 좌표 두 개에서 거리가 주어졌을 때 있을 수 있는 좌표는 두 원의 교점으로 볼 수 있다. 따라서 경우의 수는1. 원이 완벽하게 겹칠 때2. 두 점에서 교점이 있을 때3. 한 점에서 교점이 있을 때4. 교점이 없을 때이렇게 4가지 경우의 수가 있다. 그리고 교점의 좌표를 구할 이유가 없..

백준 온라인 코딩 문제풀이https://www.acmicpc.net/ Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net11399번 - ATM 문제  우선 알고리즘 방식이 Greedy Algorithm(탐욕 알고리즘)으로 기재가 되어있다. 따라서 우선 탐욕 알고리즘이 무엇인지부터 정리해보았다. 탐욕 알고리즘- 현재 상황에서 가장 최적이라고 생각되는 선택을 반복적으로 수행- 즉, 미래를 고려하지 않고 매 순간 최선의 선택을 하는 방식 특징탐욕 선택 속성 (Greedy Choice Property)- 현재의 선택이 이후의 결과에 영향을 미치지 않아야 한다. 최적 부분 구조 (Optimal Sub..