정말정말 오랜만에 쓰는 블로그 글!원래는 알고리즘을 Swift로만 하다가 최근에는 파이썬도 하고 있다 문제 링크 https://www.acmicpc.net/problem/1068 문제 접근트리에서 특정 노드를 지웠을 때, 남아있는 트리의 노드 중 리프 노드의 개수를 구하는 문제이다. 트리 문제를 풀 때는 보통 그래프로 접근을 하고, 2차원 배열에 한 노드에 연결된 노드 번호를 모두 저장하는 식으로 구현을 한다. 위의 그림으로 예를 들자면 아래처럼 저장을 한다는 이야기다. [ [1,2], // 0번 노드 [0,3,4], // 1번 노드 [0], // 2번 노드 [1], // 3번 노드 [1] // 4번 노드] 하지만 리프 노드인지에 대한 판단을 어떻게 할 것인가? 라..
문제 링크 https://www.acmicpc.net/problem/18185 문제를 맞추고 나서 티어를 보고 굉장히 놀랐던 문제 ,, 문제 접근 문제를 읽었을 때, 전구와 스위치 문제랑 굉장히 비슷하다고 생각해서 비슷한 방법으로 접근하고자 했다. 현재의 위치를 i 라고 한다면, 영향을 줄 수 있는 곳의 위치는 `i`, `i+1`, `i+2` 이다. `i`가 마지막 즈음에 도달했을 때 `i+1`과 `i+2`의 위치를 끝까지 접근하기 위해, 입력 받은 라면 개수의 배열에 0을 두 개 추가해주었다. 만약 라면 개수의 입력이 `1 1 1 0 2`라면 내가 사용하게 될 배열은 `[1, 1, 1, 0, 2, 0, 0]`이 된다. 체크 1현재 위치 `i`에 영향을 줄 수 있는 위치는 자기 자신 `i` 뿐이다...
문제 링크 https://www.acmicpc.net/problem/1253 문제 접근 N 개의 수 중 어떤 수가 다른 두 수의 합이 되는 숫자의 개수를 찾아야 한다. 주의할 점은, 각 수가 가질 수 있는 숫자의 범위가 절댓값 1,000,000,000이라는 것이다. 물론 주어진 수를 하나씩 비교하며 답을 찾을 수 있을 것이다. 그치만 그 방식으로 실행한다면 시간이 엄청 오래 걸릴 것이다.그럼 시간을 줄일 수 있는 방법을 찾아야 한다. 일단 이 문제는 숫자의 순서를 유지할 필요가 없다. 그럼 정렬을 하는 방법을 생각할 수 있다. 오름차순으로 정렬했을 때, 앞에서부터 두 개의 숫자를 더해서 답을 찾고자할 수 있다. 하지만 이 경우에도 최악의 경우 시간복잡도가 O(N^3)이 될 것이다. 두 수를 얻기 위한..
힙에 대한 설명은 이전 포스팅을 참고해주세요. 힙의 구현 힙을 구현하는 자료구조는 배열으로, 배열의 첫 번째 인덱스는 사용되지 않는다. 고로 루트 노드는 인덱스 1이고 아래 노드로 내려갈수록 인덱스가 쭉쭉 추가가 된다. 힙에서 부모 노드와 자식 노드 간의 관계왼쪽 자식의 인덱스 = `(부모의 인덱스) * 2`오른쪽 자식의 인덱스 = `(부모의 인덱스) * 2 + 1`부모의 인덱스 = `(자식의 인덱스) / 2`이 점을 참고해서 구현해보자 - ! 기본 틀 `Comparable` 프로토콜을 채택하여 비교가 가능한 데이터 타입을 받도록 구조체를 생성한다. struct Heap { private var heap: [T] = [] private let comparer: (T,T) -> (Bool) ..
문제 링크 https://www.acmicpc.net/problem/22251 문제 이름처럼 정말 빌런같았던 문제,, 질문 게시판을 참고해서 풀었다. 문제 접근반전시켜야 하는 LED 수 구하기 가장 첫 번째로 위 사진처럼 7세그먼트로 표현된 숫자를 다른 숫자로 바꾸기 위해 몇 개의 LED를 반전시켜야하는지 알아야 한다. 정말 처음 접근으로는 각 숫자 별로 다른 숫자로 바꾸기 위해 반전시켜야 하는 LED 수를 하나하나 써서 찾으려고 했다. 근데 코드로도 구할 수 있을 것 같아서 방향을 틀었다. 숫자 별로 불이 들어오는 표시등의 위치를 숫자로 표현한 후 차집합을 이용해서 반전시킬 LED 수를 구하자질문 게시판에서 얻은 아주 좋은 아이디어이다. LED의 위치에 따라 숫자를 아래와 같이 부여했다. 그렇다..
문제 링크https://www.acmicpc.net/problem/16928 (미리보기가 왜 안될까 .. ㅜㅜ) 문제 접근- 보드의 사이즈는 10 x 10, 각 보드판에는 1부터 100까지의 숫자가 적혀있다.- i라는 위치에서 뱀과 사다리가 없다면, 갈 수 있는 곳은 i+1 부터 i+6 까지이다.- 뱀 또는 사다리가 있다면, 무조건 이동해야 한다. 위 정보를 가지고 그래프 탐색을 이용해야겠다고 생각했다. 문제 풀이보드의 사이즈가 고정이고, 특정 위치에서 갈 수 있는 위치를 모두 알 수 있기 때문에 탐색을 위한 배열을 이용한다. 배열 graph는 인덱스 0부터 100까지 총 101개이며, 각 요소로는 해당 인덱스(숫자)에서 이동할 수 있는 위치들을 저장한다.예를 들어, 1번에서 갈 수 있는 위치는 2번부..
