개발 공부용

https://www.acmicpc.net/problem/2178 문제NxM 미로가 있다.미로에서 1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸이다.(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸 수를 구하는 프로그램을 작성해라. 입력첫째줄에 두 정수 N,M(2다음 N개의 줄에는 M개의 정수가 미로로 주어진다.각각의 수들은 붙어서 입력으로 주어진다. 출력첫째 줄에 지나야 하는 최소 칸 수를 출력한다.도착 위치로 이동할 수 있는 경우만 입력으로 주어진다. 풀이 방법최소 칸 수를 구하라고 명시되어 있으므로 BFS 문제임을 알 수 있다. (최소를 구하면 BFS, 모든 경우를 탐색해야 하면 DFS)시작 위치를 queue에 추가하고 방문 처리를 해준다.while문으로 queue가..

완전 탐색(Brute Force)은 주어진 데이터에서 가능한 모든 경우의 수를 시도하여 정답을 찾는 알고리즘이다.시간복잡도 면에서는 불리하지만 문제의 입력 크기가 작을 때 유리하다. DFS(Depth First Search)하나의 탐색을 전부 온전히 수행할 때까지 진행재귀 호출, 스택(LIFO)으로 구현모든 경우의 수를 탐색해야 한다면 DFS출발지에서 목적지에 도달할 수 있는지를 중점으로 탐색하는 완전 탐색 기법재귀 방식과 똑같고, 구현이 편하다.특히 문제에서 탐색 시 제약 조건을 붙이거나 결과가 누적되어야 하는 조건이 있다면,하나의 경우의 수를 고유하게 취급해주기 위해 사용한다. 구현 로직시작 부분을 스택에 삽입하고 함수 호출해당 위치를 방문했다고 표시하고 작업 처리이동 가능한 방향을 하나씩 확인다음..

문제N개의 일에 각각의 중요도를 산정하고 중요도가 높은 일부터 한다.하루에 하나의 일만 처리할 수 있으며 일을 처리한 후 그 일의 중요도가 M만큼 감소한다.일의 중요도가 K이하가 되면 그 일은 완료한 것으로 간주한다.전날의 만족감이 Y, 오늘 할 일의 중요도가 P라고 할 때 오늘의 만족감은 [Y/2]+P이다.  입력첫째 줄에 N, M, K가 공백으로 구분되어 주어진다.(2>=N둘째 줄부터 N개의 줄에 걸쳐 해야하는 일의 중요도 정수 Di가 주어진다.(M 출력첫째 줄에 송이가 일을 다 하기 위해 걸리는 날의 수를 출력한다.둘째 줄부터 일을 끝내는 날까지 일별로 느낀 만족감을 한 줄씩 구분해 출력한다. 문제 풀이 방법N, M, K를 각각 변수에 저장한다.for문을 N번 돌면서 해야하는 일의 중요도 정수를 i..

문제 출처: https://www.acmicpc.net/problem/1524 문제세준과 세비는 전쟁 게임을 한다.세준은 N명의 병사가 있고, 세비는 M명의 병사가 있다.전쟁은 여러번의 전투로 이루어진다. 전투에서는 살아있는 병사중 가장 약한 병사가 죽는다.제일 약한 병사가 여러명이고 그들이 같은 편에 있으면 그 중 한 명이 임의로 죽는다.제일 약한 병사가 여러명이고 그들이 양쪽 편에 모두 있으면 세비의 제일 약한 병사 중 한 명이 임의로 죽는다.전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다.  입력첫째 줄에 테스트 케이스 개수 T가 주어진다.(T각 테스트 케이스는 첫째 줄에 N과 M이 들어오고, (1둘째 줄에 세준이의 병사들의 힘이 들어오고셋째 줄에 세비의 병사들의 힘이 들어온다.힘은 정수이며..

문제 출처 : https://www.acmicpc.net/problem/18870 문제수직선 위의 n개의 좌표에 좌표 압축을 적용한다.Xi를 좌표 압축한 결과의 값은 XiXj를 만족하는 서로 다른 Xj의 좌표의 개수와 같아야 한다.X1~Xn에 좌표 압축을 적용한 결과를 출력하라.좌표 압축이란 주어진 숫자의 상대적 크기만 유지하면서 그 숫자들을 0부터 시작하는 연속된 정수로 변환하는 것을 말한다.참고 자료: https://blog.naver.com/vh00nj0v/223587794515  입력첫째 줄에 N이 주어짐.둘째 줄에 공백 한 칸으로 구분된 X1,X2~Xn이 주어짐. 출력첫째 줄에 좌표 압축을 적용한 결과를 공백 한 칸으로 구분하여 출력한다. 문제 풀이 방법N을 변수에 저장한다X1~Xn을 리스트에 ..

문제 출처:  문제파일을 확장자 별로 정리해서 몇 개씩 있는지 알려줘.확장자들을 사전 순으로 정렬해줘.  입력첫 번째 줄에 바탕화면에 있는 파일의 개수 N이 주어진다. (1둘째 줄부터 N개의 줄에 바탕화면에 있는 파일의 이름이 주어진다.파일의 이름은 알파벳 소문자와 점으로만 구성되어 있다.점은 정확히 한 번 등장하며 파일 이름의 첫 글자 또는 마지막 글자로 오지 않는다.3 출력확장자의 이름과 확장자 파일의 개수를 한 줄에 하나씩 출력한다.확장자가 여러 개 있는 경우 확장자의 이름의 사전순으로 출력한다. 문제 풀이 방법N을 저장한다.for문을 N번 돌면서 파일의 이름을 읽는다.이 때 점 이전의 글자와 이후의 글자를 각각 나누어 다른 변수에 저장한다.점 이후의 글자(확장자)를 딕셔너리의 key로 사용하고 해..

문제회전 초밥 가게에 N명의 손님이 있고 요리사는 M개의 초밥을 순서대로 만든다.손님들은 순서대로 초밥을 받는다.먼저 초밥을 밥는 손님이 초밥을 먹으면 뒤의 손님들은 해당 초밥을 먹을 수 없다.아무도 해당 초밥을 먹지 않으면 초밥은 버려진다.손님은 각자 먹고 싶은 초밥이 적힌 주문목록을 가졌으며 목록의 순서와 상관없이 목록에 적혀있는 초밥이 오면 먹는다.만약 목록에 적히지 않은 초밥을 받으면 먹지 않는다.손님은 각 종류의 초밥을 한 개만 먹을 수 있다.  입력첫 번째 줄에 손님의 수 N(1두 번째 줄부터 N개의 줄에 걸쳐 각 손님에 대한 주문 목록을 나타내는 정수 k와 초밥 종류 k개가 공백으로 구분되어 순서대로 주어짐(1N+2번째 줄에는 요리되는 초밥의 종류를 나타내는 M개의 정수가 공백으로 구분되어 ..

문제산타는 세계 곳곳의 거점에 방문하여 선물을 충전해 나간다.착한 아이들을 만날 때마다 자신이 들고 있는 가장 가치가 큰 선물을 준다.차례로 방문한 아이들과 거점지의 정보들이 주어졌을 때 아이들에게 준 선물의 가치들을 출력 입력첫 번째 줄은 아이들과 거점지를 방문한 횟수 n다음 n줄에는 a가 들어오고 그 다음 a개의 숫자가 들어온다 (e.g 3 1 2 3(3이 a))이는 거점지에 a개의 선물을 충전한 것이고 숫자들이 선물의 가치이다.a가 0이라면 거점지가 아닌 아이들을 만난 것이다.01 출력a가 0일 때마다 아이들에게 준 선물의 가치를 출력한다.줄 선물이 없으면 -1 출력 작성한 코드import sysimport heapqn = int(sys.stdin.readline().strip())present =..

문제배열 score를 보고 순위를 확인하라1위, 2위, 3위는 각각 금메달, 은메달, 동메달이 되며 나머지는 순위를 출력한다. 입력점수가 적힌 배열 score(10출력메달 혹은 순위가 적힌 배열풀이방법각 점수를 딕셔너리의 key로 선언score를 힙에 정렬한 뒤 한 개씩 pop하면서 순위 부여1~3까지 메달 부여하고 나머지는 순위로score 순서대로 딕셔너리에서 value 찾아 result 리스트에 넣음result 출력 작성한 코드import heapqclass Solution: def findRelativeRanks(self, score: List[int]) -> List[str]: score = [-i for i in score] origin_score = [] ..

문제섞은 음식의 스코빌 = 가장 안매운 음식 스코빌 + 두번째로 안매운 음식 스코빌*2 모든 음식의 스코빌 지수가 K이상이 될 때까지 반복하여 섞기  입력배열 scoville(2K(0 출력모든 음식의 스코빌 지수를 K이상으로 만들기 위해 섞어야 하는 최소 횟수모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 리턴 작성한 코드import heapqdef solution(scoville, K): heapq.heapify(scoville) count = 0 while True: if(len(scoville)>=2): smallest = heapq.heappop(scoville) if(smallest 두..