본문 바로가기
반응형

전체 글147

[이코테][기출] 02. 곱하기 혹은 더하기 숫자 문자열의 왼쪽부터 오른쪽까지 하나씩 숫자끼리 연산을 해서 가장 큰수를 구하라. 연산은 '+'와 'x' 두개만 사용할 수 있다. 모든 연산은 왼쪽부터 순서대로 이루어진다. 문자열을 정수형 배열에 변환해서 담는다. for문으로 숫자를 하나씩 확인하면서 만약 0이면 다음에 '+', 아니면 'x'를 오게해서 Queue에 저장한다. 다음 for문으로 큐에서 연산자를 하나씩 빼면서 숫자 연산을 해서 ans에 누적시킨다. ----------------------------------------------------------------------------------------------- 첫번째 수는 ans 변수에 저장한다. 그 뒤 숫자부터 for문을 돌리면서 두 수중 하나라도 1이나 0이면 두 수를 '+' .. 2022. 10. 18.
[이코테][기출] 01. 모험가 길드 모험가가 N명 있다. 공포도가 X인 모험가는 반드시 X명 이상의 모험가 그룹이 필요하다. 최대 몇명의 모험가 그룹을 만들 수 있는가? 배열 A[N]을 정의해서 공포도를 저장한다. 오름차순으로 정렬한다. for (i = N to 0) A[N]의 공포도만큼 i를 전진하고, count++한다. (10분 걸림) 오름차순으로 정렬하는 것까지는 생각함. 하지만 공포도가 낮은 것부터 확인해서 일단 그룹에 모험가를 포함시키고 그 수와 현재 확인중인 공포도를 비교하는 로직은 생각하지 못함. --------------------------------------------------------------------------------------------- 공포도를 기준으로 오름차순으로 정렬을 한다. 공포도가 낮은 모험가.. 2022. 10. 18.
[백준] 2293번 - 동전 1 (Java) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동전의 종류가 n개 있다. k원이 되도록 하는 경우의 수를 구해야 한다. 동전의 수는 제한이 없다. 시간제한이 0.5초 이므로 이분탐색 혹은 DP일 가능성이 높다. 배열을 사용해서 동전의 가치를 저장한다. dp[i]는 i원까지 동전의 경우의 수이다. 10원을 표현하기 위해 동전 1, 2, 5를 갖고 있을 때 경우의 수는 점화식 dp[n] = dp[n-1] + dp[n-2] + dp[n-5] impo.. 2022. 10. 14.
[백준] 9663번 - N-Queen (Java) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표 문제이다. 퀸은 상하좌우 대각선으로 거리제한 없이 움직일 수 있다. 그 동선에 걸리지 않도록 다른 퀸을 N개 배치를 하는 경우의 수를 구하는 문제이다. 각 행별로 놓을 수 있는 위치가 발견되면 재귀호출을 해주고, N개 만큼 배치가 되었다면 count+1을 해준다. * 두가지 문제 1. 재귀호출을 어떤 방식으로 할 것인가 2. 퀸을 놓을 수 있는 위치인지 어떻게 판단할 것인가 * 체스판의 퀸을 일차.. 2022. 10. 13.
[백준] 15651번 - N과 M(3) (Java) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복숫자와 순열 모두 허용이다. N과 M (1)과 (2)에서 중복을 막기 위해 사용했던 visited[]을 사용 안하면 된다. 다만, 출력을 System.out.print()를 하게 되면 시간초과가 난다. 대신 StringBuilder로 문자열을 계속 머지한다음 마지막 한번 출력했더니 통과했다. import java.util.Scanner; //[백준] 15651번 - N과 M(3) (Java).. 2022. 10. 13.
[백준] 15650번 - N과 M(2) (Java) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(1)과 비슷한데 중복 순열을 허용하지 않는 점이 차이가 닌다. 이전 문제는 중복 숫자만 방문배열을 통해서 처리를 했는데 이 문제에서는 순서가 달라도 중복이면 표시하면 안된다. 예제를 보면, 4 2 ---- 1 2 1 3 1 4 2 3 2 4 3 4 이런 식으로 1로 시작하는 값이 2로 시작하는 순열을 시작할 때 중복체크 락이 걸려있어야 한다. (1)에서는 재귀 호출에서 돌아오면 중복체크.. 2022. 10. 13.
[백준] 15649번 - N과M(1) (Java) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다. dfs탐색을 사용한 백트레킹 알고리즘으로 풀자. 백트레킹은 탐색할 노드를 조건문으로 판단하여 유.. 2022. 10. 13.
닥익스트라 최단경로 알고리즘 다익스트라 알고리즘 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'한 뒤에, 그 노드를 거쳐 가는 경우를 확인하여 최단 거리를 갱신하는 방법이다. 우선순위 큐를 이용하여 풀 수 있다. 1. 문제가 주로 한 정점에서 다른 정점까지 가는 최단거리를 계산하는 게 주로 나온다. 2. Java의 경우 class Node를 만들어서 정점과 간선을 표현하자. // PriorityQueue 사용을 위해 Comparable 사용함 class Node implements Comparable { int v; // 정점 int c; // 이동값 Node (int v, int c) { this.v = v; this.c = c; } @Override public int compareTo(Node o) .. 2022. 10. 13.
[백준] 14713번 - 앵무새 (Java) N마리의 앵무새가 한 문장씩 이야기 한다. 다른 앵무새가 문장을 이야기 하는 중간에 다른 앵무새가 치고 들어올 수 있다. 예제 문장이 조합이 가능하면 possible, 불가능하면 Impossible을 출력한다. 큐를 배열로 N개만큼 만들어서 앵무새의 문장을 단어로 잘라서 저장한다. 테스트 문장은 배열, 리스트 혹은 큐로 저장하자. 테스트 문장을 루프를 돌리면서 첫 단어를 앵무새 문장의 첫 단어에 있는지 루프를 돌리며 탐색하자. 있으면 그 단어는 삭제하고 다음으로 넘어가자. 없으면 바로 Impossible 출력한다. 테스트 문장 끝까지 무사히 탐색했으면 Possible을 출력한다. 받아적은 문장의 단어의 수와 N개의 앵무새가 말한 단어의 수가 같아야 한다. 받아적은 문장의 단어검색이 끝났는데 앵무새의 단어.. 2022. 10. 12.
반응형

티스토리툴바