목록problem solving/SWEA (13)
풀이 보관함
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1258. [S/W 문제해결 응용] 7일차 - 행렬찾기 🖍 풀이 전체 행렬 크기(N)는 최대 100 고맙게도 최소 행렬 개수 문제도 아니며 서브 행렬들은 붙어있지도 않다. 사각형으로 존재한다. → 물질이 들어있는 위치를 찾으면 어떤 사각형으로 잘라야 최소 용기 개수인지 고민할 필요 없다. → 그 위치에서 서브 행렬 크기만 찾아내면 됨 이중포문으로 0이 아닌 위치를 찾는다. 그 위치에서 최대 사각형 크기를 구한다. R x C 와 크기를 저장한다. 찾은 사각형을 0으로 변경한다. 출력의 조건을 맞추기 위해 연산자 오버라이딩을 ..
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [S/W 문제해결 응용] 5일차 - 단순도금비용 🖍 풀이 🚩 주의: 단순도금비용은 Pass지만, 도금 비용은 Fail이에요. 문제를 보면 가장 큰 필름부터 붙이는 것이 좋겠다는 생각이 든다. 1) 먼저 손상 개수별로 최소 비용으로 수리할 수 있는 필름 크기를 알아보자. 9~5개는 사이즈가 3인 필름을 붙이는 것이 최소 비용 4~2개는 사이즈가 2인 필름을 붙이는 것이 최소 비용 1개는 사이즈가가 1인 필름을 붙이는 것이 최소 비용 이를 토대로 손상 개수 범위를 지정했다. const int size_range[3][2] = ..
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 DFS는 시간초과고 BFS이라고 생각해서 풀면 오답이다. (경험담) 왜냐하면 생각해보면 map의 좌표 (x, y)까지 오는 경로는 다양하다. 가는 길이 0, 1로만 이루어진 것이 아니기 때문에 첫 방문이 최소 경로라고 단정지을 수 없다. 그래서 상하좌우로 이동하면서 (x, y)까지 걸린 시간을 계속해서 갱신해주어야 한다. visited[x][y]로 재방문를 판단하기는 하지만 그냥 갱신인지 신규인지만 판단하는 용도로 사용해줬다. 다익스트라의 개념을 알고 있으면 내 풀이를 이해하는데 도움됨 💾 소스 #include #..
🔗 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 set 라이브러리의 특성을 이용하면 쉽게 풀 수 있다. set은 중복을 제외하고, 오름차순으로 자동 정렬해주는 특성이 있다. 먼저 문자열을 다 쪼개어서 저장해준다. substr(i, j) i 위치에서부터 j개를 자르는 substr 함수 for(int i=0; i T; for(int tc=1; tc> N >> str; std::set set; for(int i=0; i
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 완전 탐색으로 돌려줬다. 완전 탐색 문제를 풀 때는 조건문으로 필요없는 반복을 줄이는 것이 중요하다. for문으로 교환해줄 때 i, j의 조건을 보자. j는 i보다 더 큰 수로만 증가하여 중복되는 교환횟수를 줄였다. visited[ 교환 후 숫자 ] [교환횟수] 로 중복 교환 횟수를 줄여주었다. 💾 소스 #include #include #include // memset #include // swap #define MAX 1000000 std::string answer; bool visited[MAX][11]; //..
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 라이브러리 없이 푼 버전 더보기 🖍 풀이 인접한 숫자는 ‘x’로 변경해주고 ‘x’를 제외한 암호문을 출력해주었다. 비밀번호(pwd)를 string으로 받는다. 가장 먼저 나오는 숫자의 인덱스 번호를 pre에 저장한다. pre+1 부터 자와 같은 쌍인지 확인한다. 같은 쌍 O → pwd[pre], pwd[i]를 ‘x’로 변경하고 반복문을 break한다. 같은 쌍 X → pre = i로 바꿔준다. 만약 i가 N이 되도록 break문을 통과하지 않았다면 더 이상 암호를 압축할 수 없으니 종료시켜준다. 💾 소스 #include #..
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 완전 이진 트리의 특성을 이용하여 풀자. 완전 이진 트리의 정점 개수: N 완전 이진 트리의 정점 번호: idx 현재 노드 번호로 자식 노드 개수의 개수를 알 수 있다. 트리로 표현했을 때 연산자가 유효할 수 있는 규칙을 찾아야 한다. 유효한 연산식 하나를 세워서 트리로 만들어 보자. 만들다 보면은 규칙이 보인다. 내가 찾은 규칙은 아래와 같고, 이 두 규칙 중 하나라도 위반하면 유효하지 않다고 판단해주었다. (1) N/2 미만의 노드는 숫자를 가질 수 없다. (2) N/2 이상의 단말노드들은 연산자를 가질 수 없..
🔗 문제 [S/W 문제해결 기본] 7일차 - 암호생성기 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 입력받은 배열에서 숫자 위치를 바꾸는 짓은 하기 싫었다. 다른 사람은 어떻게 푸는지 모르겠지만, 나는 원형큐 구현을 하며 깨달은 식을 응용했다. 1. 가장 첫번째 위치를 가르킬 변수 start를 하나 선언해준다. 2. start에 있는 번호를 감소시켰으면 start를 증가시킨다. 3. 증가시킬 때 start가 총 길이 N을 벗어나지 않도록 (start+1%N)해준다. 💾 소스 #include const int SIZE = 8; int main() { int tc = 1..
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 입력을 받을 때 .. 자식 0~2개수에 따라 어떻게 파싱해야하나 고민을 하느라 1시간 이상 풀었다. 개인적으로 이 문제부터 먼저 풀길 권한다. https://viin.tistory.com/121?category=986375 [C++] SWEA 1233번: 사칙연산 유효성 검사 🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 완전 이진 트리의 특성을 이용하여 풀자. 완전 이..
🔗 문제 [S/W 문제해결 기본] 3일차 - 회문2 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 회문은 각 셀의 위치에서 오른쪽과 아래 방향으로 검색할 수 있다. 아래 방향으로 검색하는 식 세우는게 귀찮아서 전치 행열(arr2)을 만들어줬다. 문제의 목표는 가장 긴 회문의 길이다. 그렇다면 최대 회문 길이인 100부터 감소시키며 가장 먼저 찾은 회문으로 탐색 횟수를 줄여준다. for(answer = SIZE; answer>0; --answer) { if(FindLongestPelindrome(arr, answer)) break; else if(FindLongestPelindrome(arr2, ans..