Heecheol's blog

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍 문제들을 풀어보기 시작하였다. 이 문제를 처음봤을 땐 bfs풀이만 생각했었다. 3으로 나눈 경우, 2로 나눈 경우, 1을 뺀 경우를 각각 큐에 넣어 1이 만들어졌을 때 결과를 출력하면 되는데 실제로 구현해보니 시간초과가 나왔다. 이 문제는 dp로 해결해야한다. dp가 이전의 연산 값을 이용해서 문제를 푸는 건 알겠는데, 어떤 문제를 dp로 해결해야할지는 잘 모르겠다. 일단 점화식을 구하면, 임의의 수 k부터 1까지 만드는 최소 횟수를 구하기 위해선 k - 1, k / 2, k / ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 BFS를 이용해 빈 공간과 블럭을 구하고 조건을 만족하도록 구현해주면 되는 문제였다. 우선, game_board와 table에서 각각 bfs를 이용해 빈 공간과 블럭을 구해주었다. 이때, 기준을 맞춰놓기 위해서 블록의 경우는 정렬을 한 뒤에 blocks변수에 넣어주었다.(빈 공간을 기준으로 맞춰도됨) blocks의 각 원소는 하나의 블럭을 이루는 좌표로 이루어져있는데, 편하게 하기 위해..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=swift 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 BFS를 이용해 간단하게 해결할 수 있었다. 컴퓨터를 하나씩 확인해가며 연결된 컴퓨터가 있다면 방문표시를 해준 뒤에 큐에 넣어준다. 하나의 컴퓨터가 확인이 끝나면 큐에 들어있는 다른 컴퓨터를 이어서 확인해주면 된다. import Foundation func solution(_ n:Int, _ computers:[[Int]]) -> Int { var result..

문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 인덱스 실수를 알아채지 못해서 몇시간이나 걸림... 이 문제는 벽 부수고 이동하기 문제와 비슷하게 해결했다. 중요한 포인트는 3차원 배열이었다. x,y 값뿐만아니라 점프한 횟수도 갖고 있어야한다. 이 포인트만 이용한다면 어렵지 않게 해결할 수 있다. 상하좌우로 가는 경우와 점프하는 경우 모두 큐에 담아주면 된다. 이때, 주의해야 할 점은 -1(아직 지나지 않은 칸)일때만..

문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 간단히 말하면, 각 섬에서 바다와 만나는 칸에서 다른 섬들과의 최단거리를 찾아서 해결했다. 우선, 다른 영역을 구하는 문제들과 동일하게 모든 점을 확인하기 위해 중첩된 반복문을 이용하였다. 1인 점을 만났을때, 방문한 기록이 없다면 bfs를 이용해 섬을 찾아준다. 섬을 찾고나면 map이라는 변수는 섬 부분만 0이고 나머지는 -1로 초기화가 되어있을 것이다. 이때, 바다와 인접한 칸(0과 인접..