profile
내가 짱이다 😎 매일 조금씩 성장하기🌱

[프로그래머스 level2] 게임 맵 최단거리

https://programmers.co.kr/learn/courses/30/lessons/1844미로찾기 문제를 참고해서 DFS로 풀이했다. 정확성은 100이였지만, 효율성이 0이여서 69.9점밖에 받지 못했다. 이 문제는 '최단거리'를 푸는 문제기 때문에,

2021년 11월 1일
·
0개의 댓글
·

[프로그래머스 level2] 모음 사전

문제 https://programmers.co.kr/learn/courses/30/lessons/84512 문제 풀이 코드 DFS를 이용해서 중복순열을 구하고, 모든 조합을 정렬한 후, 원하는 word를 찾는다. 이때, sort()는 문자를 정렬하는 메소드이기때문에 단순하게 .sort()로 작성해줘도 된다. DFS 연습 많이 해야지!

2021년 10월 22일
·
0개의 댓글
·

[프로그래머스 level2] 소수 찾기

문제 https://programmers.co.kr/learn/courses/30/lessons/42839 문제 풀이 코드 순열 구하는것을 엄청 헤매서 오래 걸린 문제이다. 와 같이, for문을 통해 몇개를 뽑는지, i의 개수를 바꿔가면서 DFS를 호출하는 것이 관건이였다. 이방법에 대한 해답은 예전에 푼 문제인 순열구하기에서 찾을 수 있었다. DFS...

2021년 10월 21일
·
0개의 댓글
·
post-thumbnail

[프로그래머스 고득점 Kit] DFS/BFS_타겟넘버(level 2)

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 1, 1, 1, 1, 1로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.\-1+1+1+1+1 = 3\+1-1+1+1+1 = 3\+1+1-1+1+1 = 3

2021년 10월 6일
·
0개의 댓글
·

9-7) 섬나라 아일랜드(DFS 활용)

N\*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.만약 위와 같다면입력설명첫 번째 줄에 자연수 N(3&l

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

9-4) 미로탐색(DFS)

7\*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면위의 지도

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

9-3) 경로 탐색(인접리스트)

앞의 문제(9-2)와 동일 앞 문제에서 사용했던 인접행렬은, 시간복잡도가 높고 메모리도 많이 차지한다. 그러나 인접리스트는 시간복잡도가 낮으며 메모리도 많이 차지하지 않는다. 따라서 노드의 개수가 많아지면 인접리스트를 사용하는것이 좋다. 인접리스트의 원리는 다음과 같다

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

9-2) 경로 탐색(인접 행렬)

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는12345125 1342513451425 145총 6 가지입니다.입력설명첫째 줄에는 정점의 수 N(

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

9-1) 그래프와 인접행렬

9장은 그래프와 탐색을 DFS, BFS로 구현하는 문제들이다. (DFS, BFS의 개념은 앞 챕터 참고!) 그래프는 V(노드), E(엣지)의 집합이다. 따라서 G(V, E)로 표현하기도 한다. 여기서 E(엣지)란, 노드와 노드를 연결한 선이다. 그래프 이론에서 '인접행

2021년 9월 8일
·
1개의 댓글
·

8-15) 수들의 조합

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수 는 몇 개가 있는지 출력하는 프로그램을 작성하세요.예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-14) 조합 구하기

1부터N까지번호가적힌구슬이있습니다.이중 M개를뽑는방법의수를출력하는프로그 램을 작성하세요.입력설명첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.출력설명첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-13) 수열 추측하기(순열, 조합의 경우수 응용)

이 문제는 순열(8-10), 조합의 경우수(8-12)의 응용문제이다. 이해가 안되면 해당 챕터를 다시보고오자!가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-12) 조합의 경우수(메모이제이션)

조합은 위의 공식으로 계산합니다. 하지만 여러분은 이 공식을 쓰지않고 다음공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.입력설명첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.출력설명첫째 줄에 조합수

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-11) 팩토리얼

자연수 N을 입력하면 N!값을 구하세요. N! = n(n-1)(n-2).....21입니다. 만약 N=5라면 5!=5432\*1=120입니다.입력설명첫째 줄에 자연수 N(3<=n<=10)이 입력됩니다.출력설명첫째 줄에 N팩토리얼 값을 출력합니다.5120문제 풀

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-9) 동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.입력설명첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-8) 중복순열 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.입력설명첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.출력설명첫 번째 줄에 결과를 출력합니다.

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-7) 최대점수 구하기(DFS)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-6) 바둑이 승차(DFS)

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-5) 합이 같은 부분집합(DFS: 아마존 인터뷰)

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.둘로 나뉘는 두 부분집합은 서로소 집합이며,

2021년 9월 7일
·
2개의 댓글
·
post-thumbnail

8-4) 부분집합 구하기(DFS)

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.입력설명첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.출력설명첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.

2021년 9월 7일
·
2개의 댓글
·