インプリメンテーション

実施:頭の中のアルゴリズムを正確で迅速なプログラムに編成する.
実装能力の要件を有する典型的なアルゴリズム問題タイプであり,終点探索とシミュレーションがある.
完全なナビゲーション:これは、すべての状況ですべての数を計算できるソリューションを意味します.

dfs,bfsアルゴリズムを用いて問題を解決した.

シミュレーション:問題で提案された論理または操作プロセスをコードのタイプに移動します.
解決策は、

の問題で要求される複雑な実施要件をコードに直接移行することと同様である.

 
標準ライブラリitertools
リストされたすべての要素の数を考慮する必要がある場合、通常、シーケンスまたはコンビネーションライブラリを使用するときにitertoolsを使用して実装されます.
 
ソースコードが実現しにくい、複雑な文字列を処理する必要がある、または実装する必要がある大量のソースコードの問題を実装タイプに分ける.
 
 
 

[Q 07]ラッキーストレート

n = input()

front_n = n[0:len(n)//2]
back_n = n[len(n)//2:len(n)]

front_n = map(int,front_n)
back_n = map(int,back_n)

result_f = sum(front_n)
result_b = sum(back_n)

if result_f == result_b:
    print('LUCKY')
else:
    print('READY')

 

[Q 08]並べ替え文字列

リストを文字列に変換

A = ['a','b','c']
stra = ''.join(A)
print(stra)

ソース

s = input()

alpa = []
sum = 0

for i in range(len(s)):
    if '1' <= s[i] and s[i] <= '9':
        sum += int(s[i])
    else:
        alpa.append(s[i])

alpa.sort()
alpa.append(str(sum))
print(''.join(alpa))

 

[Q 09]文字列圧縮

def solution(s):
    answer = 0
    total = ''
    result = ''
    
    
    for i in range(1, len(s)//2+1):
        check_in_s = s[:i]
        cnt = 1
        result = ''
        
        # print("i : ",i,end = " ")
        for j in range(i,len(s),i):
            # print("j : ",j,end = " ")
            check_after_s = s[j:i+j]
            # print("after_s : ",check_after_s, end=" ")
            if check_in_s == check_after_s:
                cnt += 1
            else:
                if cnt > 1:
                    result += str(cnt) + check_in_s
                else:
                    result += check_in_s
                check_in_s = check_after_s
                cnt = 1
            # print("result : ",result, end=" ")
            # print()
        if cnt > 1:
            result += str(cnt) + check_in_s
        else:
            result += check_in_s
        
        # print("result : ",len(result), " ",result)
        # print()
        if total == '' or len(total) > len(result):
            total = result
   

    answer = len(total)
    
    if answer == 0:
        answer = 1
    
    return answer

 

[Q 10]ロックとキー

やるべきこと:キーを適切に回して移動し、ロックスロットに挿入します.
アクセスサイズが20 x 20の2 Dリスト内のすべての要素にアクセスするには、400の演算量が必要です.
完全ナビゲーションを使用してキーを移動または回転させ、キーをすべてロックに挿入する操作を試みることができます.

例では
の場合、
は、です.
空白に鍵をかけるとドアが開きます.
ロックについてすべての状況を確認すればいい.
完全なナビゲーションを容易にするために、ロックリストのサイズを3倍以上に変更すると、計算が容易になります.
鍵と鍵の大きさが3*3の場合、まず鍵を3倍の大きさの新しいリストとして、中央部分に移動します.

次に、左上からグリッドを1つずつ移動して、ロックされたすべての溝を順番に充填できるかどうかを確認します.
0:ホームページ、1:回転部分
ロックリストにキーリストの値を追加した後、追加の結果を確認するには、ロック部分のすべての値が1であることを確認するだけです.
すべての値が1である場合、ロックの溝部分が正しく充填されます.
ソースで使用するrotate a matrix by 90度()メソッド
:2 Dリストを90度回転させた結果を返す方法(Pythonで2 Dリストを処理する際にたまに使用)

# 2차원 리스트 90도 회전
def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0] * n for _ in range(m)] # 결과 리스트
    for i in range(n):
        for j in range(m):
            result[j][n - i - 1] = a[i][j]
    return result

# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
    lock_length = len(new_lock) // 3
    for i in range(lock_length, lock_length * 2):
        for j in range(lock_length, lock_length * 2):
        if new_lock[i][j] != 1:
            return False
    return True

def solution(key, lock):
    n = len(lock)
    m = len(key)
    # 자물쇠의 크기를 기존의 3배로 변환
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]
    # 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[i + n][j + n] = lock[i][j]
    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
        for x in range(n * 2):
            for y in range(n * 2):
                # 자물쇠에 열쇠를 끼워 넣기
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] += key[i][j]
                # 새로운 자물쇠에 열쇠가 정확히 들어맞는지 검사
                if check(new_lock) == True:
                    return True
                # 자물쇠에서 열쇠를 다시 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    return False

# 강의 영상 : https://youtu.be/RrWnBaflV2o

def match(arr, key, rot, r, c):
    n = len(key)
    for i in range(n):
        for j in range(n):
            # 회전 값이 없다면 그대로 복사한다.
            # 이외는 회전한다.
            if rot == 0:
                arr[r + i][c + j] += key[i][j]
            elif rot == 1:
                arr[r + i][c + j] += key[n - 1 - j][i]
            elif rot == 2:
                arr[r + i][c + j] += key[n - 1 - i][n - 1 - j]
            else:
                arr[r + i][c + j] += key[j][n - 1 - i]

def check(arr, offset, n):
    for i in range(n):
        for j in  range(n):
            if arr[offset+ i][offset + j] != 1:
                return False
    return True


def solution(key, lock):
    offset = len(key) - 1
    # key * key 크기의 사각형에서
    # offset은 겹치는 부분 제외 나머지 부분
    
    for r in range(offset + len(lock)):
        for c in range(offset + len(lock)):
            for rot in range(4):
                # 90도 방향으로 돌려본다. (4번을 돌리게 된다.)
                # 열쇠 같은 경우 최대 가로 20, 20, 20 세로 20, 20, 20
                # 최대한 하나는 겹쳐야 하므로 key 양쪽 끝 2개를 제외함으로
                # 60 - 2 = 58개가 필요하다.
                arr = [[0 for _ in range(58)] for _ in range(58)]
                # 자물쇠를 offset만큼 떨어진 위치에 복사한다.
                for i in range(len(lock)):
                    for j in range(len(lock)):
                        arr[offset + i][offset + j] = lock[i][j]

                # r, c, rot를 통하여 열쇠를 복사한다.
                match(arr, key, rot, r, c)
                if check(arr, offset, len(lock)):
                    return True
    return False


k = [[0,0,0],[1,0,0],[0,1,1]]
lock = [[1,1,1],[1,1,0],[1,0,1]]
solution(k, lock)

 

[Q 11]ヘビ

n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보

# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
    a, b = map(int, input().split())
    data[a][b] = 1

# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
    x, c = input().split()
    info.append((int(x), c))

# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn(direction, c):
    if c == "L":
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
    return direction

def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0 # 처음에는 동쪽을 보고 있음
    time = 0 # 시작한 뒤에 지난 '초' 시간
    index = 0 # 다음에 회전할 정보
    q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)

    while True:
        nx = x + dx[direction]
        ny = y + dy[direction]
        # 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
        if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
            # 사과가 없다면 이동 후에 꼬리 제거
            if data[nx][ny] == 0:
                data[nx][ny] = 2
                q.append((nx, ny))
                px, py = q.pop(0)
                data[px][py] = 0
            # 사과가 있다면 이동 후에 꼬리 그대로 두기
            if data[nx][ny] == 1:
                data[nx][ny] = 2
                q.append((nx, ny))
        # 벽이나 뱀의 몸통과 부딪혔다면
        else:
            time += 1
            break
        x, y = nx, ny # 다음 위치로 머리를 이동
        time += 1
        if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
            direction = turn(direction, info[index][1])
            index += 1
    return time

print(simulate())

 

[Q 12柱とビーム取り付け]

コマンド総数:M(1000個未満)
時間の複雑さ:Bigo(M^2)、時間は5秒に制限され、Bigo(M^3)を使用できます.
柱と梁を重点とする
柱に隣接すれば梁を立てることができる.
動画リスト

インストールと削除操作が要求されるたびに、構造全体を確認し、ルールを確認します.
かのう()ほうほう

現在の構造が正常かどうかを確認する

を演算するたびに、可能な()メソッドを呼び出して、現在の構造が正常であるかどうかを確認します.
正常でない場合、現在の演算は無視されます.
 

# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0: # 설치된 것이 '기둥'인 경우
            # '바닥 위' 혹은 '보의 한쪽 끝부분 위' 혹은 '다른 기둥 위'라면 정상
            if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
                continue
            return False # 아니라면 거짓(False) 반환
        elif stuff == 1: # 설치된 것이 '보'인 경우
            # '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
                continue
            return False # 아니라면 거짓(False) 반환
    return True

def solution(n, build_frame):
    answer = []
    for frame in build_frame: # 작업(frame)의 개수는 최대 1,000개
        x, y, stuff, operate = frame
        if operate == 0: # 삭제하는 경우
            answer.remove([x, y, stuff]) # 일단 삭제를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치
        if operate == 1: # 설치하는 경우
            answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거
    return sorted(answer) # 정렬된 결과를 반환

 

[Q 13から揚げ]

問題を理解する
0:スペース、1:家、2:フライドチキン屋
既存のフライドチキン店を減らし、最大でM個を維持し、一般店からM個のフライドチキン店までの距離を減らすことを目標としている.
その後、都市フライドチキン街協定の最高価格を計算すればいいです.

例の結果は次のとおりです.
 
フライドチキン店個数範囲:M<=フライドチキン店個数<=13
フライドチキン屋でM個セットを選べば(Combinations)
最大13個からM個を選択した組み合わせと同じである.
13 CMの値は100000を超えない.
家の数は最大でも100個あるので、すべての場合の数を計算しても、タイムアウトせずに問題を解決できます.
 
Pythonはコンビネーションライブラリを提供しています
それを利用してすべての状況を簡単に計算することができます.
フライドチキン店でM個を選ぶ場合は、フライドチキン距離の和(完全探索)を算出し、フライドチキン距離の最高価格を求めて出力すればよい.
 

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

candidates 결과 예시

[((0, 1), (3, 0)), ((0, 1), (4, 0)), ((0, 1), (4, 1)), ((0, 1), (4, 4)), ((3, 0), (4, 0)), ((3, 0), (4, 1)), ((3, 0), (4, 4)), ((4, 0), (4, 1)), ((4, 0), (4, 4)), ((4, 1), (4, 4))]

 
ソース

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []

for r in range(n):
    data = list(map(int, input().split()))
    for c in range(n):
        if data[c] == 1:
            house.append((r, c))  # 일반 집
        elif data[c] == 2:
            chicken.append((r, c))  # 치킨 집

# 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))

# 치킨 거리의 합을 계산하는 함수
def get_sum(candiate):
    result = 0
    # 모든 집에 대하여
    for hx, hy in house:
        # 가장 가까운 치킨집을 찾기
        temp = 1e9
        for cx, cy in candiate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy))
        # 가장 가까운 치킨집까지의 거리를 더하기
        result += temp
    # 치킨 거리의 합 반환
    return result

# 치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candiate in candidates:
    result = min(result, get_sum(candiate))

print(result)

 

[Q 14外壁をチェック]

n:外壁長
弱い部分:弱い部分の位置
dist:友人1時間あたりの移動距離を含む配列
弱いリストとdistリストの長さは小さい.
指定されたデータが少ない場合は、完全なナビゲーションを使用してすべての状況にアクセスしようとします.
質問から探す値:入力する必要がある友人数の最大値
最大友達数:8(dist長さ最大値)
すべての友人のすべてのシーケンスの数をランダムにリストします:8 P 8=8!=計算可能な40320数量
(シーケンス:Permutations)

from itertools import permutations

arr = ['A', 'B', 'C']
nPr = permutations(arr, 2)
print(list(nPr))

# 결과
# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

 
友人をリストする場合は、それぞれ数を確認し、少なくとも何人かの友人を手配する必要があると計算すると、問題を解決することができます.
 
しかし、問題では、弱点は原型で構成されていると説明している.
リストされたデータを処理する場合、問題解決を簡略化するために、長さを2倍に増やして「円形」を1文字にすることができます.
ex) n : 12, weak : [1, 3, 4, 9, 10], dist : [3m, 5m, 7m], result : 1
脆弱な場所を2回羅列し、「円形」を1文字にする.メンテナンス時間1時間(n:12)

の弱点:1、3、4、9、10、13、15、16、21、2

各友人のすべての状況をリストする数:3!=六種類

[3m, 5m, 7m]

[3m, 7m, 5m]

[5m, 3m, 7m]

[5m, 7m, 3m]

[7m, 3m, 5m]

[7m, 5m, 3m]

いずれの場合も、5つの弱点を検査しなければならない.
友達の数を羅列する中で[7 M,3 M,5 M]
移動7 mの友人が9 mポイントから5カ所を訪問すれば、移動7 mですべての弱点をチェックすることができます.

1, 3, 4, 9, 10, 13, 15, 16, 21, 22

 
ソース

from itertools import permutations

def solution(n, weak, dist):
    # 길이를 2배로 늘려서 '원형'을 일자 형태로 변형
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    answer = len(dist) + 1  # 투입할 친구 수의 최솟값을 찾아야 하므로 len(dist) + 1로 초기화
    # 0부터 length - 1까지의 위치를 각각 시작점으로 설정
    for start in range(length):
        #print()
        #print("시작지점(start) : ", start)
        # 친구를 나열하는 모든 경우의 수 각각에 대하여 확인
        for friends in list(permutations(dist, len(dist))):
            #print("friends : ", friends, end=' ')
            count = 1  # 투입할 친구의 수
            # 해당 친구가 점검할 수 있는 마지막 위치
            position = weak[start] + friends[count - 1]
            #print("친구가 점검할 수 있는 마지막 위치 : ", position, ":", weak[start], "+", friends[count - 1])
            # 시작점부터 모든 취약 지점을 확인
            #print("시작점 부터 모든 취약지점을 확인", start, start + length)
            for index in range(start, start + length):
                # 점검할 수 있는 위치를 벗어나는 경우
                if position < weak[index]:
                    #print("현재 index", index, "해당 친구가 점검할 수 있는 마지막 위치 < 취약한 지점 :", position, weak[index], end =' ')
                    count += 1  # 새로운 친구를 투입
                    #print("새로운 친구를 투입")
                    if count > len(dist):  # 더 투입이 불가능하다면 종료
                        #print("새로운 친구 명수가, 총 투입될 수 있는 인원수 보다 많아 종료")
                        break

                    position = weak[index] + friends[count - 1]
                    #print("새로운 친구가 점검할 수 있는 마지막 위치 업데이트 : ", position,":",weak[index]," + ",friends[count-1], " index, count : ", index, count)
            answer = min(answer, count)  # 최솟값 계산
            #print("결과 : ", answer)
    if answer > len(dist):
        return -1
    return answer

 
 
参考資料

https://youtu.be/_hVVk-frECw

就職のためのコードテストです.

プログラマ