백준99 [백준] 2108 - 통계학 (Python) 문제 출처 : www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 풀이 : 주어진대로 풀면 된다. 대부분 어려울 것 없이 풀릴텐데 최빈값 푸는 부분만 신경쓰면 쉽게 풀릴꺼라고 생각한다. 나의 경우 count 정렬을 이용하여 풀었다. idx를 숫자라고 생각하고 count[idx]의 값은 idx 값이 나온 횟수를 저장해주었다. 이때 생각해야하는 것이 count 배열의 크기인데 문제에서 보면 주어지는 정수의 절댓값은 4000이 넘지 않는다. 즉 배열의 크기는 8001 크기면 충분하다. 또한 idx.. 2021. 1. 25. [백준] 14504 - 로봇청소기 (Python) 문제 출처 : acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀이 : 전형적인 삼성 스타일의 구현, 시물레이션 문제이다. 굉장히 친절하게도 동작이 어떻게 되는지까지 친절하게 되어있다. 구현 문제를 접근할땐 우선 구현해야하는 상황을 먼저 살펴보고, 입력값을 살펴보며 푼다. 구현해야하는 상황만 보았을 때 살짝 이해가 안되는 경우가 더러 있는데(국어도 못하는데 코딩을 해야한다니..) 입력값을 살펴보면서 예제를 보면 이해가 되는 경우가 많다. 이 문제의 경우 격자.. 2021. 1. 25. [백준] 1463 - 1로 만들기 (C++) 문제 출처 : www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 : 입력값 n에 대해서 3으로 나눌수 있다면 3으로 나눠보고, 2로 나눌 수 있다면 2로 나눠보고 , 나머지 경우에 대해서 생각해보시는 식으로 점화식을 설계하였다. 재귀 함수를 통해 작성하였는데 통과는 하였다. 푸는 과정에서 느낀점은 DFS 처럼 이미 답이 나왔는데도 그 외의 경우도 모두 확인하는 경우가 나오는데 C++ 언어 특성상 속도에 강점이 있기 때문에 통과한거라고 생각한다(python으로 똑같은 로직으로 짠다면 시간초과가 난다) #include #include using namespace st.. 2021. 1. 13. [백준] 10844 - 쉬운 계단 수 (Python) 문제 출처 : www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 : 전형적인 DP문제이다. 다만 처음 DP를 풀었다면 2차원으로 볼 생각을 못해서 어려웠을 꺼 같은데 저번에 2차원으로 푼 경험이 있기 때문에 2차원 배열을 이용한 DP로 문제를 풀었다. DP 문제는 식을 세우기만 하면 의외로 쉽게 풀리는 경향이 있는듯 하다. 다음과 같이 DP식을 정하고 규칙을 찾아보았다. DP[i][j] = 길이 i에 가장 오른쪽 자리 숫자가 j 일때 존재하는 계단수의 개수 i/j 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 .. 2021. 1. 13. 이전 1 ··· 19 20 21 22 23 24 25 다음 반응형
