전체 글

[baekjoon 12852] 1로 만들기 2 (DP) (C++)

www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 의 조건을 갖고 문제를 푼다. 무턱대고 2나 3으로 나뉘어서 나누고 연산을 세주면 안 되고 최솟값을 저장해야 한다. 10의 경우로 보면 2로 나뉘어서 10 -> 5 -> 4 -> 2 -> 1 이면 5번이지만 1을 먼저 빼고 시..

[baekjoon 17070] 파이프 옮기기 1 (DFS, 백트래킹) (C++)

www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프를 옮겨서 주어진 사이즈의 끝점까지 옮길 수 있는 경우의 수를 찾는 문제이다. 신경 써줘야 할 점은 가로로 옮긴 다음엔 가로 OR 대각선 세로로 올긴 다음엔 세로 OR 대각선 대각선으로 옮긴 다음엔 가로 OR 세로 OR 대각선이 모두 가능하다. 또한 대각선으로 옮길 때에는 다음 나아갈 점뿐만 아니라 그 점의 위와 왼쪽 또한 벽이 없어야 한다. 이 조건만 잘 지켜주면서 모든 경우의 ..

[baekjoon 1238] 파티 (플로이드와샬, 다익스트라) (C++)

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 집(N)마다 목표점까지 왕복하는 최단 거리 중 가장 큰 값을 찾는 문제이다. 처음에 각 노드 당 최단거리를 구하는 것이기 때문에 플로이드 와샬 알고리즘을 생각했지만, N이 1000으로 O(N^3)의 시간 복잡도를 가지는 플로이드 와샬로 풀리지 않을 것으로 생각했다. 결론적으로는 통과됐다. (왜지?) 플로이드로 풀고, 더 좋은 방법이 없을까 하고 찾아봤더니 다익스트라를 이용해서 ..

[프로그래머스 LV3] 가장 먼 노드 (BFS) [C++]

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1번 노드로부터 최단 거리 중 가장 먼 노드들의 개수를 찾는 것이다. 즉, 1번으로부터 4번 5번 6번 노드의 최단 거리가 3이고 그 거리가 그래프에서 1번과 가장 먼 거리면 정답은 3이다. 따라서 나는 input을 인접 리스트에 저장하고, BFS를 수행해서 최단거리를 찾으면 되겠다고 생각했다. #include #include #include using namespace std; vector v[20001]; int check[20001], re..

[Tensorflow-YOLO4] Window 환경에서 YOLO4 모델을 통해 객체 검출해보기.

우리의 프로젝트는 실시간으로 객체를 검출해야 하는 파트가 있기 때문에 YOLO 모델을 선택하기로 했다. 그리고 리눅스 서버에서 환경 설정하기 전 연습 삼아서 로컬 Window 환경에서 yolo4-tensor flow 버전을 돌려보았다. 일단 환경설정은 Python ver 3.7과 Tensorflow 2.3.0rc0이다. 나는 아나콘다 환경에서 진행했기에 처음 가상 환경을 설정해주었다. 아나콘다를 사용하지 않는다면 명령 프롬포트(CMD) 들어가서 2번에 있는 pip install tensorflow 부터 바로 진행하면 된다. 1. Anaconda Prompt에서 가상 환경 생성. conda create -n [영어 이름] python=3.7 나는 conda create -n yolo4 python=3.7로..

[baekjoon 1937] 욕심쟁이 판다 (DFS+DP) (C++)

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 판다는 상하좌우 움직일 수 있으며, 자기가 먹은 대나무보다 더 많은 대나무가 있어야 움직인다. 만약 네 방향 모두 현재 먹은 대나무보다 적으면 움직이지 않고 죽어버린다고 한다.. 즉, 현재보다 더 큰 수가 있어야 움직이며, 그 경로들 중 최장거리를 출력하면 된다. 따라서 DFS를 하되, 만약에 모든 칸에서 DFS를 돌려서 장거리를 계산한다고 하면 매번 n^2 만큼에 그걸 또 n^2번 돌리니 시간 복잡도..

네이버 검색 엔진 등록, 티스토리 사이트맵 등록하기.

1. 네이버 웹마스터 도구 들어가기 searchadvisor.naver.com/ 네이버 서치어드바이저 네이버 서치어드바이저와 함께 당신의 웹사이트를 성장시켜보세요 searchadvisor.naver.com 2. 로그인 후 웹마스터 도구 클릭하기 3. 사이트맵 등록하기 -> 티스토리는 사이트맵이 개편돼서 생성할 필요 없이 자동으로 만들어져있다고 한다. 나의 티스토리 블로그 관리 들어간 다음 관리 탭의 블로그를 들어가 준다. 사이트맵 주소를 찾을 수 있다. 이후 아까 네이버 웹마스터 도구란에서 요청 - 사이트맵 제출 - 에서 /이후 sitemap.xml를 입력해준다. 끝!

[baekjoon 11404] 플로이드 (플로이드-와샬) (C++)

www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 기본적인 플로이드 와샬 알고리즘을 사용해서 푸는 문제이다. 다익스트라와 같이 최단 거리를 찾는 알고리즘이지만, 차이점을 한번 비교해보았다. 다익스트라 VS 플로이드-와샬 1. 최단거리를 찾는 경로 - 다익스트라 : 어떤 한 점에서 목적지까지의 최단 거리를 업데이트 - 플로이드 : 모든 정점에서 모든 정점까지의 최단 거리 -> 단일 경로의 최단 거리를 찾는 것은 다익스트라가 훨씬 빠르다. 2. 최단 거리를 찾는 ..