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도 고려를 해보아야겠다. 내일은 최단거리로도 한번 풀어보아야겠다...
Problem Solving
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..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 난이도: 실버2 소요시간: 30분 다익스트라를 쓰면 풀리는 문제이다. 거리가 1로 고정인 점을 생각하여 다익스트라 알고리즘을 조금 수정 하면된다. import sys import heapq N,M,K,X = map(int,sys.stdin.readline().split()) INF=1e9 dist = [INF]*(N+1) g..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 난이도: 실버2 소요시간: 60분, 엣지케이스 관련 힌트 참고함 최대로 나올수 있는 값을 end로 정했다. 1~end를 이분탐색하여서 정답을 찾았다. import sys K,N = map(int,sys.stdin.readline().split()) end=0 cableList=[] for _ in range(K): temp=int(sys.stdin.readline())..
