성공을 즐기자

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 코드는 맞는 것같은데 시간초과가 난다....😥 시간초과 코드 : def dfs(L,val) : if L == n : candi.add(abs(val)) else : dfs(L+1,val+goosle[L]) dfs(L+1,val-goosle[L]) dfs(L+1,val) if __name__=="__main__" : n = int(input()) goosle = list(map(int,input()...

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이전에 했던 다익스트라는 한 노드에서 모든 노드로의 정점을 찾는 방법이었다. 이와 비슷한 플로이드 와샬은 모든 노드에서 모든 노드로의 최단 경로를 찾는 알고리즘이다. 2차원 테이블에 dp를 이용해 최단거리 정보를 저장하며 구한다. 시간복잡도는 O(n^3)로 오래걸린다. 삼중 for문을 사용하기 때문이다. 노드나 간선의 개수가 많으면 플로이드 와샬이 아닌 다익스트라를 고려해보시라 아무래도 dp이기 ..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 5번을 읽었는데 문제가 잘 이해가 안되서 답을 찾아봤다.😂 그냥 쉽게 말하면 n개의 센서를 k개의 구간으로 나누기 더만!! 내가 독해력이 떨어지나....ㅋㅋㅋ 정렬을 이용하여 그리디 방식으로 풀이하였다. - 만약 집중국의 개수가 센서보다 크거나 같다면 0이다. 1) 센서들을 순서대로 만든다.(오름차순 정렬) 2) 센서들..

이해하는게 참 어려웠던 문제다. 앞서 풀었던 행렬처럼 (https://what-am-i.tistory.com/408) 그리디이기 때문에 한번만 돌면서 다르면 바꾸고 이런 식일거라고 생각했다. 그런데 이 문제는 i-1, i, i+1 이 변경이되고 가장 앞과 가장 뒤는 2개씩만 변경되니까 어떻게 나눠야할지 막막했다. 찾은 방법은 바로! 내 앞에 있는 전구와 동일한 위치의 목표로 하는 전구가 다르면 나를 변경시킨다! 앞에 있는 전구를 보기 때문에 첫번째 있는 전구는 볼 전구가 없다. 그래서 첫번재 전구를 키는 경우, 안키는 경우 두가지를 확인하여 최소값을 찾으면 된다. # 0은 1으로 , 1은 0으로 def change(num) : return 1 - num def flip(state,cnt) : # 첫번째 ..

이 문제를 보고 든 생각 : 이거를 내가 어떻게 구해 🥴 그리디인가....라는 느낌이 들기는 했지만 어떻게 그리디하게 풀지 생각이 안나서 풀이를 찾아봤다. 역시 그리디였고 풀이는 내가 바꿀수 있는거만 바꾸고 이게 맞으면 다음 칸으로~ 내가 바꿀 수 있는 것만 신경쓰고 바꾼 다는게 우리 인생에서 꼭 필요한 생각같다. 내가 바꿀 수 있는 것과 없는것을 구분하는 지혜와 바꿀 수 있는 것에 집중하는 능력이 중요하다. 그냥 알고리즘 풀다가 드는 뻘생각...ㅋㅋㅋ 현재 내 위치만 보고 내 위치의 원소가 같은 위치에서의 B행렬과 일치하지 않는다면 뒤집기 때문에 그리디라고 한다. 근데 왜 이게 최소 횟수지? 순서대로 하는게 최소인가 왔다갔다하면서 최소로 바꿀수도 있는거 아닌가? 아 예를 들어 내부에 있는거 먼저 하고 ..

처음에 구현은 어떻게 했는데 세부적인 내용에서 틀렸나보다.. 결국 구글링으로 답을 찾아봤다. 내가 아직 많이 부족하구나.. 방향은 4개다. 8개가 아니고 왜냐하면 시작하는 좌표중 왼쪽, 위를 구하라고 했으므로 왼쪽, 위부터 시작하는 방향만 보기 때문이다. 1. 만약 1또는 2를 찾았다면 cnt 를 1로 해서 탐색을 시작한다. 2. while 문으로 좌표안에 있는지 같은지 여부를 파악하며 계속 진행한다. 3. 만약 5개가 되었다면 6목인지 아닌지 판변한다. 4. 만약 6목이면 continue 5. 6목이 아니라면 값과 좌표를 찍고 문제를 끝낸다. 코드 : dx = [0,1,1,-1] dy = [1,0,1,1] if __name__=="__main__" : n = 19 mp = [list(map(int,in..

문제에서 적어도 c명을 늘리는 것이므로 더 많이 늘리는 것도 생각을 해주어야 하기 때문에 dp의 크기를 c+100으로 한다. 100의 이유는 100명보다 작거나 같게만 고객의 수가 비용에 따라 증가할 수 있기 때문이다. 입력받은 (비용과 고객의 수)리스트를 돈다. (첫번째 for문) 입력받은 고객의 수에서 시작해서 dp리스트의 끝까지 돈다. (두번째 for문) 최소 고객의 수보다 작게는 증가를 못시키기 때문이다. dp[i]의 의미는 i 명을 증가시키는데 필요한 돈의 최솟값이다. 점화식 : dp[i] = min(dp[i-custo] + cost , dp[i]) 고객을 custo 만큼 늘린 대신 cost를 더한 값과 원래 값중에서 더 저렴한 값으로 갱신한다. i가 원했던 고객의 수 보다 크보다 같은 경우 값..

이걸 어떻게 풀지...고민을 많이 했다. dict? defaultdict? 하다가 점수와 시간을 같이 dict에 넣어서 정렬해서 하려면 머리가 복잡해서 이게 맞나 찾아봤는데 그냥 list 2개를 쓰면 되는거였다. picture 리스트와 score 리스트를 index로 연결하여 이미 사진틀에 있다면 해당 인덱스의 score를 1증가시킨다. 만약 없다면 - 자리가 없다면 -> picture에서 하나 빼고, score에서 하나 빼고 - 자리가 있다면 -> picture에서 하나 추가하고, score에서 하나 추가한다. 코드 : if __name__=="__main__" : n = int(input()) vote = int(input()) student = list(map(int,input().split()))..

상황을 잘 나눠서 상황에 따라 잘 계산해줘야한다. dy[j]의 의미는 j번째 문자열까지 연산했을 때 연산의 최댓값이다. 코드 : if __name__=="__main__" : a = list(input()) dy= [-int(1e9)]*(len(a)) # dy[j] : j가 마지막 숫자일 때의 최대 계산 결과 # 글자가 한글자라면 숫자로 해석 if len(a) ==1 : if a[0] == '+' : print(10) else : print(1) # 글자가 여러 글자라면 else : # 첫 글자 - 은 연산자가 아님 if a[0] == '-' : dy[0] = 1 else : dy[0] = 10 # 이왕이면 큰 숫자를 얻는게 좋음 if a[1] == '-' : dy[1] = 11 # 나머지 숫자들을 돌면..

유니온 파인드인줄 알았는데 아니었다. DFS 였다. 그저 A,B,C,D,E 가 각각 한명씩만 친구 관계로 연결되어있는 것을 확인하면 된다. 즉, DFS의 깊이가 4인지 확인하는 문제다. A - B(depth == 1) - C(depth == 2) - D(depth == 3) - E(depth == 4) if finish : return 을 통해 시간을 줄여준다. 이미 finish가 True라면 깊이가 4인 dfs를 돌았다는 것이고 추가로 확인하지않아도 되기 때문이다. 코드 : def dfs(now, depth) : global finish if finish : return # 왔음을 표시 vis[now] = 1 if depth == 4 : finish = 1 return # 친구 목록을 돌면서 for i..