본문 바로가기

Algorithm

 (2139)
(C++) - 프로그래머스(연습문제) : N-Queen https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr backtracking문제였습니다. 풀이방법 퀸이 놓일 수 있는 자리라면 dfs를 호출해줍니다. pruning 방식은 well-known입니다. Code #include #include using namespace std; int ans, N; vector board; int isOk(int tuple) { for (int col = 0; col ..
(C++) - 프로그래머스(연습문제) : 멀리 뛰기 https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr dp문제였습니다. 풀이방법 1칸 또는 2칸을 뛰므로 n에 도착하기 위한 경우의 수 점화식은 다음과 같습니다. D[n] = D[n-1] + D[n-2] Code #include #define MOD 1234567 using namespace std; using ll = long long; ll d[2001]..
(C++) - 프로그래머스(연습문제) : 최고의 집합 https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 수학 문제였습니다. 풀이방법 1. 몫이 0이라면 -1을 담아 반환합니다. 그 외에 가장 곱이 크기 위해서는 s/n값이 n개 있을 때 입니다. 따라서 s/n값을 n개 가지고 있는 vector ans를 선언합니다. 2. ans의 끝부터 끝 - s%n 으로 오면서 나머지를 1씩 배분해줍니다. 3. 정답을 반환합니다. Code #include ..
(C++) - 프로그래머스(2017 팁스타운) : 예상 대진표 https://programmers.co.kr/learn/courses/30/lessons/12985?language=cpp# 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 수학 문제였습니다. 풀이방법 토너먼트 방식이므로 n을 2로 나누어가며 a와 b가 왼편과 오른편에 위치해 있으면 해당 라운드에는 만난다는 것을 알 수 있습니다. 재귀를 이용해 해결합니다. * a와 b는 누가 더 큰지 명시되어 있지 않기 때문에 여러 입력에 대해 고려해야합니다. * 만약 a와 b가 모두 n/2기준으로..
(C++) - 백준(BOJ) 1655번 : 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 문제였습니다. 풀이방법 * 입 출력이 많으므로 c와 동기화를 끊어줘야 합니다. 제 소스코드의 #define의 fastio 참고하세요. 최대 힙, 최소 힙 이렇게 두 개의 우선순위 큐를 선언해줍니다. 이 두개로 중앙값을 찾기 위해 규칙을 세웁니다. 1. 최대 힙과 최소 힙의 원소 개수가 같다면 최대힙에 push를 먼저해줍니다. 2. 최소 힙의 원소들은 최대 힙의 원소 이..
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 점프와 순간이동 https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 진수활용 문제였습니다. 풀이방법 *가장 먼저 떠올릴 수 있는 풀이방법은 bfs나 다익스트라이지만 n이 10억이므로 시간복잡도가 높아집니다. 따라서 다른 방식을 생각해야합니다. 점프를 한 것은 현재자리에서 1칸을 움직인 것에 해당하며 순간 이동을 하게되면 현재자리에서 *2를 하므로 다음 자리로 넘어가게 됩니다. 이는 이진수의 속성에 대입해볼..
(C++) - 프로그래머스(월간 코드 챌린지 시즌2) : 약수의 개수와 덧셈 https://programmers.co.kr/learn/courses/30/lessons/77884 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr brute force 문제였습니다. 풀이방법 한 숫자에 대해 약수의 개수를 찾고 짝수면 해당 수를 더하고 홀수면 해당 수를 빼줍니다. Code #include #include using namespace std; int getNum(int num){ int cnt = 0; for(int i = 1; i
(C++) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[3차]) : 파일명 정렬 https://programmers.co.kr/learn/courses/30/lessons/17686 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 문자열 파싱 후 정렬하는 문제였습니다. 풀이방법 stl sort함수는 unstable quick sort입니다. 따라서 정해진 기준 외에 놔둬야 하는 문자열들의 서순이 뒤바뀔 수 있습니다. 때문에 stable_sort함수를 사용해 기준이 없는 문자열의 서순을 바꾸지 않도록 한다면 맞을 수 있습니다. 1. Head, Number를 문자열 파싱으로 구합니..

티스토리툴바