코딩테스트/C++ 문제풀이
[백준] 수 정렬하기 2
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 100만개 이하의 숫자를 입력 받아서 sorting해서 출력하면 되는 문제입니다. 사실 c++ 에서의 algorithm에서는 자동으로 최악의 pivot 설정을 피하면서 퀵정렬을 해주는 sort() 함수를 제공합니다. 이 함수를 이용해서 구현하면 됩니다. #include #include using namespace std; int numArray[1000..
[백준] 스도미노쿠
https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 우선 문제부터 요약하면, 스도미노쿠라는 게임을 풀어야하는 문제입니다. 초기상태가 주어지면, 해당 게임을 모두 푼 결과를 출력해야 합니다. https://life318.tistory.com/211 [백준] 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재..
[백준] N-Queen
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 우선 문제부터 요약하면, NxN의 체스판에 Queen을 놓는 경우의 수를 구하는 문제입니다. 이전에 python으로 두 번 해결한 적이 있습니다. https://life318.tistory.com/91 [백준] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이..
[leetcode] Rotate List
https://leetcode.com/problems/rotate-list/ Rotate List - LeetCode Can you solve this real interview question? Rotate List - Given the head of a linked list, rotate the list to the right by k places. Example 1: [https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg] Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1 leetcode.com 우선 문제부터 간단하게 요약하면, single linked list를 k회 회전 시켰을 때의 head를 출력해야 하는 ..
[leetcode] Add Binary
https://leetcode.com/problems/add-binary/ Add Binary - LeetCode Can you solve this real interview question? Add Binary - Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: "10101" Constraints: * leetcode.com 우선 문제부터 간단하게 요약하면, 두 string으로 이진법 숫자가 두개 주어지면, 해당 숫자를 더한 string을 return..
[백준] 리모컨
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 100번 채널에서 특정 채널로 리모컨을 이용해서 이동하려 할 때, 숫자 버튼들이 고장날 수 있습니다. 이 때, 총 몇번의 최소 횟수를 눌러야 이동이 가능한 지를 구해야 하는 문제입니다. (+와 -버튼은 고장나지 않습니다.) 우선 두가지 종류의 경우가 있습니다. 1. 그냥 +와 -버튼으로 100번채널에서 원하는 채널으로 이동하는 방식과, 2. 채널을..
[백준] Z
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 문제속의 그림처럼 Z모양을 순회하게 될 때, r,c가 지목되었을 때 몇번째로 해당 칸이 조회되는지를 구해야 하는 문제입니다. 규칙을 찾아서 문제를 해결할 수 있는데, 항상 문제는 다음과 같은 모양의 영역으로 나누어집니다. 해당 영역이 더 커지게 되면, 다음과 같이 형광색으로 칠해진 영역처럼 1,2,3,4 구역을 더 큰 관점에서도 볼 수 있습니다. 여기에서..
[백준] 좌표 압축
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 우선 문제부터 요약해보면, 주어진 좌표들 각각에 대해 총 좌표중 본인보다 작은 것들의 갯수를 출력해야 하는 문제입니다. 이 문제에서 생각 해야 하는 부분들은, 1. 중복된 값이 등장하는 경우에는 하나로 카운팅 해야한다 2. 숫자들이 총 1,000,000개 등장이 가능하기에, 매 숫자마다 전체를 탐색하면 시간초과가 된다 이렇게 두가지입니다. 그래서 ..