모든 트럭이 조건을 맞추면서 다리를 지나게 한다음 시간을 출력하면 되는 문제다. 보고 이전에 풀었던 백준문제와 똑같다는 생각으로 바로 큐로 접근했다. 다리를 나타내는 큐를 생성하고 시간마다 뒤에서 넣고 앞에서 빼면서 트럭이 모두 없어질때까지 반복했다. 트럭 리스트가 비게되면 반복문을 끝내고 시간 + 큐의 길이 해줬다. from collections import deque def solution(bridge_length, weight, truck_weights): # bridge_length 최대 다리위 트럭 수, weight 하중, truck_weights 트럭별 무게 answer = 0 truck_weights = deque(truck_weights) queue = deque([0]*bridge_len..
알고리즘/python
이 문제는 음.. 전형적 탐색 문제 dfs로 접근했다. 컴퓨터(노드)의 갯수와 관계 그래프가 주어지기 때문에 하나의 노드를 시작으로 쭉 이어진 마지막 노드까지 가면서 방문처리(visit)를 해주면된다. 물론 다음 노드를 볼때는 방문처리(visit)가 되지 않은 상태의 노드를 선택해야한다. 그리고 한번의 dfs가 끝나면 네트워크의 갯수(answer)에 1을 더해주면된다. def solution(n, computers): answer = 0 visit = [False] * n def dfs(node): visit[node] = True for i in range(n): if node != i and computers[node][i] and not visit[i]: dfs(i) for i in range(n)..
이건... N개의 행, 4개의 열이 있다. 첫번째 행에서 만약 2번 열을 골랐다면, 다음행에서는 2번열을 고르지 못한다. 이런 조건에서 N행까지 도착했을때 수의 합이 최대가 되게 하는 문제이다. 처음에는 dfs로 접근을 했지만... 코드가 굉장히 복잡하고 연산 문제 때문에 DP로 접근했다. 선택한 열을 제외한 모든 요소를 더해서 가장 큰값을 골라 초기회 해주고 누적하는 식으로 진행했다. def solution(land): answer = 0 n = len(land) dp = land for i in range(1, n): for j in range(4): dp[i][j] += max(dp[i-1][:j] + dp[i-1][j+1:]) answer = max(dp[-1]) return answer
간만에 다시 푸는 하노이의 탑. 다시 풀어도 드는 생각, 왜 이게 lv2? 알고리즘을 생각하기 어렵기도 하고, 맞게 동작해도 제대로 이해된게 맞나 싶다. 무튼 문제를 풀어보자. 일단 하노이의 탑은 워낙 유명하니 간략하게 설명하면, 1번 기둥의 모든 고리를 3번 기둥으로 옮기면 된다. 단, 크기순 배열을 곁들인... 그림을 보면 이해는 쉽다. n=2(고리 2개)는 보기가 너무 적어 설명이 어려우니 n=3으로 가정하자. n=3(고리 3개)인 상황 1번 기둥의 가장 큰 고리는 3번 기둥으로 옮기려면 그전까지의 고리를 모두 2번 기둥으로 옮겨야한다. 즉, 우리는 n번째의 고리를 옮기기 위해 n-1개의 고리를 2번 기둥으로 옮겨야 한다. 이후 1번에 남은 n번 고리를 3번 기둥으로 옮긴다. 다시 2번기둥에 있는 ..
탐색인데 조건이 있으니 백트래킹. 타겟으로 주어진 좌표를 순서대로 지나치며 마지막 도착지까지 가는 가짓수를 구하면 된다. 방문한 곳은 재방문 불가니까 visit 생성. 재귀로 풀었다. 가장 기본적인 문제. 생각한다고 좀 골아팠다. import sys input = sys.stdin.readline n, m = map(int, input().split()) ground = [list(map(int, input().split())) for _ in range(n)] visit = [[False]*n for _ in range(n)] target = [] for _ in range(m): y, x = map(int, input().split()) target.append([y-1,x-1]) dy, dx = [..
성적 데이터를 토대로 각 대회마다 등수를 출력하고, 모든 대회 점수를 합산한 최종 등수를 출력하면된다. 이 문제에서 enumerate를 활용하였다. 우선 각 대회 점수를 입력 받음과 동시에 enumerate와 lambda를 사용하여 리스트안의 각 요소의 1번 인덱스 기준으로 내림차순 정렬을 했다. 그리곤 반복문을 통해 등수를 매겨 출력했다. 생각의 정리가 된다면 쉬운 문제다. import sys input = sys.stdin.readline N = int(input()) all_score = [0] * N # 각 대회별 점수 매기기 for _ in range(3): score = list(map(int, input().split())) for i in range(N): all_score[i] += sc..
상남자의 수를 구하는 문제. 이건 쉽다. lv3 아닌 느낌. 친분있는 사람들 중 가장 무거운 무게를 들면 된다. 그럼 상남자 등극. 친분있는 사람들을 인덱스에 맞춰 리스트화 시키고, 1번부터 친분있는 사람들과 비교하며 모두를 무게로 이기면 상남자 카운트 +1 단 한명이라도 더 무거운 무게를 든다면 상남자에서 탈락. 그러니 for문을 모두 돌 필요는 없는거다. 아 물론 친분이 있단건 양방향이란거다. 그러니 양방향으로 리스트화 해주자. import sys input = sys.stdin.readline n, m = map(int, input().split()) weight = [0] + list(map(int, input().split())) friend = [[] for _ in range(n+1)] fo..
이 문제는 정말 까다로웠다. 정확히는 지금 내 수준으로 시간내에 풀기에는 무리가 있었다. 그래서 제공되는 해설을 한번 보고 풀이를 진행했다. 문제는 간단하다. 마을 수 n(정점 수)이 주어지고, 갈수있는 길 m(간선 수)이 주어진다. 그리고 쭉 간선이 m개 만큼 주어지고 마지막에 시작과 끝이 주어진다. 구해야할건 시작점에서 끝점, 그리고 끝점에서 다시 시작점으로 돌아올 때 출근길에 방문하고 퇴근길에 다시 방문할 수 있는 마을의 수를 구하는 것이다. 말로는 이해가 어렵다. 그림을 보면 쉽다. 그림에서 1번 마을에서 3번 마을로 출근한다. 그리고 다시 3번 마을에서 1번 마을로 퇴근한다. 길은 많다. 여기서 dfs를 생각하긴 했다. (정점과 간선이 나오면 dfs라고 생각하는 편) 그런데 길의 갯수를 구하는게..
