PS-알고리즘2

18405번 - 경쟁적 전염 행렬이 주어졌을 때 1초뒤 1~3까지의 바이러스가 상하좌우 한 칸씩 자기 자신으로 감염을 시킵니다. N초가 지났을 때, 행렬의 X,Y좌표에 어떤 바이라스가 있는지 구하면 되는 문제입니다. 행렬크기와 바이러스의 종류, 그래프와 시간 및 최

1926번 - 그림1로 구별된 그림의 개수와 그림의 넓이를 구하는 문제입니다. BFS를 활용하면 풀어낼 수 있습니다. 먼저 가로 세로와 BFS 사용을 위한 큐 선언 및 그래프의 크기 등을 받아내겠습니다. 정답을 받을 변수 1,2를 선언하고 bfs를 돌려 변수1은 그림의

13565번 - 침투 위에서부터 잉크를 침투시키는데 아래쪽까지 닿을지 안닿을지 맞추는 문제입니다. 격자의 가로와 세로 길이, 그리고 그래프를 받아주고 que를 하나 선언해줍시다. BFS 항상 쓰는 것처럼 que선언하고 4방향 탐색을 실시해서 만약에 잉크를 떨어트

2583번 - 영역 구하기그림과 같이 도화지 위에 직사각형의 집합이 주어지면 직사각형을 제외한 영역의 개수와 넓이를 구하는 문제입니다. BFS를 사용하기 위해 que를 받아오고 그래프를 이차원 리스트 위에 표현하기 위해 a,b,c,d 변수를 받은 다음 for문을 통해

17836 - 공주님을 구해라!확실히 실버와 골드 사이에는 넘을 수 없는 차원의 벽이 있는 것 같습니다. 문제를 한번 더 꼬아놨다고 해야 하나...(0,0)에 용사가 있고 (N,M) 그러니까 끝자락에 공주가 있습니다. 용사가 공주한테 갈 수 있는 최단거리를 구해서 시

새해가 밝았습니다!다들 새해복 많이 받으시고 하시는 일 다 잘되시길 기원합니다! 24년엔 코딩실력 많이 오르게 해주세요 ㅎㅎ...10026번 - 적록색약위와같이 3색 배열 그림이 주어지면 구역(동일한 각 색깔이 뭉쳐있는 곳)이 총 몇 개인지 구하는 문제입니다. 단, 색

2589번 - 보물섬W는 바다, L은 대륙입니다. 대륙의 끝과 끝에 (둘 사이의 거리가 제밀 먼 곳에) 각각 보물이 묻혀있는데 이 둘 사이의 거리 중 제일 긴 거리를 구하면 됩니다. 제가 쓸 방식은 인덱스 하나하나 다 BFS를 돌리고 deep copy 메소드를 사용할꺼

1068번 - 트리트리가 주어질 때, 노드를 하나 고르고 해당 노드의 하위노드까지 싹 다 지웠을 때 리프 노드의 개수의 합을 구해내는 문제입니다. 먼저 기본적인 입력을 받습니다. lst의 각 인덱스마다 연결된 노드가 표시됩니다. 예를 들어 0번 인덱스에 1이 있다면 노

13023번 - ABCDE위와 같은 형식으로 친구관계가 이어져 있는 트리인지 확인해보면 되는 문제입니다. 이전 깊이 우선 탐색 문제를 풀듯 시간초과와 메모리 제한을 피하는게 쉽지 않았습니다. 일단 그래프, 방문여부(백트래킹), 측정 깊이 등을 받아주고 해당 인덱스.ap

다시 BFS 문제입니다!빈공간 / 울타리 / 양 / 늑대로 이루어진 그래프가 주어졌을 때 날이 밝은 후 최종적으로 살아남는 생물과 그 생물의 마릿수를 출력하면 되는 문제입니다. 울타리로 가두어진 공간을 '한 공간'이라고 규정하며, 한 공간 내 양의 수가 늑대보다 많을

16929번 - Two Dots사이클을 돌리는 문제입니다.그래프가 주어졌을 때, 위에 보시는 사진과 같이 시작점에서 다른 점과 겹치지 않게 다시 돌아와 사이클을 형성 할 수 있으면 Yes, 그게 아니라면 No를 출력하면 되는 탐색 문제입니다. 일단 문제를 보고 떠오른

22352번 - 항체 인식그래프가 두 개 주어집니다 (항체를 놓기 전, 항체를 놓은 후)저희는 이 두 개의 그래프를 보고 놓은 항체가 CPCU-1202 백신인지 아닌지를 판별하면 됩니다. CPCU-1202는 투약하면 현재 속해있는 값과 같은 데이터값을 가지고 상하좌우에

1240번 - 노드 사이의 거리 트리가 주어지고 노드 사이의 거릿값이 주어질 때 노드 두 개가 주어졌을 때 해당 노드 사이의 거리를 구하면 되는 문제입니다. 이런 씩으로 말입니다. 처음 접근한 방식 문제를 보고 2차원 배열의 DFS로 풀되 그래프의 값에 거리값을

27211번 - 도넛 행성탐색을 하는데 그래프가 주어지면 제한이 없습니다! 이게 무슨 말이냐면 저희가 보통 BFS나 DFS를 사용하게 되면 이런 씩으로 그래프를 넘어갈 시 continue를 시키지 않습니까?근데 이 그래프는 위와 같이 도넛모양의 형태여서 넘어가도 그대로

23352번 - 방탈출 널널한 시간제한 이번문제는 코드가 상당히 더티합니다. 그 이유는 이렇게 배열 크기가 50 X 50 이라는 넉넉한 사이즈로 주셨기에 시간제한을 염두할 필요 없이 배열의 복사 및 탐색을 거리낌없이 사용하여 풀이할 수 있었습니다. 물론 깔끔하고 빠

2660 - 회장뽑기트리가 하나 주어지면 노드 하나를 잡고 이 노드를 회원이라고 합시다. 이 회원과 이어진 노드는 회원의 친구이고, 회원과 이어진 노드의 이어진 노드는 회원의 친구의 친구입니다. 회원이 모두와 친구라면 (해당 노드가 모든 노드와 직접적으로 이어져있다면)

13265번 - 색칠하기트리가 하나 주어졌을 때 이 트리를 두 가지 색으로 색칠할 수 있는지 묻는 문제입니다. 다만, 이어진 노드끼리는 같은 색을 띨 수 없습니다. 일단 단순히 구현 문제라고 생각하고 노드를 모두 이진 트리로써 취급하여 생각해보기로 했습니다. 레벨 1에

그동안 BFS와 DFS 골드 문제들을 풀어보면서 알고리즘이 어떤 건지, 어떻게 활용하여 해결 할 수 있는지 감을 잡아갔습니다. 약 47일간 DFS와 BFS를 해결했으므로 하나만 계속해서 힘든 것도 있고 보다 다양한 알고리즘을 접하고자 오늘부터는 DP 알고리즘에 손대보려

9095번 - 1,2,3 더하기DP문제인데 그냥 재귀로 풀어버렸습니다 하하...입력받을 횟수를 받고변수를 받아 재귀를 돌려줍니다. 만약 start변수가 end와 같아지거나 더 커진다면 cnt를 하나 올리고 함수를 종료합니다. 1,2,3을 사용하여 해당 숫자를 어떻게 만

11726번 - 2\*N 타일링이런 문제입니다. 2xn이라는 총 공간이 주어졌을 때 1x2타일과 2x1타일을 이용해서 이 공간을 채울 수 있는 경우의 수를 구하면 되는 문제입니다. 이런 경우 두 가지 유형으로 나눌 수 있는데먼저 타일이 1x2타일로 끝나는 경우 와 타일

11053번 - 가장 긴 증가하는 부분 수열 (LIS)가장 긴 증가하는 부분 수열을 탐색하는 문제입니다. 이 문제는 이분 탐색과 DP 두 가지 방법으로 풀이할 수 있으나 저는 DP 연습중이므로 DP로 풀겠습니다. DP로 풀이하는 방법은 다음과 같습니다. 위와 같이 생긴

안될 가능성이 높으나 15기 소프트웨어 마에스트로에 지원했습니다. 뭐든 도전해보는게 중요하니까요.따라서 하던 DP 잠시 미뤄두고 소마 기출 푸는거에 집중하려 합니다. 기출에 DP도 포함되어 있으니 겸사겸사 공부하겠습니다. 1012 - 유기농 배추BFS로 1이 뭉쳐있는

9184번 - 신나는 함수 실행문제에 주어진 코드를 실행시키려고 하는데 문제에서 해당 코드를 실행시키면 시간이 너무 오래걸릴까봐 걱정이랍니다. 해당 코드를 시간초과가 나지 않게 실행시키는 코드를 작성하면 됩니다....보자마자 짐작이 갑니다. DP의 메모이제이션 기법을

10844 - 쉬운 계단 수쉽지않은 문제였습니다. 일단 위와같이 각 자릿수의 차이가 1인 수를 게단수라고 할 때, 자릿수가 주어지면 해당 자릿수에서 가능한 계단 수의 경우의 수의 합을 출력하면 되는 문제입니다. 이 문제가 어려운 이유로는 두 가지가 있습니다. 일단 첫번

1463번 - 1로 만들기 세 가지 연산을 사용해서 주어진 수를 최대한 적게 연산하여 1로 만들때, 연산의 횟수를 구하는 문제입니다. 분석

11055번 - 가장 큰 증가하는 부분수열가장 큰 증가하는 부분수열을 구하는 문제입니다. 이전에 풀었던 가장 긴 증가하는 부분수열을 응용한 문제라고 보시면 될 것 같습니다. 먼저 dp를 list와 똑같이 초기화해줍니다. 왜냐하면 현재 문제에서 제일 작게 나올 수 있는

17216번 - 가장 큰 감소 부분 수열가장 큰 감소하는 부분 수열의 합을 구하는 문제입니다. 합의 최소는 자기 자신이므로 dp값은 기존 리스트 인덱스와 똑같이 초기화해줍니다. 각 인덱스마다 순회를 돌며 자기 자신보다 큰 인덱스가 존재하면 자기 자신의 dp값과 자기자신

2156번 - 포도주 시식연속으로 3개를 고르면 안되고 마실수 있는 최대 포도주를 구하는 문제입니다.전에 풀었던 계단 문제와 비슷한 감이 없잖아 있는데 조금 더 복잡합니다. 본 문제는 세 가지 경우로 나눠서 풀 수 있습니다. 1\. i번째 잔을 아예 고르지 않거나2\.

14494번 - 다이나믹이 뭐에요?이차원 배열이 주어질 때 시작점에서 끝점까지 가는데의 최단 경로의 수를 구하는 문제입니다. 문제에서 구체적으로 명시하지는 않았는데, 최단 경로가 맞습니다. 먼저 최단 경로는 이러한 식으로 생겼습니다. 문제에서 친절히 맨 위에서 아래,오

11048번 - 이동하기미로가 주어지고 각 미로의 칸에 사탕이 놓여있다고 가정할 때, 리스트 (0,0) 에서 (N,M)까지 가는데 주울 수 있는 사탕의 최댓값을 구하는 문제입니다. 언뜻 보면 BFS류라고 생각할 수 있으나 DP로 해결 가능합니다. 어제 저는 14494번

18353번 - 병사 배치하기 가장 긴 오름차순 수열 문제에서 한번 꼰 문제입니다. 분석을 할 수 있으면 어렵지 않게 풀 수 있습니다.위 수열에서는 2,5,3,2,15 라는 체크해둔 수열을 제외하면 병사의 수가 최대가 되도록 할 수 있습니다. 그런데 체크해 둔 수열을

프로그래머스 - 바탕화면 정리하기소마 테스트가 프로그래머스에서 진행된다길래 맛 좀 보려고 놀러왔습니다. 어려울 것 없는 간단한 리스트 활용 문제입니다.wallpaper에서 deque 하나 import 하고 시작하겠습니다. popleft를 통해 개별 원소마다 접근하고위에

프로그래머스 - 가장 먼 노드DFS로 풀다가 한참 해맸습니다... 심지어 예전에 유사문제 한번 풀어봤던 것 같은데...어쨋든 이 문제의 쟁점은 BFS로 level(depth)를 구할 수 있는가 없는가 입니다.그림과 같이 노드의 간선이 2개 이상인 경우에는 DFS로 노드

소마 구현쪽에 투포인터 나왔다는 소리가 있어 어제 하루종일 투포인터 공부하느라 게시글을 못올렸습니다 ㅜㅜ...하지만 큰 수확이 있었으니...바로 골드4 투포인터 문제를 자력솔 했습니다!1806번 - 부분합수열이 주어지면 S보다 크거나 같은 부분수열의 합 중에서 가장 크