전체 글 45

[백준] LCS 9251번 (c++)

출처 : 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..

Algorithm 2021.09.15

[백준] 알파벳 1987번 (c++)

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

Algorithm 2021.09.09

[백준] 스타트 링크 5014번 (c++)

출처 : 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..

Algorithm 2021.09.07

[백준] 신입 사원 1946번

출처 : 1946번: 신입 사원 (acmicpc.net) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 방법 서류심사와 면접시험이 둘 다 어떤 사람보다 낮으면 채용되지 않는다고 문제에 설명되어 있다. 서류심사 등수 기준으로 정렬을 한 뒤 서류심사 1등은 무조건 채용된다. 서류심사 1등의 면접 등수를 temp라는 변수에 저장한뒤 for문을 돌며 temp보다 좋은 등수를 받은 사람이 있으면 이 사람의 면접 등수를 temp에 저장해주고 ans를 +1해준다 이 과정을 for문 끝까지 반복..

Algorithm 2021.08.20

[백준] 보물섬 2589번 (c++)

출처 : 2589번: 보물섬 (acmicpc.net) 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 풀이 방법 그래프 문제인데 시작점을 여러번 바꿔가면서 bfs를 수행하여야 한다. 그래서 완전 탐색(Brute Force)를 이용하여 육지에서의 거리가 가장 먼 값을 구하여 답으로 출력 해야한다. 여기서 visited에 거리를 저장하는데 시작점을 1로 두어야 다시 시작점을 방문하는 오류를 줄일수 있어 시작점의 visited 값을 1로 설정한뒤 마지막에 답을 출력할때 -1을 해준다. #include using nam..

Algorithm 2021.08.09

[백준] 토마토 7576번 (c++)

출처 : 7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 방법 익은 토마토의 인접한 토마토들이 익어가는 것으로 보아 그래프 문제이다. 인접한 단계에 따라 기간이 흘러가므로 bfs문제로 볼 수 있다. 그런데 이 문제는 bfs의 시작점 즉 처음부터 익어있는 토마토가 한 개가 아니므로 시작점을 여러개 해주어야한다. 그러기 위해 입력을 받을 때 처음으로 익어 있는 토마토의 위치를 저장해 둔다. 그리고 bfs를 돌기위해 저장해둔 토마토 위치를 모두 큐에..

Algorithm 2021.08.04

[백준] 정수 삼각형 1932번 (c++)

출처 : 1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 방법 삼각형을 위에서부터 내려오면서 자신의 인덱스가 자신이 속한 층내에서 i 번째라면 바로 위층의 i-1,i 번째 인덱스 중 큰 수를 더해주면서 가장 바닥까지 내려와 바닥중 가장 큰 수를 출력하면 된다 #include using namespace std; vector triangle; int N, ans; int main() { cin >> N; triangle.resize(N); for (int i = 0;i < N;i++) { for (int k = 0;k < i+1..

Algorithm 2021.08.02

[백준] 숨바꼭질2 12851번 (c++)

출처 : 12851번: 숨바꼭질 2 (acmicpc.net) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 방법 visited배열에 현재 위치를 방문했는지를 기록하고 하지 않았으면 bfs로 방문하면 된다 bfs를 이용하면 자동적으로 시간이 빠른 것부터 참 색 하여 답에 도착하므로 bfs를 사용하였다 x가 현재위치다. x-1 >=0 이고 x-1 지점을 방문하지 않았더라면 x-1 지점을 방문한다 여기서 현재 위치가 목표 위치보다 작더라도 x-1을 해주어야 한다 왜냐하면 ..

Algorithm 2021.07.01

[백준] 감시 피하기 18428번 (python)

출처 : 18428번: 감시 피하기 (acmicpc.net) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 방법 완전 탐색 + DFS로 풀이할 수 있다. 벽을 세우는 경우를 완전 탐색으로 푸는데 시간을 줄이기 위해 빈 공간을 미리 리스트에 저장해둔다 벽이 3개 생성되면 check 함수를 호출하여 각 선생님의 동서남북 방향을 검사한다 while 문을 통해 board안에서의 동서남북중 한쪽씩 방향을 정해서 검사한다. 만약 검사 중 벽이 나타나면 다른 방향으로 넘어가고 검사중 학생이 나타나면 retu..

Algorithm 2021.06.11

[백준] 연산자 끼워넣기 14888번 (python)

출처 : 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 방법 DFS로 완전 탐색으로 풀어야 한다. 연산자를 배열로 따로 넣어 두고 각 연산자가 남아 있으면 사용하고 연산자 배열에서 -1을 해주고 dfs를 호출하고 다시 연산자 배열에서 +1을 해주는 백트레킹 방식으로 풀이 하였다. max_num = -987654321 min_num = 987654321 def dfs(index, sum): glo..

Algorithm 2021.06.10