본문 바로가기

알고리즘 문제/SWEA6

[SWEA - Java] 1266. 소수 완제품 확률 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Sx36IwACFAZN 설명 주어진 시간은 90분이며, 각 가구 장인은 5분 안에 최대 1개의 완제품을 만들 수 있다고 가정 5분에 성공하면 최대 1개 / 실패하면 0개 90분간 모두 성공하면 → 18개 90분간 모두 실패하면 → 0개 5분 10분 15분 ... 90분 1 2 3 16 17 18 Fail : 0 or Success : 1 18개 중 소수는 → 2, 3, 5, 7, 11, 13, 17 → 2개, 3개, ... , 17개 해당 소수 개의 개수만큼 완제품이 나올 확률을 다 더한 값 → 장인이 만든 완제품의 수가 소수일 확률 A장인, B장인 두 명.. 2021. 10. 27.
[SWEA - Java] 1232. 사칙연산 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 설명 위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다. 사람들은 사칙 연산을 할때 (9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다.하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다.즉 (9/(6-4))*3 → 964-/3*으로 변환되고 이를 계산한다. 따라서 해당 문제에서는 트리를 입력받고 후위 순회하며 각 단계에서 계산을 해주면 된다. 트리에서 후위 표기식 계산 방법 스택을 이용해 계산하면 된다. 숫자일 경우 바로 스택에 넣는다.. 2021. 10. 24.
[SWEA - Java] 1231. 중위순회 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD 설명 트리를 구성할 때는 1차원 배열, 2차원 배열, 클래스 등 다양한 방법으로 구현할 수 있다. [Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 이 문제는 1번 노드부터 완전 이진트리 형식으로 주어지기 때문에 1차원 배열만으로도 중위 순회를 처리할 수 있다. 따라서 배열의 각 인덱스에 해당하는 알파벳 값을 저장하고 재귀를 이용해 순회할 수 있다. N번 노드의 왼쪽 자식 노드는 N * 2번 노드, 오른쪽 자식 노드는 N * 2 + 1번 노드가 된다. 중위 순회는 왼쪽 자식 노드 → 부모노.. 2021. 10. 24.
[SWEA - Java] 1233. 사칙연산 유효성 검사 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 설명 사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라. 여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다. (단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 .. 2021. 10. 24.
[SWEA - Java] 1265. [S/W 문제해결 응용] 9일차 - 달란트2 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18R8FKIvoCFAZN 설명 묶음을 어떻게 나눠야 할까? DP? 완전 탐색? 잘 생각해보자. 10 달란트를 3묶음으로 나눌 경우 어떻게 나누어야 가장 많은 사탕을 교환할 수 있을까? 각 묶음에 들어있는 달란트 수의 차이가 최소여야 곱했을 때 얻는 사탕의 수가 크다 즉, N개를 묶음 P로 나눈 각 묶음의 숫자의 차이가 작아야만 곱했을 때 값이 커진다. 이렇게 되면 문제는 쉬워진다. N개를 말 그대로 N / P만큼으로 나누자. 나머지가 생길 수 도 있고 안 생길 수도 있다. 나머지가 안 생기면 그대로 N / P만큼으로 나누고 끝인 거고, 나머지가 있다면 각 남.. 2021. 10. 21.
[SWEA - Java] 2814 : 최장 경로 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 전체 코드 dfs를 하되, 각 정점마다 dfs를 모두 해보면서 최장 경로를 따져봐야 한다. 그렇기에 dfs후에 정점 인덱스에 해당하는 visited 값을 false로 만들어주어야 한다. (아예 dfs를 시작할 for문 안에서 visited를 초기화해주어도 된다.) 그리고 갔다 온 정점은 visited의 값이 true인데 이것 역시 재귀가 종료될 때 false로 만들어주어야지 최장 경로 구할 수.. 2020. 6. 6.
반응형