코딩,안되면 될때까지

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net -BFS알고리즘사용!! 그래프에서 집이 있는곳의 방문여부를 저장할 visited 배열을 선언한다.(초기값은 전부 미방문,즉 False로 선언) 집이 있는곳에서 출발해 인접한 네 방향의 위치를 확인한다. 이때 그래프의 값이 1인곳이면서(즉 집이 있는곳)동시에 아직 방문하지 않은경우 해당위치를 queue에 삽입한다. 그리고 단지의 크기를 저장할 total(초기값=1)변수에 1을 더해준다. (※ 해당위치..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net -BFS알고리즘 사용 출발위치를 queue에 넣는다. queue에 넣은 원소를 추출한다음 해당원소의 인접노드중 이동가능한 노드를 queue에 넣는다. 이동가능한 노드를 queue에 삽입하고 이동거리를 +1해준다. 위의 2,3번째 과정을 queue가 빌때까지 계속 반복해준다. from collections import deque n,m = map(int,input().split()) dx = [-1,1,0,0] dy = [0,0,..

: 이진탐색을 쉽게 구현할수 있도록 bisect 라이브러리 제공 bisect_left(a,x) : 정렬된 리스트 a에서 x가 들어갈 가장 왼쪽 인덱스 반환 bisect_right(a,x) : 정렬된 리스트 a에서 x가 들어갈 가장 오른쪽 인덱스 반환 from bisect import bisect_left,bisect_right #값이 [left_value,right_value]인 데이터의 개수를 반환하는 함수 def count_by_range(a,left_value,right_value): right_index = bisect_right(a,right_value) left_index = bosect_left(a,left_value) return right_index - left_index #정렬된 리스트..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 힙큐( heapq)를 사용하면 쉽게 풀수 있는 문제다. 비교횟수를 최소로 하기 위해선 가장 작은 크기의 카드 묶음부터 비교해 나가야 한다.힙큐를 사용하면 우선순위 큐 기능을 구현할 수 있기 때문에 손쉽게 작은 묶음부터 비교해 나갈수 있다.(※참고 : https://hae-sooo97.tistory.com/22?category=925334) -파이썬- #입력받은 카드 묶음을 순서대로 ..

heapq : heapq.heappush() : 힙에 원소를 삽입 heapq.heappop() : 힙에서 원소를 추출 우선순위 큐를 구현하고자 할때 사용 (우선순위 큐 : 들어온 순서에 상관없이 원소에 우선순위를 부여해 그 우선순위가 높은 순서대로 원소를 추출하는 큐) -파이썬- import heapq def heapsort(iterable): h=[] result = [] #모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h,value) #최대힙 구현->-value #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(heapq.heappop(h)) #최대힙->-heapq.heappop(h..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 1.)서류전형순위와 면접전형순위를 record배열에 저장한다.-record[(서류전형순위,면접전형순위)] 2.)서류전형순위를 기준으로 오름차순 정렬한다.-recordd.sort(key=lambda x:x[0]) 3.)문제에서 다른 면접자와 비교해서 두 순위 모두 낮으면 탈락이라했고 서류전형순위는 오름차순으로 정렬했으니 면접전형순위를 비교한다. 3)-1. 즉 record[1][..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 포인트 : 주유소의 가격이 가장 낮은 도시에서 최대한 먼거리를 이동할 경우 이동비용이 최소가 된다! 주유소 가격이 저장된 배열에서 가장 낮은 가격을 직접 찾는 방법으로 접근했지만 이렇게 접근할 경우 서브태스크의 2번문항을 만족하지 못해 높은 점수를 받지 못한다. 따라서 왼쪽에서부터 반복문으로 출발하면서 기존 가격보다 낮은 가격이 나올경우 가장 낮은 가격을 갱신해나가는 식으로 접근해야..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net -포인트- 1) 30의 배수이므로 일의자리 숫자는 무조건 0이다. 따라서 입력받은 숫자에 0이 반드시 포함되어야 한다. 2) 30의 배수이기 위해선 3의 배수이기도 해야한다. 3의 배수가 되기위해선 각 자리의 수를 더했을때 3의 배수가 되어야한다. -파이썬- s = list(input()) s.sort(reverse=True) sum = 0 for i in s: sum+=int(i) if sum%3..