본문 바로가기

알고리즘 문제77

[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.
[백준 - Java] 1759번 : 암호 만들기 문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 설명 조합을 이용해 주어진 C개의 문자로 만들 수 있는 L개의 암호 조합을 구하면 된다. 조합을 구한 뒤에는 모음의 개수가 적어도 1개 이상, 자음의 개수가 2개 이상이 되는 경우만 정답 리스트에 추가하면 된다. 아래 조합 포스트를 참고하면 좋다. [Java] 조합 Combination 전체 코드 import java.util.ArrayList; import java.util.Arrays; imp.. 2021. 7. 27.
[백준 - Java] 4386번 : 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 설명 주어진 각 별의 좌표를 이용해 모든 간선을 만들고 가중치(두 별 사이의 거리)를 저장한다. Kruskal 알고리즘을 이용해 최소 신장 트리를 구성해 최소 비용을 구한다. 크루스칼 알고리즘은 Union-Find를 이용해 구현할 수 있다. 전체 코드 import java.util.ArrayList; import java.util.Collections; import java.util.Scann.. 2021. 7. 27.
[백준 - Java] 1987번 : 알파벳 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 설명 DFS, 백트래킹을 이용해 구현 (0, 0)부터 시작해서 상하좌우 이차원 배열 범위를 넘지 않고, 방문하지 않았던 곳으로 이동 이동할 곳에 있는 알파벳이 지금까지 DFS를 돌며 만들어진 문자열 str에 포함되지 않는 문자라면 str에 추가하고 길이도 +1 가장 최장 길이를 구해야 하기 때문에 매 DFS마다 길이 length와 최장 길이를 저장할 ans의 값을 비교해 업데이트 해주.. 2021. 7. 16.
[프로그래머스 - Java] 번 : 가장 큰 수 문제 https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 설명 처음에 순열을 구해서 모든 수를 구한 뒤에 최대 값을 구하면 되지 않을까라고 생각했다. 하지만 순열은 모든 수의 조합을 구하다보니 너무 커서 그런가 런타임 에러가 났다...ㅠㅠ 구글에 검색한 결과 역시 문제의 분류가 정렬이다보니 정렬로 풀면 쉽게 끝나는 문제였다..! 하지만 일반 정렬이 .. 2021. 6. 11.
[프로그래머스 - Java] 주식 가격 문제 https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 설명 스택 / 큐로 분류된 문제라 이걸 활용해야 하나 싶었는데 그냥 이중 for문으로 풀었다. 정확성, 효율성 시간초과 안나더라! 아무튼 현재 주식가격을 기준으로 그 이후의 주식 가격들을 순회하면서 시간을 + 1 해 나간다. 그러다 현재보다 작은 주식 가격을 만난다면 순회를 멈추면 된다. 이를 이중 for문으로 모든.. 2021. 6. 10.
반응형

티스토리툴바