코테 공부/그 외 사이트 11

[Python/BFS] 부대 복귀

문제 설명 강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다. 강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sourc..

[Python/그리디] 3.직사각형 만들기

출처: 구름 알고리즘 먼데이 챌린지 8주차 문제 구름이는 N개의 직선 막대기를 가지고 있다. 구름이는 이 막대기들 중 일부를 잘 배치해서, 직사각형을 만들고자 한다. 직사각형을 만들기 위해서는 길이가 같은 막대기 두 쌍이 필요하다. 같은 쌍에 속한 막대기들을 마주 보게 배치하고, 다른 쌍에 속한 막대기들을 수직으로 배치하면 아래 그림과 같이 직사각형을 만들 수 있다. 길이가 a인 막대기와 길이가 b인 막대기 쌍을 사용해서 직사각형을 만들었을 때, 만들어진 직사각형의 넓이는 ab이다. 하나의 막대기는 하나의 직사각형을 만드는 데만 이용할 수 있고, 구름이는 가능한 많은 직사각형을 만들면서도 직사각형들의 넓이 합이 최대가 되기를 원한다. 구름이가 가지고 있는 막대기의 정보가 주어졌을 때, 구름이가 만들 수 ..

[Python/스택] 2.뒤통수가 따가워

출처: 구름 알고리즘 먼데이 챌린지 8주차 문제 구름나라의 저편에 있는 무릉도원에는 높은 산봉우리들이 있는 산맥이 있다. 모든 산봉우리에는 동쪽을 바라보며 명상을 하는 신선이 한 명씩 있다. 그러던 중 신선들은 다른 신선들이 자신의 뒤통수를 바라봐서 그런지 뒤통수가 따가워짐을 느끼다가, 문득 얼마나 많은 신선이 자신의 뒤통수를 볼 수 있는지 궁금해졌다. 산맥의 모든 봉우리들은 왼쪽에서 오른쪽으로 정확히 일렬로 놓여있다. 왼쪽에서 a번째 봉우리에 있는 신선이 b번째 봉우리에 있는 신선의 뒤통수를 보기 위해선, a

[Python] 1.구름 숫자

출처: 구름 알고리즘 먼데이 챌린지 8주차 문제 구름 나라는 기존의 숫자 대신에 알파벳 소문자를 사용하여 숫자를 표기하기로 한다. 이를 구름 숫자라고 부른다. 구름 숫자는 아래의 표를 참고하여 작성할 수 있다. 구름 숫자는 효율성을 위해서 특별한 규칙을 가지고 있다. 여러 개의 구름 숫자를 이어서 작성하다가, 중복되는 알파벳이 있으면 합친다. 구름 숫자로 작성한 문자열이 주어질 때, 이를 기존의 숫자로 바꿔서 출력하는 프로그램을 작성하고자 한다. 이때 여러가지 경우의 수가 나온다면, 그 중 길이가 최대인 수를 출력하시오. 입력 첫째 줄에서는 문자열의 길이 N(1

[Python/백트래킹] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

문제 예제 입력 출력 10 123 1 2737 1 757148 1 78466 2 32888 2 777770 5 436659 2 431159 7 112233 3 456789 10 #1 321 #2 7732 #3 857147 #4 87664 #5 88832 #6 777770 #7 966354 #8 954311 #9 332211 #10 987645 풀이 백트래킹을 사용한 DFS 문제이다. 원본 숫자를 담은 리스트 num의 index를 증가시키면서 count(현 교환 횟수)가 cnt(주어진 교환 횟수)와 같아질 때까지 경우의 수를 확인한다. 앞쪽 숫자가 뒤쪽 숫자보다 같거나 작으면 둘의 자리를 바꾸어 나가고 (#2), 이미 내림차순으로 정렬이 끝났음에도 교환 횟수가 남으면 남은 횟수가 홀수냐, 짝수이냐에 따라 ..

[Python] 1206. [S/W 문제해결 기본] 1일차 - View

문제 예제 입력 출력 100 0 0 225 214 82 73 241 233 179 219 135 62 36 13 6 71 179 77 67 139 31 90 9 37 93 203 150 69 19 137 28 174 32 80 64 54 18 0 158 73 173 20 0 102 107 48 50 161 246 145 225 31 0 153 185 157 44 126 153 233 0 201 83 103 191 0 45 0 131 87 97 105 97 209 157 22 0 29 132 74 2 232 44 203 0 51 0 244 212 212 89 53 50 244 207 144 72 143 0 0 ... (생략) #1 691 #2 9092 #3 8998 #4 9597 #5 8757 #6 100..

[Python/BFS] 3.구름이의 여행 2

출처: 구름 알고리즘 먼데이 챌린지 7주차 문제 구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했다. 설치된 다리들은 아래의 특징들을 만족한다. - 모든 다리는 단방향으로만 이동 가능하다. - 다리가 잇는 두 섬은 항상 다른 섬이다. 구름이는 현재 K번 섬에 있고, 다른 섬들을 둘러본 뒤 다시 K번 섬으로 돌아오려고 한다. 그렇지만 오래 돌아다니는 것은 피곤한 일이기 때문에, 구름이는 최소한의 섬만 거치는 경로를 택할 것이다. 구름이를 도와 최소 몇 개의 섬을 거쳐서 원래 구름이가 있던 섬으로 돌아올 수 있을지 알아보자. 단, 구름이는 K번 섬 이외에 최소 하나 이상의 ..

[Python/DFS] 2.퍼져나가는 소문 / 그래프 탐색

출처: 구름 알고리즘 먼데이 챌린지 7주차 문제 "발 없는 말이 천 리 간다"는 옛말이 있듯, 한 번 퍼져나가기 시작한 소문은 막을 수 없이 퍼져나간다. 구름이는 N명의 친구가 있고, 그 친구들 중에는 M쌍의 친구 관계가 있다. 구름이가 만약 어떤 친구에게 소문을 퍼뜨리게 된다면, 그 소문은 친구의 친구, 친구의 친구의 친구... 를 타고 퍼져나갈 것이다. 구름이가 1번 친구에게 소문을 퍼뜨렸을 때, 그 소문을 듣게 될 친구가 몇 명이나 될지를 구해보자. 예제 설명 첫 번째 예시의 친구 관계는 아래 그림과 같다. 모든 친구가 친구 관계로 연결되어 있으므로, 1번 친구에게 비밀을 전달하게 되면 모든 친구에게 비밀이 퍼져나가게 된다. 두 번째 예시의 친구 관계는 아래 그림과 같다. 1번 친구에게 비밀을 전달..

[Python] 1.UXUI 디자이너/ lambda, sorted

출처: 구름 알고리즘 먼데이 챌린지 7주차 문제 구름이는 구름 사이트의 UXUI디자이너로 일하게 되었다. 구름이의 첫 업무는 구름 사이트에서 사용자들이 자주 실행하는 이벤트를 정리하는 일이다. 이때 이벤트란 사용자가 웹사이트에서 실행하거나, 클릭한 것을 의미한다. 구름이는 이를 위해서 사용자들이 취할 수 있는 이벤트를 N개로 규정하고, 각각의 이벤트에 1번부터 N번까지 번호를 붙였다. 구름이는 이어서 M명의 사용자가 구름 사이트에서 이벤트를 실행한 내역을 추출하였다. 추출한 정보를 바탕으로 구름이는 사용자들이 가장 자주 실행하는 이벤트들을 알아내고자 한다. 한 사람이 같은 이벤트를 여러 번 실행한 경우에도 중복으로 세어준다. 구름이를 도와 M 명의 사용자들이 가장 자주 실행했던 이벤트들을 찾아 출력하시오..

[Python/BFS] 이코테 미로탈출 (중요. 기본기)

문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M(4