https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 난이도: 실버2 소요시간:20분 inputList[i]가 양수라면 dp[i+1]은 max(dp[i]+inputList[i] , inputList[i])를 하면 된다 이전인덱스의 inputList가 음수였다면 뒤에 것이 맥스 일것이고 양수였다면 앞의 것이 맥스 일것이다. inputList[i]가 음수라면 무조건 전보다 작아진다. 이전의 dp값과 이번 잇풋값을 합쳐서 양수 이면 더하는게 이후에 이득이다. 그러니..
Problem Solving
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 난이도: 골드5 소요시간: 45분, hint 문제자체는 다익스트라 유형의 기본문제이다. 다만 제한시간이 0.5초로 매우 짧다. 처음 풀었을 때는 메모리초과가 떴다. 이 문제는 약간 수정하니 해결되었다. 정말 문제는 시간 초과이다. 이 문제를 해결하기 위해서 리스트에서 인덱스접근하는것을 변수로, 중간에 조건으로 브랜치 등을 하였지만 해결이 되지 않았다. 결국 해결한..
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 난이도: 실버1 소요시간: 35분 문제를 보자마자 다익스트라를 써야하나 라는 생각이 들었다. 그러나 오늘 풀 주제는 bfs였기에 bfs로 풀었다. 풀고나니 최단거리문제이면서 모든 거리가 1이라면 bfs를 써도된다는 것을 깨달았다. 앞으로 전형적인 최단거리 문제라도 거리가 1이라면 bfs도 고려를 해보아야겠다. 내일은 최단거리로도 한번 풀어보아야겠다...
https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 난이도: 실버2 소요시간:60+, hint 처음에는 쉬운 풀이법이 생각나지않아 생각난 방법으로 풀이를 하였는데 예외처리를 해야하는 부분이 많이 나와서 시간을 많이 잡아먹었으나 결국 풀지못하였다. 그래서 새로운 방법으로 풀었다. 한번 자리를 잡으면 뒤의 수는 나보다 크기때문에 왼쪽에만 칸을 비워두면 알아서 왼쪽수 조건이 충족된다는 것을 늦게 깨달았다,, 그 후 테스트를 몇번 돌리면서 잘못된 ..
https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 난이도: 실버1 (난이도에 비해서는 쬐끔 어려운 듯하다.) 소요시간: 60+ 처음접근법이 잘못되어 시간소비를 많이 하였다. 그리고 오류를 찾느라 시간을 오래 소비하였다. 테스트 케이스를 틀리면서 찾았다. # 18:50 실버1 from collections import deque import sys N,K= map(int,sys.stdin.readline().split()) my_bottle=deque(..
https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 난이도: 실버1 소요시간:45분 관련 알고리즘: 다익스트라(데이크스트라) DFS,BFS,다익스트라,이분검색은 조금 더 익숙해질 필요가 있는 것 같다. 예상치 못하게 오류를 만나 시간을 많이 소비했다. 손에 익어서 깊게 생각안하고도 구현할 정도로 연습을 해야겠다. 아래는 나의 코드다. 고속도로는 전부 이어져 있기 때문에 거리값을 1,2,3,...으로 초기화 했다. 그리고 i+1노드와 전부..
https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 난이도: 브론즈1 소요시간:15분 아래는 나의 코드이다. import sys N= int(sys.stdin.readline()) inputList=[] for i in range(N): inputList.append(str(sys.stdin.readline().rstrip())) result="" for i in range(len(inputList[0])): count=1 for j in r..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 난이도: 실버2 소요시간: 30분 관련 알고리즘: 그래프, dfs, bfs 나는 bfs를 이용하여 풀었다.이전에 풀었던 bfs 문제와 비슷하여 30분이내에 풀었다. 15분만에 풀었지만 인덱스를 실수한 부분이 있어 시간이 더욱 걸렸다. 그래프 문제의 경우 입력을 받을 때 인접 리스트로 받으면 편하다. graph[a] =b, graph[b..
