문제 출처 : https://www.acmicpc.net/problem/2564분류 : 구현 백준 2564 경비원최소 거리 구하기구현 포인트1) 특정 점을 기준으로 위치를 다시 표현동, 서, 남, 북에 따라 점의 위치를 따로 다루기에는 코드가 길어지고 복잡해 지므로조금만 더 생각해 보면 왼쪽 상단을 0으로 두고, 시계방향으로 각 점들의 위치를 나타내면 간단해 진다. 코드는 아래 같다.123456789101112131415161718192021#include #include int main() { int w, h, n, sum=0; scanf("%d %d %d", &w, &h, &n); int d, o, *a = new int[n+1]; for (int i = 0; i
[1068] 트리
문제 출처 : https://www.acmicpc.net/problem/1068분류 : 트리 백준 1068 트리트리의 노드를 삭제시 남은 리프 노드의 갯수를 구하라구현 포인트1) 트리를 간단하게 구현(배열로) 2) Bottom-up으로 리프의 갯수를 파악한다. 우선 첫번째로 풀었던 방식은 각 노드마다 각 노드가 root인 sub-tree의 리프노드 갯수를 가지고 있게 한뒤노드가 삭제되면 전체 리프노드 갯수에서 삭제된 리프노드의 갯수를 삭제하도록 했다. 이렇게 생각하면 고려해야 하는 부분이 더 생긴다. 위와 같이 4번노드를 삭제 할 때 자식 노드가 1개로 이어진 경우 위와 같은 논리는 문제가 생긴다.이런 경우를 고려하여 답을 찾도록 추가적으로 구현을 해주어야 했다. 1234567891011121314151..
문제 출처 : https://www.acmicpc.net/problem/2491분류 : 구현 백준 2491 수열가장 긴 단조증가 혹은 단조감소 수열의 길이를 찾아라구현 포인트1) 증가하는 것만 고려해서 찾고, 감소하는 것만 고려해서 최대 길이를 찾는다. 2) 너무 복잡하게 생각하지 말 것(입력이 최대 100,000개이다.) 이 문제에 대한 리뷰가 필요했던 이유는 너무 복잡하게 생각했다는 것이였다.증가인 상태와 감소인 상태, 감소에서 증가로 가는 상태 등등 여러 상태들을 표현하려고 했다.그러다 보니 코드가 길어지고 복잡해 졌다.우선 처음에 구현된 코드는 아래와 같다...매우 가독성이 떨어지는..;; 반성해야 할 것 같다.. 참고로 여기서는 flag로 상태 전이를 이용하여 구현하였다..너무 어렵게 생각했다...
문제 출처 : https://www.acmicpc.net/problem/11403분류 : 그래프 백트래킹 백준 11403 경로찾기각 정점간의 연결 여부를 확인하라구현 포인트1) 정점이 100개 밖에 안되므로 뭘 써도 제한시간 1초안에 가능하다. (BFS, DFS, Flyod-Warshall) 2) 자기 자신간의 연결여부를 확인해야 한다. 자기 자신으로 돌아오는 싸이클의 여부 판단정답률이 높고 쉬운 문제임에도 여기다 적는 이유는 처음에 2번을 고려하지 않았기에..ㅎㅎ;;;구현된 코드는 아래와 같다. (BFS) 1234567891011121314151617181920212223242526272829303132333435#include#include#includeusing namespace std; int m..
문제 출처 : https://www.acmicpc.net/problem/1016 분류 : 소수판별법 백준 1016 제곱ㄴㄴ수주어진 범위에서 제곱수로 나누어 떨어지지 않는 숫자의 개수를 구하라구현 포인트1) 일반 정수의 제곱의 배수보다는 소수의 제곱을 고려하는 것이 더 경우의 수가 적어진다. (소수의 제곱의 배수만 고려해도 모든 경우를 커버할 수 있기 때문이다.) 2) 소수의 제곱을 고려해서 배수의 갯수를 뺄 때 중복되는 것이 있음에 주의해야 한다.(ex, 16의 9배 = 9의 16배) 3) 계산과정에서 int범위가 넘어 갈 수 있음에 유의해야 한다. 구현된 코드는 아래와 같다.소수는 에라토스테네스의 체를 이용하였고,중복된 수는 갯수에서 제외하기 위해 check라는 배열을 만들어서 제곱의 배수는 0으로 만..
문제 출처 : https://www.acmicpc.net/problem/1013분류 : 오토마타, 정규표현식 백준 1013 Contact정규표현식 (100+1+|01)+ 을 만족하는 문자열을 찾아라처음에 풀때는 아무 생각없이 state transition graph를 그려서 그래프를 그대로 코드로 옮기려고 하였다.그 결과 나오게 된 코드는 아래와 같다.종결상태와 여러 입력에 대해 state를 바꾸는 오토마타를 만든 것과 다름이 없다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081..
문제 출처 : https://www.acmicpc.net/problem/11047분류 : 그리디 백준 11047 동전0동전을 N종류 가지고 있을 때 K원을 만드는 최소 동전의 개수아무런 조건이 없다고 가정할 때, 큰 것 부터 골라야 최소를 만들 수 있을까? 다음의 예를 보자. 우리는 다음 주어진 가격의 동전을 가지고 있다고 하자.10, 50, 60100원을 만드려고 그리디하게 구하면 60,10,10,10,10이 나오는데실제로 100원을 만드는 최소는 50,50이다.즉, 무조건 큰 것 부터 고르면 안된다는 말이 된다. 그렇다면 어떻게 그리디하게 동전의 최소 갯수를 만들 수 있을까?다시 예로 돌아가 보자.5, 40, 70으로 120원을 만들 경우 70, 40, 5, 5 또는 40, 40, 40이 된다. 이 ..