분류 전체보기 (163) 썸네일형 리스트형 [Python] 백준 1987번 문제, 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 백트래킹을 사용해서 시간을 단축해야 하는 문제이다. 기존 DFS를 수행한다면, 매 경우를 탐색해야 하기 때문에 비효율적이다. 그래서 일정 조건에 부합할 경우 그 위치 p를 저장해 한 턴이 끝났을 때 처음부터 시작하는 것이 아닌 저장해둔 그 위치 p부터 시작한다. 예시를 하나 들기 위해 구조가 (1) -> (2) -> (3)처럼 되어 있고 노드가 가진 자식 노드를 dic으로 표현하.. [Python] 백준 1753번 문제, 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘을 사용해 최단 경로를 구하는 문제이다. 그런데 리스트를 사용한 다익스트라 알고리즘은 모든 정점에 대해 모든 경우를 처음부터 탐색해야 하기 때문에 비효율적이라고 한다. 그래서 우선순위 큐를 이용한다면 최소한으로 모든 경우의 최단 경로를 업데이트 할 수 있다. 이 우선순위 큐는 min_path를 업데이트 했을 때만 push가 되며, 최소힙으로 정렬된다. .. [Python] 백준 7662번 문제, 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이중 우선순위 큐를 큐 한 개만 이용해서 풀려고 했는데 안 됐다... 최소힙이 기준인 heapq 라이브러리를 이용해도 0-index가 최소값이기 때문에 반대편인 len(que)-1-index가 최대값일 것이라고 생각했다. 하지만 아니였다. 최소힙 기준으로 정렬되는 것이기 때문에 뒷부분에서 최대값들로 정렬된다는 보장이 없기 때문이다. 그렇기 때문에 최대힙과 최소힙으로 이루어진 우선순위 큐가 필요.. [Python] 백준 2156번 문제, 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제에서 원하는 답은 최대로 마실 수 있는 포도주의 양이다. 그런데 주어진 포도주 잔의 개수인 n에 대하여 DP[n]이 최대값이라는게 보장되지 않는다. 따라서 Top-down 방식을 통해 현재 포커싱 중인 index에는 다음을 비교해야 한다. (1) 기존 최대 포도주 양 (2) 자신의 최대값 (1)은 DP[n-1]이며, (2)는 MAX(비연속, 연속)에서 큰 값에 wine[index]를 더해주면 된.. [Python] 백준 12865번 문제, 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 동적 프로그래밍 이용해 중복된 연산을 줄여 시간을 단축해야하는 문제이다. N, K까지의 최적값들을 계산해 최종 N, K일 때 최고의 가치가 몇 일지를 구해야 한다. 따라서 DP의 크기는 [N+1][K+1]이다. ([넣을 수 있는 물품 수][배낭 최대 무게 한도]) 배낭 문제 알고리즘에 대한 DP 연산식은 다음과 같다. (.. [Python] 백준 2178번 문제, 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 너비 우선 탐색(BFS)를 이용하여 미로를 빠져 나가기 위한 최소 이동 횟수를 구하는 문제이다. 그래서 BFS를 위해 방문 정보를 담는 visited와 queue는 무조건 있어야 한다. blocks을 초기화 할 때 좌우상하 이동을 위해 padding을 주었고(Index Out 에러 방지) blocks에 칸이 1인지 0인지를 입력 받은 후에 BFS 메소드에 (N, M, blocks. queue, visited)를 넘겨 주어 출구인.. [JAVA] 백준 17478번 문제, 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 재귀함수가 어떻게 작동되는지만 알면 쉽게 풀 수 있는 문제이다. 나는 재귀 함수 + format 형식에 맞게 출력하기 위해 printTab()이라는 메소드를 만들어 "____"를 재귀 호출 횟수만큼 출력되게 만들었다. 재귀함수가 종료시 "재귀함수는 자기 자신을 호출하는 함수라네"를 출력해야 하며, 주의할 점은 "을 출력하기 위해서 \"(역슬래쉬)를 해줘야한다는 점이다. 또한, "라고 답변하였지".. [JAVA/PYTHON] 백준 1158번 문제, 요세푸스 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1부터 N까지의 수를 가진 리스트가 있는데 K 씩 증가하는 인덱스에 있는 사람들을 제거하여 그 순서대로 출력하면 되는 문제이다. K번째 자리 사람을 제거하면 리스트가 줄어들기 때문에 가변형 배열인 list를 사용했다. 현재 삭제할 인덱스 변수를 선언해 리스트에서 현재 인덱스에 있는 요소를 삭제해 제거된 사람이 모여 있는 변수에 저장하면 된다. 그래서 현재 삭제할 인덱스는 K번째 커지지만, 리스트 검색 범위를 넘어가면 안 되기 때문에 리스트로 나누었을 때 나머지가 현재 인덱스라는 걸 의미하.. 이전 1 ··· 12 13 14 15 16 17 18 ··· 21 다음 목록 더보기
