전체 글505

• 

  조합과 중복조합 조합 cnt가 M(총 뽑아야 하는 개수)과 동일하면 끝난다. start+1부터 N(뽑을 수 있는 수의 개수)까지 중복체크 없이 돈다. 이미 start+1부터 시작했기 때문이다. 다음 조합을 위해 start+1값부터 N까지 넣어서 재귀 호출한다. private static void findC(int cnt, int start) { if(cnt==M) { for(int i=0;i 공부/ALGORITHM 2022. 2. 20.

• 

  순열과 중복순열 순열 중복을 제거하기 때문에 flag가 필요하다. cnt가 M(총 뽑아야 하는 개수)과 동일하면 끝낸다. 0부터 N(뽑을 수 있는 수의 개수)까지 중에서 이미 뽑은 수를 제외하고 해당 순서에 숫자를 저장한다.(순열 저장 배열) 다시 재귀로 다음 순서부터 순열을 찾는다. private static void findP(int cnt, int flag) { if(cnt==M) { for(int i=0;i 공부/ALGORITHM 2022. 2. 20.

• 

  [BOJ] 2606 바이러스 - JAVA 1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. 2. 풀.. 코딩테스트/BOJ 2022. 2. 20.

• 

  [BOJ] 1260 DFS와 BFS - JAVA 1. 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 2. 풀이 private static void bfs(int v) { visited[v].. 코딩테스트/BOJ 2022. 2. 20.

• 

  [BOJ] 2840 행운의 바퀴 - JAVA 1. 문제 https://www.acmicpc.net/problem/2840 2840번: 행운의 바퀴 첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓 www.acmicpc.net 2. 풀이 같은 알파벳이 여러 개 있을 수 없으므로 26칸 boolean배열을 만든다. 룰렛 배열은 ?로 초기화한다. 룰렛을 시계방향으로 돌린다는 건 반시계방향으로 화살표가 글자를 가리킨다는 뜻이다. 따라서 글자가 몇 번 바뀌었는지 받고 %N을 한 뒤에 (idx+N-(S%N))%N을 idx에 다시 저장한다. 현재 인덱스+N을 해준 건 %N을 해주었을 때 음수가 나오지 않게 하기 위한 것이다... 코딩테스트/BOJ 2022. 2. 20.

• 

  [BOJ] 1063 킹 - JAVA 1. 문제 https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 킹은 다음과 같이 움직일 수 있다. R : 한 칸 오른쪽으로 L : 한 칸 왼쪽으로 .. 코딩테스트/BOJ 2022. 2. 20.

• 

  [SWEA] 1247 최적경로 - JAVA 1. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다. 회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100) 두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다. 회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다. 회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가.. 코딩테스트/SWEA 2022. 2. 20.

• 

  [SWEA] 3234 준환이의 양팔저울 1. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 2. 풀이 왼쪽 저울에 올라갈 순열을 찾는다. cnt==N이면 다 찾은 경우이므로 result에 1을 더한다. 경우의 수를 찾다가 중간에 이미 left가 나머지+right보다 더 크면 그 뒤의 경우의 수((N-cnt)! * 2^(N-cnt))를 전부 더해주고 끝낸다. 0부터 N-1 중에 이미 뽑은 추는 제외하고 나머지를 오른쪽, 왼쪽으로 저울에 올린다. (재귀호출).. 코딩테스트/SWEA 2022. 2. 20.

• 

  [BOJ] 15683 감시 - JAVA 1. 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없.. 코딩테스트/BOJ 2022. 2. 20.

• 

  [BOJ] 3060 욕심쟁이 돼지 - JAVA 1. 문제 https://www.acmicpc.net/problem/3060 3060번: 욕심쟁이 돼지 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 두 줄로 구성되어 있고, 첫째 줄에는 하루에 배달되는 사 www.acmicpc.net 돼지는 원형 식탁에 앉아서 식사를 한다. 현수의 돼지들은 기억력이 뛰어나기 때문에 전 날 자신의 양쪽과 맞은편에 앉았던 돼지가 먹었던 양을 기억하고 있다. 또, 욕심도 많기 때문에, 그 만큼의 양을 추가하여 식사를 하기를 원한다. 매일 현수의 집에 신선한 사료가 N만큼 배달된다. 첫 날 돼지들이 먹었던 양이 주어졌을 때, 현수가 6마리의 돼지들의 요구를 들어줄 수 없게 되는 날이 몇 번.. 코딩테스트/BOJ 2022. 2. 18.

• 

  [BOJ] 3085 사탕게임 - JAVA 1. 문제 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 2. 풀이 위에서부터 오른쪽으로 swap처음위치를 바꾸기 때문에 nr,nc는 항상 아래쪽과 오른쪽만 보면 된다. N 범위에 들어오고 바꾸려는 요소가 이전과 같지 않다면 교환하고, 이 상.. 코딩테스트/BOJ 2022. 2. 18.

• 

  [BOJ] 1987 알파벳 - JAVA 1. 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. .. 코딩테스트/BOJ 2022. 2. 18.