전체 글102 [C] 14940: 쉬운 최단거리 전형적인 BFS 문제로 각 목표지점까지의 거리를 출력하면 된다. 이때 각 거리를 저장하는 배열은 visit를 이용하였고 queue를 이용하여 bfs를 구현하였다. 주의해야할 점은 1.거리를 계산하기 위해 queue[2][] 부분을 거리를 위한 공간으로 할당하였고 queue[2][rear]=queue[2][front]+1; 를 통해 거리를 구할 수 있다. 2. 2가 있던 자리를 visit 배열에서 1로 할당했기 때문에 마지막에 출력하는 부분에서 0이 출력하도록 바꿔야한다. 이건 꼭 좀 잘하자! 맨날 풀었던 문제인데 bfs 구현하는데 이상한 곳에서 시간이 걸렸다. 특히 이번에는 front와 rear을 모두 1로 초기화해놓고 while문 들어가는 조건을 front 반복문 들어가는 조건과 다차원배열 index .. 2023. 8. 21. [C] 2293: 동전 1 시간이 엄청 오래걸려서 풀었다.. 일단 맨 처음에는 재귀함수를 이용한 Top-Down 방식으로 풀려고 노력했는데 예외처리를 해줘도 지수적으로 증가하기 때문에 자꾸 시간초과가 났다. 여기서 주의해야할 점은 각각의 코인의 가치에 따라서 dp를 따로 생각해야한다는 점이다. 결국 마지막에는 하나로 모아 풀어야하지만 처음에 생각은 따로따로 해야한다는 점인데 그 결과 구현을 하자면 dp[i]+=dp[i-price[j]]; 가 된다 1. j번째 동전을 포함하지 않은 상태에서 i의 가치를 표현하기 위해서는 j-1번쨰 동전까지만을 이용하여 만들 수 있는 경우의 수를 구하면 되기 때문에 dp[i]+=dp[i]...가 된다. 2. j번째 동전을 포함한 상태라는 뜻은 결국 가치가 i-price[j]가 되는 경우의 수를 구하면.. 2023. 8. 21. [C] 1929: 소수 구하기 사실 이 문제가 Dynamic Programming로 푸는 것은 아니다. DP는 점화식을 이용하여 i번째까지 구한 것을 저장하고 이것을 i+1번째를 구할 때 이용하는 것이다. 사실 이걸 그대로 사용하고 있지는 않다. 다만 DP에 쓰이는 방법 일부를 사용하고 있다. i번째 수가 소수인지를 각각 구하는 것이 아니라 1부터 탐색을 할때 소수이면 그 수의 배수들을 따로 저장하여 소수인지 확인하면 된다. 즉 Bottom-up 방식으로 생각해서 구현하면 된다. #include int dp[1000001]; int main(void) { int m,n; scanf("%d %d",&m,&n); for(int i=2;i=m && i 2023. 8. 10. [C] 1004: 어린 왕자 일단 문제는 예전에 원의 방정식에서 배웠던 것 처럼 출발점과 도착점이 각각 원 안의 있냐 없냐로 최소의 행성계 진입/이탈 횟수가 정해진다. 따라서 출발지/도착지와 원의 중점 사이의 거리가 원의 반지름보다 작다면 안에 있다는 것을 알 수 있다. 여기서 주의해야할 점은 출발점과 도착점이 모두 한 원 안에 있을 수 있다는 것이다. 그래서 한 원 안에 있는 경우의 수도 뺴줘야하기 때문에 tmp1과 tmp2를 이용해 출발점과 도착점이 각각 원안에 있는지 확인한 후 두개의 합, 즉 tmp1+tmp2==1인 경우에만 cnt++를 해줌으로써 문제를 풀었다. 기억해야할 점 1. pow 함수와 sqrt 함수는 모두 double형 변수에 대해서만 연산이 가능하고 다른 연산을 할때도, 예를 들어 나눌때, 계산결과가 달라질 수.. 2023. 8. 8. 이전 1 ··· 11 12 13 14 15 16 17 ··· 26 다음