본문 바로가기

Python78

[Python]2616. 사업장에 흡연구역 설정하기 https://www.swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AV6j7zwKszsDFAXN&categoryId=AV6j7zwKszsDFAXN&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com Image에서 Filter 를 옮기면서 최대값을 찾는 문제이다. stride = 1 일때 반복횟수 iter = n-m + 1 을 구하고 Filter 기준점을 이동시키면서 최댓값을 연산, 비교한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 n, m = 5, .. 2019. 5. 11.
[Python]1865. 동철이의 일 분배 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 이 문제는 일반적인 DFS로 풀면 시간초과가 발생한다. 적절한 시점에 Back Tracking 으로 가지치기를 하면(6번줄) 수행시간을 대폭 줄일 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def norm(a): return int(a)/100 def dfs(depth, prob): global n, answe.. 2019. 5. 11.
[Python]Insertion Sorting 삽입정렬은 자기 위치를 기준으로 앞 인덱스의 값과 비교해서 크기가 작다면 앞에다가 삽입(swap)하는 것이다. 장점은 N의 크기가 작을때 효과적이라는 것 단점은 성능이 좋지 않다는 것이다. 평균 시간복잡도 O(N^2) 정리 현재 인덱스를 정렬될 리스트의 끝으로 보고 전체 순회 현재 인덱스 값을 앞 인덱스 값과 비교/스와핑 후 인덱스 업데이트 반복 업데이트 반복 조건은 idx > 0 and arr[idx-1] > arr[idx def insertion_sort(a): n = len(a) for i in range(n): for j in range(i-1, -1, -1): if a[i] < a[j]: a[i], a[j] = a[j], a[i] i = j 2019. 5. 10.
[Python]13460. 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 어느 방향으로 기울이는가에 따라 queue에 Red와 Blue의 좌표를 초기화 해주어야 한다.(중요!) 또한 현재 Red 와 B.. 2019. 5. 10.
[Python]14502. 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 문제를 풀기전에 제약조건을 먼저 확인하고 경우의수를 계산해본다. 3 ≤ N, M ≤ 8 이고 벽은 3개를 배치하므로, N*M Combina.. 2019. 5. 9.
[Python]Bubble Sorting 버블정렬은 거품이 올라오는 모양처럼 정렬한다고 해서 붙여진 이름이다. 장점은 구현하기 가장 간단하다는 특징을 가지고 있다 단점은 성능이 좋진 않다는 것. 평균 시간 복잡도 O(N^2) 정리 인접한 값과 비교 후 교환 스와핑 위한 공간 1개 필요 총 n-1번 루핑 def bubble_sort(arr): for _ in range(len(arr)-1): for j in range(len(arr)-1): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j] return arr 2019. 5. 9.
[Python]12100. 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 브루트포스문제라고 생각하며 재귀호출을 통해서 모든 경우의 수를 탐색한다. 매 move마다 check 배열을 생성해서 병합이 되어있는지 안되어있는지 검새를 해주는 것이 포인트 이다. 현재 자신의 위치와 다음 위치 모두가 병합된 적이 없어야만 병합을 시켜준다. 또한, 네가지 방향으로.. 2019. 5. 8.
[Python]보이어무어 알고리즘 본 코드는 text안에 찾는 pattern 이 있으면 1 없으면 0 을 출력해주는 코드이다 보이어무어 알고리즘을 적용했다. 보이어무어 알고리즘이란 다음과 같다 pattern의 오른쪽 끝 문자와 text의 현재 위치의 문자가 일치하는지 검사 끝이 일치하면 pattern과 text를 다 검사한다. 마지막까지 일치하지 않으면 패턴길이만큼 skip 끝이 일치하지않으면 text의 현재위치 문자가 skip배열에 있는지 확인. 있으면 인덱스만큼 skip, 없으면 패턴길이만큼 skip 텍스트 끝 도달할 때까지 반복 text = 'a pattern matching algorithm' pattern = 'rithm' s = pattern[::-1] skip = list(range((len(pattern)))) i = le.. 2019. 4. 27.
[Python]1248. 맞춰봐 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" 라 www.acmicpc.net 12345678910111213141516171819202122232425262728293031323334353637383940414243.. 2019. 4. 22.
728x90
반응형

티스토리툴바