본문 바로가기

Algorithm

 (2139)
(Javascript) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[3차]) : n진수 게임 programmers.co.kr/learn/courses/30/lessons/17687?language=javascript 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 문자열 문제였습니다. 풀이방법 1. t*m만큼 10진수 i를 n진수로 변환해 num이라는 문자열 변수에 이었습니다. 2. 튜브의 차례마다 말해야할 문자를 tmp변수에 붙인 후 t의 길이만큼 잘라줍니다. 3. 소문자라면 대문자로 바꾼뒤 정답을 반환합니다. Code //진수 수개수 참가인원 튜브순서 function solutio..
(C++) - 백준(BOJ) 16935번 : 배열 돌리기 3 답 www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 무지성 구현으로 푼 문제였습니다. *3, 4 연산시 n*m이 m*n이 된다는 점 주의해야합니다. Code #include using namespace std; int n, m, r, arr[101][101]; void calculateOne(){ for(int i = 1; i
(C++) - 백준(BOJ) 14719번 : 빗물 답 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 왼쪽에서 오른쪽으로 보면서 현재 높이가 이전 높이보다 낮다면 여태까지 가장 큰 높이의 블록높이 - 현재 블록의 높이 즉, 가로에서 i번째 위치에서 고이는 빗물의 높이 값을 d[i][0]에 저장합니다. 만약 높다면 가장 높은 높이의 값을 갱신해줍니다. 2. 오른쪽에서 왼쪽으로 보면서 같은 방식을 적용합니다. 3. 다시 처음부터 끝까지 보면서 고인 빗물의 최소값을..
(C++) - 백준(BOJ) 15988번 : 1, 2, 3 더하기 3 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net dp문제였습니다. 풀이방법 * 답이 나올 수 있는 범위를 조심해야합니다. int범위를 초과할 수 있으므로 long long으로 변수를 선언해줘야합니다. * 테스트 케이스로 인해 출력이 많아지므로 c와 동기화를 끊어 입출력이 빨라지도록 합니다. * Modular 연산을 주의해야합니다. 덧셈에 대해 분배법칙이 성립하나 더할 때 마다 범위가 초과할 수 있으므로 매번 더할 때 마다 Modular 연산을 해줘야 합니다. i를 만드는 경우의 수는 i-1을 만드는 경우의 수..
(C++) - 백준(BOJ) 1722번 : 순열의 순서 www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지 www.acmicpc.net 구현문제였습니다. 풀이방법 예제에서 n = 4 소문제 번호가 1인 경우를 예시로 설명하겠습니다. 나올 수 있는 모든 순열의 경우 수는 4!이므로 24개입니다. 24개 중 천의 자리 1로 시작하는 순열들을 1 ~3! 번째 순열 사이에 있습니다. 천의 자리 2는 3! + 1 ~ 3! + 3! + 1! 천의 자리 3은 3! + 3! +1 ~ 3! + 3! + 3! +1 천의 자리 4는 3! + 3..
(C++) - 백준(BOJ) 2407번 : 조합 www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 조합, 큰 수 더하기 구현 문제였습니다. 풀이방법 1. long long 범위를 초과하기 때문에 string으로 수를 중간에 바꿔줘야 overflow가 발생하지 않습니다. 2. dfs를 통해 nCm = n-1Cm-1 + n-1Cm이라는 조합식을 구현할 수 있습니다. Code #include #define ll long long using namespace std; ll n, m, ans; string comb[101][101]; string numToString(string a, string b){ ll sum = 0; str..
(C++) - 백준(BOJ) 10972번 : 다음 수열 www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 조합문제였습니다. next_permutation은 다음 수열이 있다면 다음 수열로 바꿔준다음 true를 반환합니다. 만약 현재 vector가 마지막 수열이라면 false를 반환합니다. 풀이방법 next_permutation이 false라면 -1를 출력해줍니다. 그 외에는 다음 수열을 출력해줍니다. Code #include using namespace std; int n; int main(){ cin >> n; vector v(n); for(auto &n : v) cin ..
(C++) - 백준(BOJ) 2170번 : 선 긋기 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net sweeping문제였습니다. *c와 동기화를 끊지 않으면 시간초과가 나는데 이유를 잘 모르겠습니다. 아시는 분은 댓글 달아주시면 감사하겠습니다. ㅠㅠ 풀이방법 1. vector pair 자료구조인 point라는 변수에 x,y값을 n번만큼 입력받습니다. 2. first를 기준으로 오름차순 first가 같다면 second 기준으로 오름차순 정렬해줍니다. 그 후 startPoint는 가장..

티스토리툴바