본문 바로가기

알고리즘 문제풀이249

[softeer] GPT식 숫자비교 (C++) https://softeer.ai/practice/11001#pop_user Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문자열정수 혹은 실수로 구성된 배열이 주어질 때, 이를 오름차순으로 정리해서 출력하는 문제인데정렬 기준이 소숫점 뒤 숫자를 정수로 생각하고 비교해야한다는 것이 특이한 점이다. 소수점을 기준으로 왼쪽 수를 기준으로 우선 정렬한 뒤, 오른쪽 수를 기준으로 정렬해야함 + 소수점이 없는 경우는 값이 같더라도 있는 쪽이 더 큰 값 (ex. 3  접근방법처음에는 int로 받아서 소수점 뒤의 수를 10을 곱해서 정수로 만들어서 따로 비교하는 방법도 시도해 봤는데, 컴파일이 안되거나 실행이 안됐고string split 사용해서 string을 커스텀해서 (소수점 기준으로 sp.. 2025. 2. 4.
[프로그래머스] 방의 개수 (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.
728x90

티스토리툴바