[Programmers] - 방문 길이 (Summer/Winter Coding(~2018)) with Python

📎 간략한 문제 정리 좌표평면상의 점 이동을 추적하여 이동 거리를 계산하는 문제입니다. 단 이동 루트가 중첩되는 경우 한 개의 이동거리만 계산합니다. 📈 문제 분석 조심해야할 부분은 좌표평면의 사이즈가 정해져 있는 점입니다. 정해진 범위를 벗어나는 이동 명령은 아예 무시합니다. 포인트는 이동한 위치를 체크하는 것인데 시작점과 끝점을 묶은 튜플로 표현할 수 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 겹치는 부분을 제거하기 위해 여러가지 방법이 있을 수 있습니다. x좌표, y좌표가 더 작은 점을 왼쪽 기준점으로 두어 검색하여 존재 여부를 확인하고 추가할 수 있지만 이렇게 sort를 하게되면 O(N)이므로 비효율적입니다. Dictionary를 사용할 수 있지만 기준을 맞추기 위해서는 결국 sort를 해야..
알고리즘 학습/프로그래머스 2021. 4. 21. 22:50
[Programmers] - 게임 맵 최단거리 (찾아라 프로그래밍 마에스터) with Python

📎 간략한 문제 정리 시작점 (0, 0)에서 도착점 (n-1, m-1)에 도착하기까지 최단거리를 구하고, 도착이 불가능할 경우 -1을 출력하는 메소드를 구현합니다. 📈 문제 분석 최단거리를 찾는 문제는 전형적인 BFS 문제로 BFS를 구현하며 도착점에 도착하면 그때까지의 depth를 출력하면 됩니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 이 문제는 최단거리이기 때문에 BFS가 더 적합해보이지만 DFS로도 한번 같이 구현해보았습니다. 💻 풀이한 코드 # BFS def solution_bfs(maps): from collections import deque n, m = len(maps), len(maps[0]) visited = [[-1 for _ in range(m)] for _ in range(n)] v..
알고리즘 학습/프로그래머스 2021. 4. 21. 19:49
[백준 알고리즘] - 트리의 부모 찾기 (11725번) with Python

📎 간략한 문제 정리 트리의 루트가 1이고 나머지 요소들의 연결 상태가 주어질 때, 나머지 요소들의 부모 노드를 출력하는 코드를 작성합니다. 📈 문제 분석 연결 상태를 관찰하며 각 요소의 부모 노드를 출력하는 문제입니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 dictionary를 통해 연결 상태를 정의하고, 각 요소별로 부모 노드를 검색하면 O(1)으로 탐색 가능합니다. 💻 풀이한 코드 from sys import stdin, setrecursionlimit from collections import defaultdict setrecursionlimit(10**9) input = stdin.readline N = int(input()) adj = defaultdict(list) parents = [0 f..
알고리즘 학습/백준 알고리즘 2021. 4. 20. 17:51
[백준 알고리즘] - 토마토 (7569번) with Python

📎 간략한 문제 정리 기존의 토마토 문제(https://jayb-log.tistory.com/126) 를 3차원으로 변경한 문제입니다. 익은 토마토 주변의 토마토는 익게 되는데, 모든 토마토가 익게 될 때까지 걸리는 시간을 측정하는 문제입니다. 📈 문제 분석 BFS/DFS 문제로 조건에 맞춰 주변을 탐색합니다. 기존 토마토 문제와 다른 점은 3차원이기 때문에 dx, dy로 2방향만 보는 것이 아니라 위 아래도 관찰하는 dz도 관찰해야 하는 차이가 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 각 시점에 따라서 주변에 상황이 변해가는 것이므로 DFS보다 BFS가 적합합니다. 💻 풀이한 코드 from sys import stdin from collections import deque input = stdi..
알고리즘 학습/백준 알고리즘 2021. 4. 20. 00:15
[백준 알고리즘] - K번째 수 (1300번) with Python

📎 간략한 문제 정리 2차원 배열 A의 요소는 다음과 같이 정의됩니다. A[i][j] = i*j 이 리스트를 1차원으로 만든 후 k번째 요소를 찾는 문제입니다. 📈 문제 분석 배열을 일반적으로 정렬하기 위해서는 O(NlogN)의 속도가 발생합니다. 문제에 주어진 N의 범위가 100000이므로 NlogN은 약 1600000 정도로 속도 이슈가 발생하지 않을 것 같습니다. -> 메모리 이슈가 발생합니다. 속도에는 문제가 없을지 모르지만 메모리에 문제가 발생합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 병합정렬은 O(NlogN)으로 tim sort 역시 O(NlogN)이라서 우선 tim sort를 활용해보겠습니다. 위의 방법은 메모리 이슈가 발생하므로 메모리와 속도가 tim sort보다 동시에 여유가 있는 H..
알고리즘 학습/백준 알고리즘 2021. 4. 19. 22:03
[iOS] - Stanford CS193p iOS 강의 6강 정리 by Paul Hegarty

📱 Multi-Touch(멀티 터치) 직접 우리가 화면에 터치된 입력을 모두 추적할 수 있긴 하지만 그럴 필요가 없습니다. 대신 iOS가 모든 움직임을 관찰해서 스와이프, 확대/축소, 이동, 탭 등으로 변환한 정보를 사용합니다. iOS가 나타내는 모든 제스처는 UIGestureRecognizer 클래스입니다. 이 클래스는 모든 손가락의 움직임을 제스처로 나타냅니다. 추상적인 클래스이고, 모든 제스처를 인식할 수는 없습니다. 하지만 많은 서브클래스를 이용하면 다양한 제스처를 인식할 수 있습니다. 🏢 UIGestureRecognizer 제스처를 인식하면 크게 두 부분이 있습니다. 뷰에게 확대/축소나 탭을 인식하라고 말합니다(e.g. plz start recognizing pinches/tabs). 인식했을 ..
iOS 앱개발/iOS 2021. 4. 18. 20:06
[백준 알고리즘] - 행렬 제곱 (10830) with Python

📎 간략한 문제 정리 N by N 행렬 A가 주어질 때, A의 B제곱을 구하는 프로그램을 작성하는 문제입니다. 📈 문제 분석 곱셈 연산을 거듭제곱하는 문제이므로 백준 알고리즘의 곱셈(1629번) 풀이 를 참고할 필요가 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 분할 정복을 활용합니다. 💻 풀이한 코드 from sys import stdin input = stdin.readline a, b = map(int, input().split()) matrix = [list(map(lambda x: x % 1000, map(int, input().split()))) for _ in range(a)] def power(m, y): if y == 1: return m partial = power(m, y // 2..
알고리즘 학습/백준 알고리즘 2021. 4. 17. 23:01
[백준 알고리즘] - 곱셈 (1629번) with Python

📎 간략한 문제 정리 자연수 A를 B번 곱한 수를 계산합니다. 즉, A의 B제곱을 계산하는데 그 결과를 C로 나눈 나머지를 출력합니다. 📈 문제 분석 A, B, C는 2,147,483,647 이하의 자연수입니다. 2,147,483,647(8번째 메르센 소수)는 2^31 - 1로 C언어 기준 정수자료형 최대치입니다(양의 정수 기준). 🙋‍♂️ 내가 처음 생각한 해결 방법 오버플로우 문제가 없다고 해도 A^B 연산이 끝난 뒤 C로 나누는 연산을 하면 속도 이슈가 발생할 수 밖에 없습니다. 그래서 각 연산의 중간에 C로 나누는 연산을 하는 구조로 작성해보겠습니다. 단순 반복으로는 연산 속도 이슈가 발생할 수 밖에 없습니다. 문제를 세분화하는 과정이 필요합니다(분할). 💻 풀이한 코드 from sys impor..
알고리즘 학습/백준 알고리즘 2021. 4. 16. 23:46
1 ··· 11 12 13 14 15 16 17 ··· 39