본문 바로가기

분류 전체보기112

[백준]BOJ 5558: チーズ (Cheese) - Python/BFS 5558번: チーズ (Cheese) (acmicpc.net) 5558번: チーズ (Cheese) 入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'， www.acmicpc.net 문제 + 파파고 번역 풀이 처음에 문제를 읽었을 땐, 치즈를 먹는 순서를 어떻게 정해야 하나 싶었지만, 시작 할 때 쥐의 체력이 1 고정이므로 고민할 필요 없이 1, 2, 3, ..., N 순서대로 먹으면 된다. BFS를 이용하여 시작 지점에서 시작해서 각 치즈간의 거리를 순서대로 더하면 된다. 코드 from collections import .. 2024. 4. 12.
[백준]BOJ 15591: MooTube(Sliver) - Python/BFS 15591번: MooTube (Silver) (acmicpc.net) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제 풀이 문제가 쓸데없이 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다. 따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해.. 2024. 4. 12.
[백준]BOJ 10021: Watering the Fields - Python/Kruskal 10021번: Watering the Fields (acmicpc.net) 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 문제 + 파파고 번역 풀이 "모든 필드를 파이프 네트워크로 연결하는 데 필요한 최소 금액"에서 MS.. 2024. 4. 12.
[백준]BOJ 14226: 이모티콘 - Swift/BFS https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제 풀이 현재 상태를 나타내는 변수를 화면에 있는 이모티콘의 개수, 클립보드에 저장되어 있는 이모티콘의 개수로 나타낼 수 있다. 각각의 연산이 모두 1초가 걸리므로 BFS를 사용할 수 있다. BFS를 사용하려면 노드에 방문했는지를 판별할 방법이 필요한데, 여기에선 Array보다는 Set을 쓰는것이 효율적이다. 두 개의 정수가 노드를 구성하므로 2차원 배열을 만들면 되겠지만, 이런 방식으로 한다면 .. 2024. 4. 9.
[백준]BOJ 14658: 하늘에서 별똥별이 빗발친다 - Python, Brute force 14658번: 하늘에서 별똥별이 빗발친다 (acmicpc.net) 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제 풀이 우선 최악의 경우를 생각해보자. N, M이 각각 500,000 이고, L은 1, K가 100일 때가 최악인 경우가 된다. 이 상태에서 모든 경우의 수를 확인하려면 별의 위치를 250,000,000,000,000번 확인해야 한다. 따라서 모든 경우의 수를 판단하는건 불가능 하다. 따라서 트램펄린을 설치할 위치를 합.. 2024. 4. 7.
[백준]BOJ 10159: 저울 - Python, Floyd-Warshall 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 문제 풀이 노드간의 연결 여부를 따지는 따지는 문제이므로 처음에는 단순히 Union-Find Set을 사용하면 될 줄 알았다. 하지만 물건 A와 B의 관계가 있을 때 가능한 경우의 수는 'A가 B보다 무겁다' 혹은 'B가 A보다 무겁다' 두 가지의 경우가 있으므로 방향 그래프가 된다. 따라서 Union-Find Set을 사용하는 것 보다는 방향 그래프에서도 적용 가능한 알고리즘을 사용해야 한다... 2024. 4. 7.
[Swift] Memory Safety(메모리 안전) - 1 Memory Safety 스위프트는 기본적으로 코드에서 일어나는 안전하지 않은 행동들을 방지한다. 예를 들어, 스위프트는 변수를 사용하기 전에 초기화가 되어있는지 확인하고, 할당 해제된 메모리에는 접근하지 않으며, 배열의 인덱스 값들이 범위 안에 있는지 확인한다. 또한 스위프트는 메모리를 수정하는 코드가 해당 메모리에 독점적으로 접근하도록 요구하여 같은 위치에 있는 메모리에 대한 동시 접근이 충돌하지 않게 한다. 스위프트가 메모리를 자동적으로 수정하기 때문에, 대부분의 경우에는 메모리 접근에 대해 생각하지 않아도 된다. 하지만, 충돌이 발생할 수 있는 잠재적인 위치를 이해하여, 메모리에 접근할 때 충돌하는 코드 작성을 회피하는 것도 중요하다. 만약 충돌을 일으키는 코드라면, 컴파일 에러 혹은 런타임 에러.. 2023. 8. 26.
[Swift] Automatic Reference Counting(자동 참조 카운팅) - 3 Strong Reference Cycles for Closures 두 클래스 인스턴스의 프로퍼티들이 서로를 강한 참조하면서 강한 참조 사이클이 만들어지는지를 이전에 보았고, 약한 참조와 미소유 참조가 이러한 강한 참조 사이클을 깨뜨리는 것도 보았다. 강한 참조 사이클은 클래스의 인스턴스에 클로저를 할당하고, 해당 클로저의 본문에서 그 인스턴스를 캡처할때도 발생한다. 이러한 캡처는 self.someProperty처럼 그 클로저가 해당 인스턴스의 프로퍼티에 접근하거나, self.someMethod()처럼 해당 인스턴스의 메소드에 접근할 때 발생한다. 두 경우 모두, 이러한 접근으로 그 클로저가 self를 "캡처"할때, 강한 참조 사이클을 생성하게 된다. 이 강한 참조 사이클은 클래스와 같이 참조 타입인 클로.. 2023. 8. 21.
[Swift] Automatic Reference Counting(자동 참조 카운팅) - 2 Resolving Strong Reference Cycles Between Class Instances 스위프트는 클래스 타입 프로퍼티로 작업할 때 강한 참조 사이클을 해결하는 두 가지 방법으로 약한 참조와 미소유 참조를 제공한다. 약한 참조와 미소유 참조는 참조 사이클 내부의 한 인스턴스가 다른 인스턴스를 강하게 붙잡지 않고 참조할 수 있게 해준다. 그리고는 그 인스턴스들은 서로를 강한 참조 사이클 없이 참조할 수 있게 된다. 다른 인스턴스의 수명이 더 짧을 때 약한 참조를 사용한다. — 즉 다른 인스턴스가 먼저 할당 해제되는 경우이다. 이전의 Apartment 예시에서, 아파트의 라이프 사이클 중간에 거주자가 없는 것은 충분히 가능한 일이므로 약한 참조는 이러한 경우의 참조 사이클을 깨뜨리는데 적합하.. 2023. 8. 16.

티스토리툴바