본문 바로가기

Problem Solving44

[c++][java][백준 2098] 외판원 순회 백준 2098번: 외판원 순회 [Gold 1] https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 이 문제는 TSP (Traveling Salesperson Problem) 알고리즘 문제로 그래프의 모든 노드를 한 바퀴 순회하는 최적의 경로를 찾아내는 알고리즘입니다. 모든 노드를 순회하는 최적의 경로는 완전 탐색으로도 해결이 가능하지만 노드의 개수가 10개가 넘어간다면 시간 초과에 걸리게 됩니다. 이.. 2022. 3. 24.
[c++][java][프로그래머스] 배달 프로그래머스 배달 [Summer/Winter Coding(~2018)] https://programmers.co.kr/learn/courses/30/lessons/12978?language=java 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 문제 풀이 이 문제는 1번 마을을 기준으로 모든 마을의 거리를 구한 후 거리가 K 이하인 마을의 개수를 return 하면 됩니다. 1번 마을에서 다른 모든 마을의 거리를 구하기 위해 Single Source Shortest Path 알고리즘인.. 2022. 3. 23.
[c++][python][백준 15649] N과 M (1) 백준 15649번: N과 M (1) [Silver 3] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 이 문제는 DFS - 백트랙킹 문제입니다. 중복된 숫자 방지를 위한 check array와 순열의 숫자를 담은 array를 선언하여 순열 array에 M개의 숫자가 담기게 되면 해당 array를 출력하고 return 합니다. 코드 (c++) #include using namespace std; int n, m; int arr[10.. 2022. 3. 22.
[c++][백준 2042] 구간 합 구하기 백준 2042번: 구간 합 구하기 [Gold 1] https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 풀이 이 문제는 구간 합을 구하는 문제로 단순하게 n ~ m을 반복문을 통해 더하게 되면 시간 초과에 걸리게 됩니다. 구간 합을 위해 세그먼트 트리나 펜윅 트리를 구현해야 하는데, 저는 펜윅 트리를 구현하여 문제를 풀었습니다. 아래의 링크에 세그먼트 트리와 펜윅 트리의 개념에 대해 잘.. 2022. 3. 22.
[c++][프로그래머스] 표 편집 프로그래머스 표 편집 [2021 카카오 채용연계형 인턴십] https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 문제 풀이 이 문제는 이중 연결 리스트(Doubly linked list)를 사용하여 풀었습니다. U, D 커맨드는 X만큼 prev or next로 이동합니다. C 커맨드는 현재 노드를 스택에 담고 cur->prev와 cur->next를 서로 연결시켜줍니.. 2022. 3. 7.
[c++][프로그래머스] 거리두기 확인하기 프로그래머스 거리두기 확인하기 [2021 카카오 채용연계형 인턴십] https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 문제 풀이 이 문제는 .. 2022. 3. 5.

티스토리툴바