problem solving/SWEA

🔗 문제SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  🖍 풀이양방향 리스트를 지원하는 컨테이너 list 를 활용해서 풀어도 된다. 기존 암호문: list의 뒤에 데이터를 연달아 삽입한다.새 암호문: list는 임의 위치 엑세스가 불가하다는 특징이 있다. 그래서 string이나 vector처럼 container[i+x]가 불가능하다. 대신 반복자 iter를 사용해주었다. list의 begin()부터 x번 반복자를 이동시켜야 삽입할 위치를 iter에 저장한다. 그리고 나서 insert(삽입 위치, 데이터)하여 새 암호문을 넣어준다.이 때, 명령문마다 삽입할 위치 (x)가 다르므로..

🔗 문제SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com ✏️ 풀이문제에서 대놓고 비트마스크라고 힌트를 주어서 어렵지 않은 문제지만 생각해보지 못한 풀이 방법을 배워서 풀이를 남긴다. 일단 문제를 읽자. (위 사이트 참고) M이 최대 10^8승 (1억)이므로 배열로 순회하면 C++ 기준 1000ms 이내에 제출해야 하는데 바로 시간초과행이다 🙂그에 비해 N은 최대 30이므로 절대 시간초과가 안 걸릴 줄 알았는데 시간초과에 걸렸다.테스트케이스가 1만개 중에 9883개를 맞추길래 부랴부랴 FAST IO를 적용해서 맞출 수 있었다. FAST IO를 습관화 하자.1000ms를 못 넘겨서 ..

🔗 문제 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..