https://school.programmers.co.kr/learn/courses/30/lessons/43162# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이: 서로 연결되어있는 컴퓨터의 네트워크 개수, 즉 집합이 몇개 있는지를 물어보는 문제. Union ford 알고리즘을 이용해 풀었다. 한가지 주의할 점은 마지막에 각 컴퓨터가 연결되어있는 부모가 어떤것인지 체크하는 작업을 해 주어야지 정확한 네트워크 개수가 나온다. import Foundation func solution(_ n:Int, _ computers:[[Int]]) -> Int..
https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이: 처음에는 dfs방식으로 문제를 풀었지만 잘 안되서 피보나치와 비슷하다는 문제인 걸 알아서 dp로 문제를 해결. dp[n]은 n번째 위치에 있을때 마지막까지 갈 수 있는 방법의 수를 의미한다. var dp: [Int] = Array(repeating: 0, count: 2002) func solution(_ n:Int) -> Int { dp[0] = 0 dp[1] = 1 dp[2] = ..
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 풀이: dfs와 메모이제이션을 이용하여 푼 문제. dfs로 특정 칸에 있을때 최대로 움직일 수 있는 갯수를 구하여 메모이제이션에 저장, 해당 좌표에 다시 접근하였을때 바로 리턴을 하는 방식으로 문제를 구현. 만약 dfs로만 하게 된다면 시간 초과가 뜨니 메모이제이션은 필수로 구현해야 하는듯 하다. import Foundation let n = Int(readLine()!)! var..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 풀이: 기존 최단경로 찾기 문제와 비슷하지만, 다른 점이 있다면 물이 시간이 지남에 따라 확장된다는 점이다. 따라서 Queue에서 어느 시점을 꺼내지만, 해당 시점이 2의 시간이 지난 후일수도, 3의 시간이 지난 후 일수 있다. 이에 시간에 지남에 따라 물이 번진 지도를 3차원 배열로 만들어서 큐에서 꺼낸 시간의 지도 상태값을 가지고 올 수 있도록 구현했다. import Foundation enum Bl..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이: 저번에 푼 문제와 동일하게 BFS를 이용하여 최단 경로를 구한다. 단, 이전 문제와 마찬가지로 같은 칸에 도착하더라도 벽을 부순 경우와 부수지 않은 경우, 두가지를 따로 생각해야 하기에 3차원배열로 이를 구현했다. import Foundation let nm = readLine()!.split(separator: " ").map{ Int($0)! } var m..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 풀이: bfs로 풀면 쉽게 풀릴듯 보이나, 한가지 고려해야할 점이 있다. O X O O X O O O O O X O 단 한번만 점프가 가능하다고 가정하고, 다음과 같이 지도가 존재한다고 할때, (0,0)에 위치한 원숭이가 x축으로 점프를 한다고 가정해보자. 그러면 원중이의 위치는 (1,3)으로 위치하게 되고, (1,3)은 방문처리 하면, 목적지로 점프할 수 없으니 해당 점프는..
