삼성전자 알고리즘 (65) 썸네일형 리스트형 9. 2581 : 예산 문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1842&sca=50&sfl=wr_subject&stx=%EC%98%88%EC%82%B0&sop=and JUNGOL | 예산 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 771 회 시도횟수: 2997 회 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. (1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. (2 jungol.co.kr.. 1. 더하기 [DFS] 덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다. 철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자. 첫 번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다. 두 번째 줄부터 아래 내용이 T개 만큼 주어진다. 첫 줄에 자연수 개수 N(5 8. 1889 : N Queen [DFS] 문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162&sca=50&sfl=wr_subject&stx=queen&sop=and JUNGOL | N Queen > 문제은행 제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 2500 회 시도횟수: 7257 회 체스에서 queen의 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다. 즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때, 그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다. N X N 크기의 정방형 체스판이 주어졌다. 우리는 거기에 N개의 queen을 배치하려고 하는데, jungol.co.kr 문제 풀이 : .. 7. 1169 : 주사위 던지기1[DFS] 문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=50&sfl=wr_subject&stx=%EC%A3%BC%EC%82%AC%EC%9C%84&sop=and JUNGOL | 주사위 던지기1 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 1525 회 시도횟수: 3247 회 주사위를 던진 횟수 N과 출력형식 M을 입력 받아서 M의 값에 따라 각각 아래와 같이 출력하는 프로그램을 작성하시오. M = 1 : 주사위를 N번 던져서 나올 수 있는 모든 경우 M = 2 : 주사위를 N번 던져서 중복이 되는 경우를 제외하고 나올 수 있는 모든 경우 M = 3 : 주사위를 N번 던져서 모두 다른 수가 나올 수 있는 모든 경.. 코딩인터뷰완전분석 : 자외선을 피해가기(BFS) + Heap 문제내용 : 영희는 자외선이 피부에 좋지 않기 때문에 이동 시 자외선에 노출되는 것을 최소한으로 하고 싶어서 가는 길의 자외선 양을 모두 조사하였다. N*N 모양의 장소의 모든 길의 자외선 양이 주어지고 영희는 상하좌우 한 칸씩만 이동이 가능하다. 시작점(1,1)에서 도착점(N,N)까지 이동 시 자외선 합의 최소값을 찾아라. 예를 들어 3*3 장소의 자외선 양이 아래와 같다면 오른쪽처럼 이동하면 8만큼만 노출된다. 입력 첫 줄에 N(2≤N≤100)이 들어온다. 그 다음 줄부터 N개의 줄에 각각 N개씩 M(0≤M≤9)이 공백 없이 들어온다. 출력 출발점에서 도착점까지 자외선 합의 최소값을 출력한다. 풀이 : #include #define MAX 101 #define SWAP(a, b, type) {type.. 5. 1078 : 저글링 방사능 오염 문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=50&sfl=wr_subject&stx=%EC%A0%80%EA%B8%80%EB%A7%81&sop=and JUNGOL | 저글링 방사능 오염 > 문제은행 제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 2154 회 시도횟수: 6759 회 승훈이는 심심한 시간에 스타크래프트(Starcraft) 게임을 하며 놀고 있었다. 스타크래프트 유닛중 하나인 저글링을 한 곳에 몰아세운 뒤, 방사능 오염 공격으로 없애보려고 했다. 그런데 좀 더 재미있게 게임을 하기 위해서 게임을 개조하여 방사능 오염 공격을 가하면 방사능은 1초마다 이웃한 저글링에 오염된다. 그리고 방사능에 오염된 저글.. 4. 1661 : 미로 탈출 로봇 문제 원본 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=50&sfl=wr_hit&stx=1661&sop=and JUNGOL | 미로 탈출 로봇 > 문제은행 제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 590 회 시도횟수: 2465 회 정올에서 미로탈출 로봇 대회를 개최하였다. 대회에 사용되는 미로는 가로(X), 세로(Y) 100이하의 크기이며, 미로를 한 칸 이동하는 데는 1초가 걸린다. 대회에 참가중인 민성이는 자신의 로봇이 가장 빨리 미로를 탈출하기 위해 미로의 모양을 입력받아서 도착점까지 가장 빠른 길을 찾으려고 한다. 프로그램을 작성하여 민성이를 도와주자. jungol.co.kr 문제 풀이 : #include #.. BFS / DFS DFS : 1) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 3) 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다 (완전탐색) 특징 : 1)자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다. 2)어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다 시간 복잡도: DFS는 그래프 (정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다. -인접 리스트로 표현된 그래프 : O(N+E) -인접 행렬로 표현된 그래프 : O(N^2) 출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.. 이전 1 2 3 4 5 6 ··· 9 다음