Python
-
[Python] 백준 2206 벽 부수고 이동하기알고리즘/문제풀이 2021. 7. 17. 21:12
1. 문제 링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 문제 요약 최단 경로 구하기 문제 → bfs 탐색 벽을 1개까지만 부수고 이동 가능 → 최단경로에서 이 조건으로 어려워짐. 3. 아이디어 정리 아이디어 1. 벽을 모두 부수면서 모든 경우의 수를 확인 ⇒ 시간 초과 아이디어 2. 벽을 부순 상태와 부수지 않은 상태의 visit 값을 분리하기 벽을 부순 상태와 부수지 않은 상태 분리 visit_0 = [..
-
[Python] 백준 3151 합이 0알고리즘/문제풀이 2021. 7. 17. 21:04
1. 문제 링크 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 2. 문제 요약 세 팀원 코딩 실력이 0이 되는 경우의 수 구한다. 3. 아이디어 정리 3명인데 투포인터를 진행해야 한다. -> 한 명씩 기준으로 잡고 그 안에서 투 포인터를 진행한다. 1. 합이 0이 되는 경우, left값과 right 값이 같은 경우 해당 범위를 더한다. ⇒ 0이되는 right 학생수 얻어서 더하기 left값과 right 값이 다른 경우 right에 해당되는 점수를 ..
-
[Python] 백준 15565 귀여운 라이언알고리즘/문제풀이 2021. 7. 17. 20:57
1. 문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 2. 문제 요약 k개 이상 라이언이 포함된 가장 작은 연속된 인형들의 집합 크기 구하기 ⇒ 투 포인터 3. 아이디어 정리 투 포인터를 이용해서 이동 k개의 라이언이 존재하는 구간에서 결과 저장 left + 1 k개 이하의 라이언이 존재하는 경우, right + 1 4. 문제 풀이 4-1. 내 풀이 import sys n, k = map(int, sys.stdin.readlin..
-
[Python] 스타트 링크 5014 - bfs 그래프 탐색알고리즘/문제풀이 2021. 7. 3. 19:35
1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 문제 요약 S > G로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 찾는 문제 → 탐색 문제 3. 아이디어 정리 BFS로 그래프 탐색을 진행하여 최솟값을 찾아본다. S를 큐에 넣어 탐색을 시작한다. 위로 올라가는 경우: 방문을 안 했다면 큐에 넣고, 버튼 누른 수 저장 아래로 내려가는 경우: 방문을 안 했다면 큐에 넣고, 버튼 누른 수 저장 4. 문제 풀이 4-1. 내 풀이 import sys..
-
[Python] 백준 한 줄로 서기 1138 - 구현 문제알고리즘/문제풀이 2021. 7. 3. 19:30
1. 문제 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 2. 문제 요약 자기보다 큰 사람이 왼쪽에 몇 명인지 알 수 있다. 줄을 선 순서대로 출력한다. 3. 아이디어 정리 키가 작은 학생부터 왼쪽에 나보다 키가 큰 사람 수만큼 자리를 비우고 맞는 순서에 배치한다. 예제 입력을 통해 직접 순서를 구현해보면 아래와 같다. 4. 문제 풀이 4-1. 내 풀이 """ 단순 구현 - 작은 사람부터 차례대로 채우기 """ import sys n ..
-
이진탐색(Binary Search) with Python알고리즘/문제풀이 2021. 1. 22. 21:29
이진 탐색을 알아보기 전에 가장 기본 탐색 방법인 순차 탐색을 알아보고 이진 탐색을 알아본다. 1. 순차 탐색 순차 탐색은 리스트 안에 있는 특정 데이터를 찾기 위해서 앞에서부터 차례대로 확인하는 방법이다. 앞에서부터 하나씩 확인해야 하기 때문에 시간 복잡도는 O(N)이 된다. 1-1. 구현하기 순차 탐색 소스를 구현하면 아래와 같다. 사람 이름 리스트 중 dongbin의 위치를 출력한다. def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i + 1 array = ["hanul", "jonggu", "dongbin", "taeil", "sangwook"] print(sequential_searc..
-
python 해시 테이블알고리즘/문제풀이 2020. 9. 20. 16:28
이번 시간에는 python 해시 관련하여 알아본다. python 해시 테이블 방식과 dict 자료형을 알아보고 자주 사용되는 모듈을 알아본다. 1. 파이썬 해시 테이블 파이썬에서 해시 테이블로 구현된 자료형은 딕셔너리다. 그렇다면 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까? 파이썬에는 오픈 어드레싱 방식으로 구현되어 있다. 파이썬에서 오픈 어드레싱 방식을 사용한 이유는 체이닝 시 malloc으로 메모리 할당하는 오버헤드가 높아서 오픈 어드레싱을 선택했다고 한다. 오픈 어드레싱 방식은 체이닝에 비해 성능이 좋다. 하지만 슬롯이 80% 이상 차게 되면 급격하게 성능 저하가 일어나며, 체이닝과 달리 로드 팩터 1 이상은 저장할 수 없다. 따라서 파이썬은 오픈 어드레싱 방식을 택해 성능을 높이지만 로..