https://school.programmers.co.kr/learn/courses/30/lessons/12902 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 보고나서 맨 처음 들었던 생각은 dfs를 통해서 모든 타일을 구해볼까 했다가, 시간초과가 날 것 같았다. 괜히 " 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요." 라는 제한사항이 걸려있는게 아닐 것이기 때문이다. 그래서 완전탐색으로 알아보자는 생각은 얼마 안가 접게 되었고, 차근차근 생각해보기로 했다. N = 4일때는 2칸씩..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 시간 제한 메모리 제한 solved.ac 티어 1초 128MB 골드 3 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은..
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 시간 제한 메모리 제한 solved.ac 티어 1초 256MB 실버 2 문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 시간 제한 메모리 제한 solved.ac 티어 1초 256MB 골드 4 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하..
https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 실제로 2차원 배열로 만들어서 일일이 1차원 배열로 바꾸고, 이를 자르는 구현을 한다면 뭐 당연히 시간초과나 메모리초과 둘중하나는 무조건 뜰 것이다. n의 최댓값이 10^7인데, n X n 크기의 2차원 배열을 만든다면, 10^14개의 int가 들어가고, 여기서 메모리 초과가 당연히 날 것. 결국 우리는 배열을 만드는 것이 아닌, i행 j열의 숫자를 i와 j를 통해 일반화하여, 그 숫자..
https://school.programmers.co.kr/learn/courses/30/lessons/77484 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현문제이다. 굳이 알고리즘적이 내용을 부여하자면 탐색문제이다. 그것도 아주 간단한 순차탐색. 몇개의 숫자가 지워져 있기 때문에, 최저 순위는 지워지지 않은 나머지 숫자중에서 정답과 일치하는 숫자의 개수로 따지면 될 것이고, 최고 순위는 여기에 0의 개수를 더해주면 될 것이다. 간단한 상황을 통해 이해해보자. 만약 0이 3개이고, 같은 숫자가 2개, 다른 숫자 1개라면, 최저 5등은 보장한다. 2..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 시간 제한 메모리 제한 solved.ac 티어 1초 192MB 실버 1 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오..
https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 처음 봤을 때에는 그리디나 DP로 접근해야할 것 같았는데, 개수가 생각보다 많지 않아서, 완전탐색으로 진행해도 무방할 것 같았다. 모든 경우를 따지기 위해, C++의 next_permutation함수를 통해 순열을 구성했고, 이를 통해 모든 경우를 탐색했다. #include #define ALL(X) X.begin(),X.end() using namespace std; int solution..
