아이디어 MST 를 구하는 문제이므로 대표적인 방법들 중 취향에 맞게 선택해서 풀면 된다. 나는 오늘 처음 보는 알고리즘이라 둘 중 Kruskal 알고리즘을 사용했고, UNION-FIND 를 이용해 사이클을 방지하도록 했다. 다만 UNION-FIND 과정에서 서로 다른 그룹을 그룹화 할 때 그룹화 하기 위해서는 각 그룹의 루트 노드를 연결해줘야 하는데 이 부분에 실수로 입력 노드를 연결하는 방식을 취해서 애를 먹었다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import ..

https://w-hand.tistory.com/134 Built in Functions - map, filter, zip map(function, *iterables) map 함수는 입력으로 들어오는 iterable 들의 각 요소를 인자로 삼아 function 을 적용해주는 함수이다. 보통 알고리즘 문제를 풀면 한 줄로 들어오는 입력을 정수로 치환해 사용해 w-hand.tistory.com 배운 것 다양한 내용을 배웠지만 새롭게 배울 수 있었던 건 빌트인 함수들인 map, filter, zip 이었다. 특히 map 과 filter 에서 발생하는 'lazy evaluation' 이라는 개념은 그동안 해당 함수들을 사용하면서도 몰랐던 개념인데 새로 배울 수 있어 좋았다. 그 외에는 함수, 매개변수, 인자 ..

map(function, *iterables) map 함수는 입력으로 들어오는 iterable 들의 각 요소를 인자로 삼아 function 을 적용해주는 함수이다. 보통 알고리즘 문제를 풀면 한 줄로 들어오는 입력을 정수로 치환해 사용해야 하는 경우가 많은데 이 때 map 을 사용할 수 있다. numbers = list(map(int, input().split())) 만약 여러 iterable 객체들을 입력으로 주면 아래와 같이 동작한다 map(func, iter1, iter2, iter3) -> func(iter1[0], iter2[0], iter3[0]) func(iter1[1], iter2[1], iter3[1]) ... map 함수의 특징 중 하나로 lazy evaluation 이 있는데 map ..

https://w-hand.tistory.com/130 Sequence Type Sequence Type 이란? 여러 요소를 가지며 요소 간의 순서가 있는 자료형을 의미한다. 대표적으로 str, list, tuple, range 가 있으며 이는 또 내부 요소를 변경할 수 있는지에 따라 가변 객체 : list 불변 객 w-hand.tistory.com https://w-hand.tistory.com/131 Non Sequence Type - set, dictionary Non Sequence Type 여러 개의 요소를 가지고 있는 Collection 종류 중 순서가 없는 Non Sequence Type 에는 대표적으로 set 과 dictionary 가 있다. Set set 은 '집합'을 의미하며 요소들의 ..

배운 것 Python 의 다양한 데이터 타입 중 숫자를 나타내는 Numeric Type 과 문자열을 나타내는 Text Sequence Type(=str) 에 대해 배웠다. 컴퓨터는 2진수에 기반하다보니 소수를 정확하게 표현하는 데에 어려움이 있는데 이로 인해 예상치 못한 결과가 나올 때가 있다. 이를 Floating Point Error 라고 하는데 이 문제를 해결하는 간단한 방법에 대해서도 배울 수 있었다. # 작은 수 더해서 기대하는 결과 얻기 print(round(3.15, 1)) # 3.1 print(round(3.15+1e-4, 1)) # 3.2 보통 오전에는 강의를 듣고 오후에는 담임강사님의 짧은 복기 강의와 함께 자습을 하는데 이런 유용한 팁들은 잊어버리지 않도록 연습을 많이 해야겠다.

Non Sequence Type 여러 개의 요소를 가지고 있는 Collection 종류 중 순서가 없는 Non Sequence Type 에는 대표적으로 set 과 dictionary 가 있다. Set set 은 '집합'을 의미하며 요소들의 순서와 중복이 없는 자료형이다. 일반적으로 수학에서 배우는 집합과 동일하며 합집합, 차집합, 교집합 등의 연산도 가능하다. set1 = {1, 2, 3, 4} set2 = {3, 4, 5, 6} print(set1|set2) # {1, 2, 3, 4, 5, 6} print(set1 - set2) # {1, 2} print(set1 & set2) # {3, 4} Dictionary dictionary 는 key - value 쌍으로 구성된 요소를 갖는 자료형이다. 순서가..

Sequence Type 이란? 여러 요소를 가지며 요소 간의 순서가 있는 자료형을 의미한다. 대표적으로 str, list, tuple, range 가 있으며 이는 또 내부 요소를 변경할 수 있는지에 따라 가변 객체 : list 불변 객체 : str, tuple, range 로 나뉜다. 가변 객체인 list 는 인덱스로 접근해서 값을 변경하는 것이 가능하지만 불변 객체인 str, tuple, range 는 인덱스로 접근해도 읽는 것만 가능하고 변경은 불가능하다 Sequence Type 의 특징 시퀀스 타입은 '순서가 있는' 자료형이기에 몇 가지 공통된 특징을 가진다. 1. 순서 : 값들이 순서대로 저장(정렬과는 다름) 2. 인덱싱 : 각 값에 고유한 인덱스를 가지고 있고 인덱스를 사용해 특정 위치의 값에..

아이디어 처음에는 치즈가 존재하는 칸을 찾고 이 칸을 기준으로 인접한 4칸을 탐색한 후 빈 칸이 몇 개인가를 카운팅하는 로직을 생각했으나 치즈 내부 공간은 치즈가 녹는 데 영향을 미치지 않으므로 이 방법을 사용할 수 없었다. 그래서 치즈가 없는 외부에서 dfs 또는 bfs 를 수행하고 치즈로 막힌 경우 다른 경로를 찾게함으로써 치즈 외부 빈칸을 모두 탐색하는 방식을 사용했다. 이 때 내부 공간과 구분하기 위해 탐색된 칸의 값은 음수로 설정해주었다. 이렇게 외부 공간을 표시한 후 현재 치즈가 녹으면 큐에서 제거해주고 아니면 다시 큐에 추가하는 방식을 사용했고 치즈를 담은 큐에 아무것도 남지않을 때까지 반복해 시간을 구했다. 풀이코드 import java.io.BufferedReader; import jav..