devlog

출처 : 9251번: LCS (acmicpc.net) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 방법 비슷한 문제를 풀어봐서 쉽게 접근 할 수 있었다. 2차원 배열을 만든 뒤 i인덱스는 문자열 0부터 i까지의 문자열1과 0부터 j까지 문자열2 까지의 LCS를 구한 것이다. 배열에서 만약 i인덱스 문자와 j문자의 인덱스가 같으면 i-1, j-1인덱스 의 값에 +1 한 것이고. 만약 다르다면 i-1, j or i, j-1 의 값중 큰 값을 넣으면 된다. #i..

출처 : 1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 방법 bfs로 풀지 dfs로 풀지 고민하다 지금 까지 지나온 알파벳을 저장하고 알파벳 방문 여부를 판단하기에 dfs가 더 적합할 거 같아서 dfs 로 풀이하였다. 알파벳은 26개의 배열을 만들어 방문했으면 배열에 1로 두고 두 번 방문하지 않게 하였다. 그리고 백트레킹을 활용하여 더 이상 갈 곳이 없으면 배열을 다시 초기화하여서 다른 방향에서 방문을 할 수 있도록 하였다. #include usin..

출처 : 5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 방법 경우가 올라가고 내려가는 2경우 밖에 없으므로 bfs를 통해 탐색했다. bfs의 큐를 통해 방문하지 않은 층이라면 내려가는 경우와 올라가는 경우 두 개의 층을 범위가 벗어 나지 않으면 큐에 추가해주었다. 그리고 visited를 활용해 몇번 움직였는지를 저장해 주었다. #include using namespace std; // boj num 5014 int F, S, G, U, D; int visited[10..