골드 boj9251 LCS 링크 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째... 백준골드DPDP boj2293 동전1 링크 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는... 백준골드DPDP boj23318 행렬분할 링크 문제 n × m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a + 1) × (b + 1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다. 위 그림 1과 같은 6 × 7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다. 분할의 '점수'... 백준골드DP브루트포스DP boj20181 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다. 호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다. 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 ... DP골드백준DP [BOJ] 5582 - 공통 부분 문자열 ✔ Problem - - DP 🔰 Level solved.ac 기준 골드5 ❔ How dynamic programming 문제이다. 문자열을 비교하면서, 만약 같은 문자열이 등장하면 길이를 더해줘야 한다. 2차원 배열을 이용해서, 문자열의 인덱스와 배열 인덱스를 이용한다. 같은 문자열이 나오면 해당 dp배열의 오른쪽 아래 대각선 자리에 왼쪽 위 대각선 값에 1을 더한 값을 넣어준다. 문자열의... DP백준coding test골드골드5algorithmboj공통 부분 문자열5582코딩테스트알고리즘5582 백준 13549번 숨바꼭질 3 파이썬 현재 위치에서 *2 로 이동하는것은 비용이 0 이다. 1번에 의해서 큐에 제일 앞에 넣어줘서 *2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다. 그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다. 제일 중요한건 *2로 이동하는 가중치가 0 이기 때문에 체크를 할 경우에 큐에 가장 앞에 넣어주는게 제일 중요한 키포인트... BFS파이썬알고리즘골드BFS 5014번 스타트링크 파이썬 s - > 시작 층 g - > 목표 층 u - > 올라가는 버튼 층수 d - > 내려가는 버튼 층수 현재 층수 + u or - d 가 갈수있는 층 수 일경우에 dq에 삽입해서 현재층수가 목표층 즉 g 까지 달성할때까지 bfs를 돌림 만약 g층에 도달하지 못했을경우 use the stairs 를 출력 아닐경우에는 cnt , 사용한 버튼 횟수를 출력 다 풀었는데 print를 이상한곳에 써놨어서 ... BFS파이썬알고리즘골드BFS 백준 1360번 구슬탈출 2 파이썬 한쪽 방향으로 기울이면 끝까지 보내준다. 동시에 빠지면 실패 같은위치에 있는 경우면 이동을 덜 한것이 먼저 도착하므로 이동을 많이 한 공 위치를 뒤로 한칸 빼준다.... BFS알고리즘골드BFS 백준 1300번 k번째 수 파이썬 k번째 수는 최대 k값을 가짐 k번째의 수 보다 작은 수의 개수를 찾음 mid의 값보다 작은 수의 개수는 EX) 3 3 에서 7보다 작은 수의 개수는 11 ~ 13 = 3개 = min(n,7/1) = 3 21 ~ 23 = 3개 = min(n,7/2) = 3 31 ~ 3*2 = 2개 = min(n,7/3) = 2 즉 min(n,mid/i)를 n번 하면 mid의 값보다 작거나 같은수의 개수를 찾... 이분탐색파이썬알고리즘골드골드 백준 1715번 카드 정렬하기 파이썬 우선순위 큐 , 힙을 사용해서 문제를 풀었다. 입력받은값을 최소힙으로 다 넣어주고 heap크기가 1일때까지 pop을 2번 실행해서 그값을 더하고 cnt , 결과값에 저장해주고 그값을 다시 heap에 넣어준다. 우선순위 큐 , 힙을 사용하여 알고리즘은 처음 풀어봤는데 많이 편한것같다..... 파이썬알고리즘골드그리디골드 [백준] 9663. N-Queen(골드5) 백준(골드5) - 풀이 체스 룰을 모르는데 알고리즘으로 풀려고 하니까 너무 피곤했다.. 문제는 안어려운데 퀸의 이동이 이게 맞나? 하고 확신을 못했다. 결국 인터넷에 퀸의 이동방향을 쳐보고 나서야 문제를 풀었다;ㅡ; 해당 구역이 비어있고, 다른 퀸들에게 공격받지 않은지만 체크(isValid) 해주면 되었다.... 백준골드5골드골드 백준 14567번 선수과목 파이썬 위상정렬을 이용하여 풀이를 했다. 위상정렬이란 앞에 진입하는 간선노드가 없는경우 실행을 하는 방식이다. res에 연결된 간선노드개수를 삽입을 해주고 반복문을 통해서 진입하는 간선노드가 없는경우 큐에 삽입을 노드 번호 , 학기를 삽입을 해준다 그리고 해당 노드랑 연결되어 있는 노드들을 반복문을 사용해서 res , 간선의 개수를 1개씩 없애주고 만약에 없을경우 큐에 삽입 , 그리고 cur에 수업... 파이썬알고리즘골드위상정렬골드 백준 2206번 벽 부수고 이동하기 파이썬 간단한 bfs 문제이다. ' 벽을 뚫고 갈 수 있다.' 이게 포인트 인데 처음에는 드릴을 뚫었나 안뚫었나 이것만 생각해서 visited 에는 count값, 오는데 걸린 횟수를 넣고 0 , 1 로 뚫고왔는지 안뚫고 왔는지를 체크했다. 이렇게 하니 11%에서 막혔다. 그래서 visited를 드릴을 뚫고 갔는지 안뚫고갔는지 두가지 경우로 3차원배열로 만들었다. 그리고 도착했을때 res값에 가장 작... BFS알고리즘골드파이썬BFS BOJ14500 테트로미노 골드 테트리스 조각에 해당하는 공간만큼의 숫자를 더해서 최대값 구하기 좌표를 움직이면서 4칸 움직이면 멈추면 되겠다 ➡ dfs를 쓰고 depth == 4 이면 값을 계산하자! 컷엣지방식을 써서 가지치기하자 배열의 최대값을 구하기 maxv = max(map(max,arr)) ➡ 현재의 총합(sumv) + arr의 최대값(maxv) * (3 - depth)번 곲한값 <= 현재의 최대값(resul... 다시풀기골드bojTILTIL [백준] 1987. 알파벳(골드4) 백준(골드4) - 풀이... 백준골드4골드골드
boj9251 LCS 링크 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째... 백준골드DPDP boj2293 동전1 링크 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는... 백준골드DPDP boj23318 행렬분할 링크 문제 n × m 크기의 행렬이 있다. 이 행렬을 가로로 a번, 세로로 b번 잘라 (a + 1) × (b + 1) 개의 부분으로 분할하려고 한다. 이 때, 같은 부분을 두 번 이상 자를 수는 없다. 즉, 한 개의 원소도 포함되지 않은 부분은 존재할 수 없다. 위 그림 1과 같은 6 × 7 행렬이 있을 때, 이 행렬을 가로로 2번, 세로로 3번 자르면 그림 2와 같이 된다. 분할의 '점수'... 백준골드DP브루트포스DP boj20181 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다. 호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다. 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 ... DP골드백준DP [BOJ] 5582 - 공통 부분 문자열 ✔ Problem - - DP 🔰 Level solved.ac 기준 골드5 ❔ How dynamic programming 문제이다. 문자열을 비교하면서, 만약 같은 문자열이 등장하면 길이를 더해줘야 한다. 2차원 배열을 이용해서, 문자열의 인덱스와 배열 인덱스를 이용한다. 같은 문자열이 나오면 해당 dp배열의 오른쪽 아래 대각선 자리에 왼쪽 위 대각선 값에 1을 더한 값을 넣어준다. 문자열의... DP백준coding test골드골드5algorithmboj공통 부분 문자열5582코딩테스트알고리즘5582 백준 13549번 숨바꼭질 3 파이썬 현재 위치에서 *2 로 이동하는것은 비용이 0 이다. 1번에 의해서 큐에 제일 앞에 넣어줘서 *2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다. 그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다. 제일 중요한건 *2로 이동하는 가중치가 0 이기 때문에 체크를 할 경우에 큐에 가장 앞에 넣어주는게 제일 중요한 키포인트... BFS파이썬알고리즘골드BFS 5014번 스타트링크 파이썬 s - > 시작 층 g - > 목표 층 u - > 올라가는 버튼 층수 d - > 내려가는 버튼 층수 현재 층수 + u or - d 가 갈수있는 층 수 일경우에 dq에 삽입해서 현재층수가 목표층 즉 g 까지 달성할때까지 bfs를 돌림 만약 g층에 도달하지 못했을경우 use the stairs 를 출력 아닐경우에는 cnt , 사용한 버튼 횟수를 출력 다 풀었는데 print를 이상한곳에 써놨어서 ... BFS파이썬알고리즘골드BFS 백준 1360번 구슬탈출 2 파이썬 한쪽 방향으로 기울이면 끝까지 보내준다. 동시에 빠지면 실패 같은위치에 있는 경우면 이동을 덜 한것이 먼저 도착하므로 이동을 많이 한 공 위치를 뒤로 한칸 빼준다.... BFS알고리즘골드BFS 백준 1300번 k번째 수 파이썬 k번째 수는 최대 k값을 가짐 k번째의 수 보다 작은 수의 개수를 찾음 mid의 값보다 작은 수의 개수는 EX) 3 3 에서 7보다 작은 수의 개수는 11 ~ 13 = 3개 = min(n,7/1) = 3 21 ~ 23 = 3개 = min(n,7/2) = 3 31 ~ 3*2 = 2개 = min(n,7/3) = 2 즉 min(n,mid/i)를 n번 하면 mid의 값보다 작거나 같은수의 개수를 찾... 이분탐색파이썬알고리즘골드골드 백준 1715번 카드 정렬하기 파이썬 우선순위 큐 , 힙을 사용해서 문제를 풀었다. 입력받은값을 최소힙으로 다 넣어주고 heap크기가 1일때까지 pop을 2번 실행해서 그값을 더하고 cnt , 결과값에 저장해주고 그값을 다시 heap에 넣어준다. 우선순위 큐 , 힙을 사용하여 알고리즘은 처음 풀어봤는데 많이 편한것같다..... 파이썬알고리즘골드그리디골드 [백준] 9663. N-Queen(골드5) 백준(골드5) - 풀이 체스 룰을 모르는데 알고리즘으로 풀려고 하니까 너무 피곤했다.. 문제는 안어려운데 퀸의 이동이 이게 맞나? 하고 확신을 못했다. 결국 인터넷에 퀸의 이동방향을 쳐보고 나서야 문제를 풀었다;ㅡ; 해당 구역이 비어있고, 다른 퀸들에게 공격받지 않은지만 체크(isValid) 해주면 되었다.... 백준골드5골드골드 백준 14567번 선수과목 파이썬 위상정렬을 이용하여 풀이를 했다. 위상정렬이란 앞에 진입하는 간선노드가 없는경우 실행을 하는 방식이다. res에 연결된 간선노드개수를 삽입을 해주고 반복문을 통해서 진입하는 간선노드가 없는경우 큐에 삽입을 노드 번호 , 학기를 삽입을 해준다 그리고 해당 노드랑 연결되어 있는 노드들을 반복문을 사용해서 res , 간선의 개수를 1개씩 없애주고 만약에 없을경우 큐에 삽입 , 그리고 cur에 수업... 파이썬알고리즘골드위상정렬골드 백준 2206번 벽 부수고 이동하기 파이썬 간단한 bfs 문제이다. ' 벽을 뚫고 갈 수 있다.' 이게 포인트 인데 처음에는 드릴을 뚫었나 안뚫었나 이것만 생각해서 visited 에는 count값, 오는데 걸린 횟수를 넣고 0 , 1 로 뚫고왔는지 안뚫고 왔는지를 체크했다. 이렇게 하니 11%에서 막혔다. 그래서 visited를 드릴을 뚫고 갔는지 안뚫고갔는지 두가지 경우로 3차원배열로 만들었다. 그리고 도착했을때 res값에 가장 작... BFS알고리즘골드파이썬BFS BOJ14500 테트로미노 골드 테트리스 조각에 해당하는 공간만큼의 숫자를 더해서 최대값 구하기 좌표를 움직이면서 4칸 움직이면 멈추면 되겠다 ➡ dfs를 쓰고 depth == 4 이면 값을 계산하자! 컷엣지방식을 써서 가지치기하자 배열의 최대값을 구하기 maxv = max(map(max,arr)) ➡ 현재의 총합(sumv) + arr의 최대값(maxv) * (3 - depth)번 곲한값 <= 현재의 최대값(resul... 다시풀기골드bojTILTIL [백준] 1987. 알파벳(골드4) 백준(골드4) - 풀이... 백준골드4골드골드