Heecheol's blog

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 점화식을 못찾아서 힘들었따.. 아직은 모르지만 dp문제는 테이블에 들어가는 값이 어떤 의미인지와 점화식만 찾으면 해결할 수 있는듯하다. 아무튼 result[k]의 값은 result[k-1] + result[k-2] + result[k-3]이다. 그러므로 초기값을 최소 세 개가 필요할 것이기때문에 1,2,3의 경우 값을 미리 넣어주었따. 이 문제에서는 여러 케이스에 대해서 결과를 출력하는 것이므로 아예 배열을 바깥에다 선언후에 각 케이스별로 매번 새로 구해주는 것이 아니라 값이 없는 경..

문제 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(아직 지나지 않은 칸)일때만..