Learning-log/Algorithm 문풀53 백준 20183번 골목 대장 호석 - 효율성 2 (Python) .. 우당탕탕 시행착오들.. 1. 문제 조건- N개의 교차로와 M개의 골목 (교차로 : 노드 / 골목 : 간선)- 각 간선의 가중치가 그 골목의 요금- 소지한 돈보다 많은 비용이 나오면 그 경로로는 갈 수 없음- 수치심은 경로 상에서 가장 많이 낸 돈의 금액, 최소한의 수치심을 얻어야 함- 수치심을 줄일 수록 많은 돈이 필요하고 수치심이 높을 수록 적은 돈이 필요함 - 입력 - 범위1 1 1 1 1 2. 아이디어 및 시행착오시행착오 1. 다익스트라로 경로를 이동하되, 이동한 경로의 총합으로 최소비용을 계산하는 것이 아니라, max 배열을 두고 max배열을 갱신하면서 다익스트라를 돌리려고 했다. (가지고 있는 돈보다 경로를 지나온 합이 작을 때만 갱신하도록 dist배열도 관리를 하긴 한다.) 특정 노드에 왔을 때, 그 노드까지 .. 2024. 8. 18. 백준 17135번 캐슬 디펜스 (Python) 1. 문제 조건문제 조건이 정말 많고 다양해서 문제를 잘 읽어야하는 문제였다. 당장 코드부터 써가는 버릇을 고치려고, 설계부터 하고 코드를 다 짰지만 문제를 꼼꼼히 읽지 않아 엉망진창으로 설계한 코드를 짜버리고 말았다. 문제가 복잡할 수록 조건을 잘 정리해서 빠지는 부분이 없게 설계하도록 주의해야겠다. 본 문제는 배열 내에 있는 적을 맨 아래행에 궁수를 배치해 적을 잡는 게임을 코드로 설계하는 문제이다. 게임의 규칙은 아래와 같다. 1. 궁수를 성이 있는 칸인 배열의 맨 아래행(N+1번째 행)에 3명 배치한다.2. 궁수는 각 턴마다 적 하나를 죽이며, 세 명의 궁수는 동시에 공격한다. 즉, 여러 궁수가 하나의 적을 동시에 공격할 수 있다.(적은 각 칸에 최대 한명만 존재할 수 있다.)3. 궁수가 죽일.. 2024. 8. 7. (Python) 백준 2164번 카드2 파이썬에 적응하는 중인데, 아직 파이썬의 자료구조 활용에 많이 서툴다. 이 문제에서 List를 사용해 Queue를 구현해 풀었다가 시간초과를 만나버렸다. 초기 코드n = int(input())cards = [ i+1 for i in range(n)]while len(cards)>1: cards.pop(0) if len(cards) == 1: break cards.append(cards.pop(0))print(cards[0]) 정답 코드from collections import dequen = int(input())cards = deque([i+1 for i in range(n)])while len(cards)>1: cards.popleft() if len(cards) == 1.. 2024. 7. 20. 백준 12904번. A와B (Java) 1. 문제 조건 2. 아이디어 주어진 시간은 2초이다. S의 길이는 최소 1에서 최대 999, T의 길이는 최대 1000이다. S에서 T가 만들어질 수 있는 지 확인하기 위해 문자열 뒤에 A을 한 번 추가해보고, 또 문자열을 뒤집고 B를 추가하는 연산을 각각 수행해보는 완전탐색 방식은 시간초과가 난다. S의 길이가 1이고 T의 길이가 1000인 최악의 상황을 고려했을 때, 999자리만큼 문자를 늘려야한다. 위에서 설명한 방식은 한 자리씩 늘릴 때마다 2가지 경우의 수가 존재하므로 2의 999제곱이 되어 시간초과가 발생한다. 따라서 S에서 완전탐색으로 T를 만들어나가는 과정은 적용할 수 없다. 그렇다면 반대로 T에서 S를 만들어나가면 된다. S에 1번 연산을 적용하면 맨 뒤 알파벳은 A가 되고 2번 연산을.. 2024. 4. 12. 백준 1240번. 노드사이의 거리 (Java) 1. 문제 조건 2. 아이디어 주어진 예제 입력을 살펴보면 아래와 같다. 인접행렬은 메모리 차지를 많이 할 수 있다고 생각되어 인접리스트로 구현하려고 했다. 또한, 두 노드 사이의 거리를 구하기 위해서는 간선 사이에 양방향 통행이 가능해야 하므로, 부모, 자식 상관 없이(문제에서 부모 자식을 구분할 수도 없었다.) 양 쪽 노드의 자식 노드 list에 노드를 모두 추가해줘야겠다고 생각했다. 이 때, 거리도 함께 기억해야 하므로 class를 생성하여 관리하고자 했다. 문제풀이를 하는 방식은 BFS와 DFS를 떠올렸다. 단순히 하나의 노드에서 목적지 노드까지 간선을 따라 타고 가기만 하면 되는 문제였기 때문이다. 실제로 두가지 방식으로 구현하여 제출 후 정답처리 되었으며 이 문제는 메모리와 시간복잡도 두가지 .. 2024. 2. 16. 백준 2579번 계단 오르기(Java) package baek.silver3; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main_2579계단오르기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] map = new int[N]; int[][] dp = new int[N+1][3];.. 2023. 10. 1. 이전 1 2 3 4 ··· 9 다음
