이것이 코딩테스트다 | 이진탐색 기출문제
이것이 코딩테스트다 | 이진 탐색 기출문제
이것이 코딩테스트다 | 이진 탐색 기출문제
💥 문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타...
😥 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출...
🙂 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들...
링크 : https://www.acmicpc.net/problem/18405 🌐 문제 NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해...
링크 : https://www.acmicpc.net/problem/11651 🎈 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. ✨ 풀이
링크 : https://www.acmicpc.net/problem/10814 🛒 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 👓 풀이
링크 : https://www.acmicpc.net/problem/2751 🥨 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 🌭 풀이 그냥 list.sort()만 하면 되는데 왜 실버 레벨 5인지 모르겠다.. 채점 시간은 또 왜 이렇게 많이 걸리지..?
링크 : https://www.acmicpc.net/problem/10989 🍕 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 🍔 풀이 메모리를 적게 잡아먹는 알고리즘을 구현해야했다..! 단순히 sort()를 사용하면 메모리 초과 발생!
링크 : https://www.acmicpc.net/problem/11652 🚗 문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이...
링크 : https://www.acmicpc.net/problem/1377 🤔 문제 버블 소트 알고리즘을 다음과 같이 C++로 작성했다. 위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다. 위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자. 🤨 풀이 시간 초과
링크 : https://www.acmicpc.net/problem/16916 😃 문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열...
링크 : https://www.acmicpc.net/problem/16935 런타임 에러 지옥... 풀이 런타임 에러 다른 풀이 - 런타임 에러
링크 : https://www.acmicpc.net/problem/2558 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 풀이
링크 : https://www.acmicpc.net/problem/10872 문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 풀이
링크 : https://www.acmicpc.net/problem/2441 문제 첫째 줄에는 별 N개, 둘째 줄에는 별 N-1개, ..., N번째 줄에는 별 1개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. 풀이
링크 : https://www.acmicpc.net/problem/10757 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 풀이
링크 : https://www.acmicpc.net/problem/1193 문제 풀이
링크 : https://www.acmicpc.net/problem/2775 문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 ...
링크 : https://www.acmicpc.net/problem/1978 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 풀이 array라는 리스트를 만들고, 그 곳에 소수를 판별할 수를 넣었다. 소수면 cnt에 +1을 했고, 소수가 아니면 +1을 하지 않았다. 소수 판별은 2부터 루트(x)+1까지를 나눠보며...
링크 : https://www.acmicpc.net/problem/2581 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8...
링크 : https://www.acmicpc.net/problem/11653 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 풀이 첫번째 도전 : 시간초과 n의 소수를 구하고 그 소수 중 나누어 떨어지는 걸 찾음 두번째 도전 : 시간 너무 오래 걸림 세번째 도전 : 남이 쓴 코드 외워버림
링크 : https://www.acmicpc.net/problem/1929 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 풀이 첫번째 시도 : 통과는 했지만 너무 오래 걸림 두번째 시도 : 에라토스테네스 체 활용 에라토스테네스 체란 쉽게 말하면 루트n보다 작은 소수들의 배수를 체로
링크 : https://www.acmicpc.net/problem/9020 문제 풀이 첫번째 풀이 : 시간 초과 n보다 작은 소수를 찾은 뒤 더해서 n이 되고, 둘의 차가 작은 걸 뽑았다.. 차이가 작은 소수를 뽑을 때를 좀 더 간단히 해보자. 두번째 풀이 에라토스테네스의 체 응용
링크 : https://www.acmicpc.net/problem/1085 문제 풀이
링크 : https://www.acmicpc.net/problem/3009 문제 풀이 세 점 중 중간에 있는 점을 구하려고 코드가 엄청 길어졌었다. 그런데 직관력이 좋은 사람들은 예제를 보면 코드를 쉽게 구현할 수 있을 것이다. x좌표 세 개 중 count했을 때 하나만 나오는 것이 x좌표의 답이고, y좌표 세 개 중 count했을 때 하나만 나오는 ...
링크 : https://www.acmicpc.net/problem/4153 문제 풀이 처음에 혹~시나 입력이 순서대로 주어지지 않을까라는 도둑놈 마인드를 가지고 풀었다. 역시나 바로 틀렸다 ㅎㅎㅎ 두번째 풀때는 리스트 안에 각 숫자를 넣고 sort 시켜서 풀었당
링크 : https://www.acmicpc.net/problem/3053 문제 풀이 원의 넓이는 다 아시다시피 π$r^2$ 이고, 택시 기하학은 r을 반지름으로 하는 삼각형 4개의 넓이를 구하면 된다.
링크 : https://www.acmicpc.net/problem/1002 문제 풀이 문제 이해하는데 한참 걸렸다.. 알고보니 스타크래프트 게임 얘기였다..ㅎ 결국 문제는 두 원의 교점이 몇개냐?를 묻는 문제다. 처음 풀 때 내접하는 원을 생각을 못해서 한참 헤맸다.
링크 : https://codeup.kr/problem.php?id=1901 문제 1부터 정수 n까지 출력하는 재귀함수를 설계하시오. 이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다. 풀이 왜이렇게 재귀 문제가 어려운지 모르겠다ㅠㅠ
링크 : https://codeup.kr/problem.php?id=1902 문제 정수 n부터 1까지 출력하는 재귀함수를 설계하시오. 이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다. 풀이
링크 : https://codeup.kr/problem.php?id=1904 문제 시작수(a)와 마지막 수(b)가 입력되면 a부터 b까지의 모든 홀수를 출력하시오. 이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다. 풀이 첫번째 풀이 a가 b보다 크면 멈추고, a가 짝수면 a+1로 함수를 다시 호출한다. a가 b보다 작고 홀수라면...
링크 : https://codeup.kr/problem.php?id=1905 문제 정수 n이 입력으로 들어오면 1부터 n까지의 합을 구하시오. 이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다. 풀이 파이썬 최대 재귀 횟수는 1000번까지만 가능하기 때문에 sys.setrecursionlimit(Limit_number)을 쓰지 않으면 ...
링크 : https://codeup.kr/problem.php?id=1912 문제 팩토리얼(!)은 다음과 같이 정의된다. n!=n×(n−1)×(n−2)×⋯×2×1 즉, 5!=5×4×3×2×1=120 이다. n이 입력되면 n!의 값을 출력하시오. 이 문제는 반복문 for, while 등을 이용하여 풀 수 없습니다. 풀이
링크 : https://codeup.kr/problem.php?id=1915 문제 피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다. 첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다. 1, 1, 2, 3, 5, 8, 13 … 자연수 N을 입력받아 N번째 피...
링크 : https://codeup.kr/problem.php?id=1916 문제 피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다. 첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다. 1,1,2,3,5,8,13… 자연수 N을 입력받아 N번째 피보나치 수를 출...
링크 : https://codeup.kr/problem.php?id=1920 문제 어떤 10진수 n이 주어지면 2진수로 변환해서 출력하시오. 예) 10 -----> 1010 0 -----> 0 1 -----> 1 2 -----> 10 1024 -----> 10000000000 이 문제는 반복문을 이용하여 풀...
문제 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획...
문제 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안...
문제 행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다 수평으...
링크 : https://www.acmicpc.net/problem/2798 문제 풀이
링크 : https://www.acmicpc.net/problem/2231 문제 풀이 첫번째 풀이 : 1부터 n까지 부분합을 모두 찾았다 두번째 풀이 : 이진탐색 이용 -> 제일 작은 값을 어떻게 찾을지 고민해보자
링크 : https://www.acmicpc.net/problem/7568 문제 풀이
) 브루트 포스 brute : 무식한, force : 힘. 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색해 해를 찾는다. 브루트 포스의 가장 흔한 문제점은 숫자가 커질수록 시간복잡도가 엄청나게 늘어나는 것이다. 브루트 포스 종류 자료의 구조에 따라서 브루트 포스는 2종류로 나뉘게 되는데, 선형구조 : ...
링크 : https://www.acmicpc.net/problem/1436 문제 풀이 영화 제목을 1씩 늘리며 영화 제목에 '666'이 나오면 n을 -1을 한다.
링크 : https://www.acmicpc.net/problem/2750 문제 풀이 .sort를 이용해서 풀었다
링크 : 문제 풀이
링크 : https://www.acmicpc.net/problem/10989 문제 풀이 내장함수 .sort()보다 빠른건 배열 생성이다!
링크 : https://www.acmicpc.net/problem/2108 문제 풀이 최빈값에서 많이 애먹었다.. collections.Counter를 쓰지 않고 해결해보려고 했지만 실패! `collections.Counter(arra
링크 : https://www.acmicpc.net/problem/1427 문제 풀이
링크 : https://www.acmicpc.net/problem/11650 문제 풀이
링크 : https://www.acmicpc.net/problem/11651 문제 풀이 sort(key = lambda x : ) 암기하자!!
링크 : https://www.acmicpc.net/problem/1181 문제 풀이
링크 : https://www.acmicpc.net/problem/10814 문제 풀이
링크 : https://programmers.co.kr/learn/courses/30/lessons/12917 문제 풀이 첫번째 풀이 : 아스키 코드로 변환 .sort()가 안되길래 아스키
링크 : https://programmers.co.kr/learn/courses/30/lessons/12910 문제 풀이
링크 : https://programmers.co.kr/learn/courses/30/lessons/12918 문제 풀이 isdigit()을 is_digit()으로 착각해서 풀고, 안풀려서 당황했다 isdigit() 기억하자!
링크 : https://programmers.co.kr/learn/courses/30/lessons/12916 문제 풀이
좌표 압축