본문 바로가기

알고리즘 문제풀이230

[프로그래머스] 방의 개수 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/49190?language=swift 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그래프아래 그림처럼 8가지 방향으로 이동하는 순서가 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 이렇게 배열로 주어지고이동하면서 선을 그었을 때 생기는 방의 개수를 반환하는 문제아래의 경우 방의 개수는 3개가 된다.접근방법레벨 5에 겁먹고 오랜만에 본 그래프 문제에 겁먹어서 고민 조금 하다가 아래 블로그 참고해서 스위프트로 풀이했다.방이 생겼음을 확인하는 로직은.. 2025. 2. 3.
[프로그래머스] 퍼즐 조각 채우기 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr BFS이런..복잡해보이는 그림이 나오지만 그래도 들여다보면..생각보단 괜찮은 문제임..게임보드에서는 빈공간을 BFS로 찾아서 한 블럭의 좌표(x,y) 묶음들을 저장하고테이블에서는 채워진 공간을 BFS로 찾아서 한 블럭의 좌표 묶음들을 저장해서그들 중에 서로 일치하는 게 있는지 최대 개수를 세는 문제 접근방법우선 bfs를 사용해서 연결된 한 블럭, 연결된 빈 공간을 찾습니다.한블럭 : 그 블럭에 속한 칸들의 좌표 집합그리고 한 블럭씩 회전시키면서.. 2025. 1. 16.
[프로그래머스] 아이템 줍기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr BFS서로 어딘가 겹쳐지는 사각형이 1개~4개가 주어진다. 단 꼭짓점이 같거나 변이 겹치는 경우는 없다함이때 사각형들의 겉 테두리만 길이라는 가정하에 그 길 위에 두점 (캐릭터 위치, 아이템 위치)가 주어지면캐릭터가 이 겉 테두리만 따라가서 아이템을 얻기까지의 최단거리를 구하는 문제 접근방법https://velog.io/@rtunu12/lv.3-%EC%95%84%EC%9D%B4%ED%85%9C-%EC%A4%8D%EA%B8.. 2025. 1. 14.
[프로그래머스] 도둑질 (C++) DP 동적프로그래밍이런 배치로 되어있는 마을에서 각 집이 보유하고 있는 돈이 배열로 주어짐누군가 이 집들을 털 계획을 하고 있는데, 두집을 연속으로 털지 못함 (!주의! 첫집과 끝집도 함께 털지 못함)최대로 털 수 있는 금액을 반환하는 문제 접근방법dp문제라서 작은 문제로 쪼개서 하면, dp배열에 i번째 인덱스에 저장되는 값은 i번째까지의 금액이다.dp배열의 값을 입력하는 점화식은 아래와 같음dp1[i] = max(dp1[i-1] , dp1[i-2]+money[i]) --> 바로 전 집까지의 최대값(바로 전 집이 포함되어 있을 수 있음) vs 두칸 전 집까지의 최댓값(i바로 전 집은 포함하지 않음) + 현위치의 집 금액 dp배열이 두개 필요한데, 이유는 첫집은 무조건 포함하고 끝집을 포함하지 않는 조건으.. 2024. 11. 29.
[프로그래머스] 사칙연산 (Swift) DP 동적프로그래밍["1", "-", "3", "+", "5", "-", "8"] 이런 사칙연산을 담은 문자열 배열이 주어진다.빼기의 결합법칙에 따라 계산 결과가 달라지는 것을 고려해서, 어떤식으로 결합했을 때 이 사칙연산의 결과값이 가장 큰 지그 최댓값을 반환하는 문제 접근방법https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0 [프로그래머스] LV.4 사칙연산사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집.. 2024. 11. 21.
[프로그래머스] 등굣길 (C++) 탐욕알고리즘 (Greedy)n*m 그리드에서 1,1부터 n,m까지 가는 최단 경로의 경우의 수를 1000000007 로 나눈 나머지를 반환하는 문제가는 경로에 침수된 지점이 k 개 주어진다 (좌표로 주어짐) 접근방법n*m만큼의 2차원 배열 map을 만들고, 0으로 초기화한 후, 침수된 지점은 -1로 표시한다.1,1부터 n,m까지 순회하면서 각 자리에 이 지점까지 오는 경우의 수를 저장한다.즉, r,c 지점은 한칸 왼쪽 자리까지 오는 경우 + 한칸 위쪽 자리까지 오는 경우, 이 두 경우의 수를 합한 경우다.1,1자리에 처음에 1을 넣고 차례로 순회하고나면 n,m에는 학교까지 오는 데 최단거리의 경우의 수가 담긴다.(최단거리인지 체크하지 않는 이유는, n과 m이 1보다 크거나 같고, 오른쪽과 아래쪽으로 밖에.. 2024. 11. 8.
[프로그래머스] 단속카메라 (C++) 탐욕알고리즘 (Greedy)N개의 차량의 진입지점과 진출지점이 주어지면 모든 차량을 단속할 수 있는 단속카메라의 최소 설치 개수를 반환하는 문제 접근방법진출지점을 기준으로 먼저 나가는 차가 앞에 오도록 차들을 정렬한 후에,첫번째 차 부터 이 차가 나가는 지점에 단속카메라를 설치한다고 할 때, 차례로 차를 순회하며 현재 단속카메라가 단속할 수 있는 차량인지 확인한다.= 반복문에서 가리키고 있는 차의 진입지점이 현재 단속카메라의 위치와 같거나 그 전에 위치하면,해당차는 이미 단속할 수 있으므로 넘어가고,만약, 이 차의 진입지점이 현재 단속카메라의 위치보다 이후에 위치한다면, 해당 카메라로는 단속할 수 없으므로 다시 이 차의 진출지점에 단속카메라를 설치하고, 단속카메라의 총 개수를 1 추가한다. 이렇게 반복문.. 2024. 11. 7.
[프로그래머스] 구명보트 (C++) 그리디 (Greedy)최대 두명이 탈 수 있으며, limit 만큼의 무게를 감당할 수 있는 구명보트가 있고, N명의 사람들의 무게를 담은 배열이 하나 주어진다. 이때 최소 필요한 구명보트 수 구하기 접근방법힌트를 얻어서 투포인터로 풀었다. 우선 배열을 오름차순으로 정렬하고,왼쪽 포인터 s, 오른쪽 포인터 e 를 배열 양 끝을 가리키도록 한 다음두 포인터가 교차될 때 까지 반복하는 반목문을 들어간다.이 반복문에서는1) 두 포인터가 가리키고 있는 값을 더했을 때 limit 이하이면, 둘다 보트에 탈 수 있으므로 두 포인터 모두 안쪽으로 옮긴다.2) 그러나 더한 값이 limit을 초과하면, 무게가 더 많이 나가는 사람만 탈 수 있다는 의미이므로 오른쪽 포인터 (e) 만 한칸 앞으로 옮긴다. (구명보트 limi.. 2024. 11. 6.
[프로그래머스] 모음사전 (C++) 완전탐색A, E, I, O, U 으로만 이루어진 단어 사전이 있다. 이 사전에 수록된 단어의 최대 길이는 5일때,특정 단어가 주어지면, 이 단어의 순서를 반환하는 문제 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU" 접근방법어차피 한번에 단어 한개만 주어져서 저장해두고 쓰는 것도 불필요해서, 그냥 매번 순서를 셌다..(이게맞나 암튼 완전탐색임)DFS처럼 순서대로 단어를 체크했고, 이 문제에서는 의외로(?) 관건이 언제 재귀함수를 종료할 것인가 였다.1. cnt 증가 (단어 순서)2. 찾아야할 단어의 순서인지 확인 -> 맞으면 answer = cnt 담고 함수 종료3. 단어의 길이가 5이면 함수 종료 (이래야 단어의 길이가 6인 .. 2024. 11. 5.
728x90

티스토리툴바