본문 바로가기
  • "하나씩 기록하다보면 누군가에게 도움이 되지 않을까"
728x90

IT/알고리즘 풀이25

[백준] [자바] 14889번 : 스타트와 링크 문제 출처 : www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1. 풀이 접근 조합으로 nCr 구함. n은 입력으로 주어지고 r은 n/2임. 나는 home팀, away팀으로 구분하였음. (Ex. 만약 사람수가 4면 2로 조합을 구하고 나머지 2가 상대팀, 사람수가 6이면 3으로 조합을 구하고 나머지 3이 상대팀 순) home팀, away팀에 대하여 점수를 다 더해야됌 (Ex. 1,2 3,4 로 팀이 나누어졌을 경우 S12와 S21 둘다 더해야됌 away 도 마찬가지) (Ex. 1.. 2021. 3. 18.
[백준] [자바] 14891번 : 톱니바퀴 문제 출처 www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 1. 풀이 접근 회전하기 전에 미리 N극 S극에 대한 상태를 저장해 둠 회전할 때 기준점을 기준으로 왼쪽/오른쪽 나눠서 탐색 동시에 다 회전 ※ 소스 내에 과정에 있어서 이해하기 위해 간단한 주석 달아둠 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/blob/master/Solve_Algs/src/Git_BJ_14891/Main.java Choi-JinYeong/So.. 2021. 3. 17.
[백준] [Java] 12865번 : 배낭 채우기 문제 1. 풀이 접근 gsmesie692.tistory.com/113 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 gsmesie692.tistory.com 혼자 풀다가 그리디도 써보고 DFS도 써봤는데 반례생기거나 시간초과 나길래 참고해서 문제 풀었음. 위에 분이 매우 상세하게 적어주셔서 출처로 밝힘 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/blob/master/Solve_Algs/src/BJ_12865/Main2.java Choi-JinYeo.. 2021. 3. 6.
[백준] [Java] 17822번 : 원판 돌리기 문제 출처 : www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 1. 풀이 접근 원판 회전해야 할 배수 계산 원판 회전 인접 숫자 찾기 (원판이 회전하기 때문에 x축 기준으로 끝에 도달하면 인덱스 변경해줌) 인접 숫자 있을 시 인접 숫자 삭제, 인접 숫자 없을 시 평균값 구한 뒤 평균보다 크면 +1, 작으면 -1 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/blob/master/Solve_Algorithm/src.. 2021. 2. 19.
[백준] [Java] 14502번 : 연구소 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 풀이 접근 조합으로 벽 설치 할 수 있는 경우의 수 산출 벽 설치 후 바이러스 위치 기준으로 BFS 검색 이동 가능할 때마다 바이러스 숫자 2로 변경 더 이상 탐색 불가능 시 0 개수 산출 후 최대값 비교 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/tree/master/Solve_Algs/src/Sol_BJ_14502 Choi-JinYeong/Solve_Alg 알고리즘 풀이... 2021. 2. 18.
[백준] [Java] 14500번 : 테트로미노 출처 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1. 풀이 접근 테트로미노 5가지 모양에 따라 기준점으로 부터 검색할 곳으로 배열로 선언 (회전시 모양도 기준점으로부터 다 미리 작성해서 반영해둠) 기준점(모든 맵 좌표)에 따라서 넘어 가면서 검색하면서 맵 안에 있을 시 더함 ㅗ 모양은 기준점으로 가운데 기준점으로 부터 BFS로 확인, 나머지모양은 기준점으로부터 DFS로 확인 (맞는지 잘 모르겠음, 그냥 이동방향에 따라서 계속 탐색) 끝까지 다 탐색해.. 2021. 2. 17.
[알고리즘] SWEA - 보물상자 비밀번호 (5658) 보호되어 있는 글 입니다. 2020. 6. 8.
[알고리즘]SWEA - 핀볼 게임 (5650) 보호되어 있는 글 입니다. 2020. 6. 8.
[알고리즘] SWEA - 숫자배열 회전 (1961) 보호되어 있는 글 입니다. 2020. 6. 8.
[알고리즘] 완전탐색 - 수학포기자 보호되어 있는 글 입니다. 2020. 3. 25.
728x90

티스토리툴바