iyeaaa의 등록된 링크

 iyeaaa로 등록된 네이버 블로그 포스트 수는 34건입니다.

마법의 엘레베이터 - Lv. 2 [내부링크]

코딩테스트 연습 - 마법의 엘리베이터 마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10 c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다. 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지... school.programmers.co.kr DFS로 풀 수 있는 문제다. 더 최적화를 해서 그리디로 O(N)에 풀 수도 있지만, DFS의 풀이로 꽤 간편하고 약간은 신박하게 풀 수 있어 들고왔다. (N: stroey의 자릿수) stroey 를 0으로 변환하기 위해서는 마지막 자리의 숫자를 먼저 처리함으로써 두

증명하기 까다로운 시간복잡도 [내부링크]

for (int i=2; i<=e; i++) for (int j=i; j<=e; j+=i) i를 2부터 e까지 돌리면서 각 i마다 j를 i부터 시작해 i씩 더하며 e까지 수행한다. 각 i마다 e/i번 돌린다고 생각하면 된다. (e는 임의의 양의 정수, 2.71 아님) 수식으로 나타내면 다음과 같다: 조화급수에 e을 곱한 형태를 가지는 식이 된다. 이제 단조증가 함수에 대해서 다음이 성립한다. f(x) = 1/x 라고 하면 f(x)는 1/x 는 단조 증가함수이므로 대입해서 시간복잡도를 구하자. (f(x) = 1/x, n = 2, m = e를 대입) 하한 시간복잡도 : 상한 시간복잡도 : 우리는 보통 상한 시간복잡도를 따지므로 다음과 같이 결론지을 수 있다.

약수 개수 시간복잡도 계산 팁 [내부링크]

for (int i=0; i<f(N); i++) for (int j=0; j<f(N); j++) 이 알고리즘의 정확한 시간복잡도인지는 모르겠다. 하지만, O(root(N)^2) 보다 빠른 속도로 수행함은 보장할 수 있다. 이유를 생각해보자. 우선 약수의 개수를 구해보자. N의 약수를 구할 때, 1부터 root(N)까지 나누면서, N이 나눠진다면, 나누는 수와 그 몫을 저장하면 된다. (두 개씩 저장한다) 즉 약수의 개수는 항상 2 * root(N) 이하의 값을 가진다. 따라서 다음이 성립한다. 이제 2*root(N)을 알고리즘에 대입한다면, 다음이 성립함을 알 수 있다.

S1 그리디 탐욕 대상 [내부링크]

1931 - 회의실 배정 1931번: 회의실 배정 1931번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 회의실 배정 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 156692 49401 34768 29.712% 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 ... acmicpc.net 처음 시작하는 회의부터 '하나씩' 선택해가면서 어떤 회의를 진행할건지 선택한다고 하자 끝나는 시간이 가장 빠른 회의를 고르면 된다. 가장 먼저 시작할 회의를 '1개' 골랐고, 가장 먼저 끝나는 회의를 골랐기 때문에 회의가 가능한 시간이 제일 많아진다.[ 1080 - 행렬 1080

복습예정 문제 [내부링크]

코딩테스트 연습 - 대여 횟수가 많은 자동차들의 월별 대여 횟수 구하기 다음은 어느 자동차 대여 회사의 자동차 대여 기록 정보를 담은 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블입니다. CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블은 아래와 같은 구조로 되어있으며, HISTORY_ID , CAR_ID , START_DATE , END_DATE 는 각각 자동차 대여 기록 ID, 자동차 ID, 대여 시작일, 대여 종료일을 나타냅니다. Column name Type Nullable HISTORY_ID INTEGER FALSE CAR_ID INTEGER FALSE ... school.programmers.co.kr 코딩테스트 연습 - 즐겨찾기가 가장 많은 식당 정보 출력하기 Column name Type Nullable REST_ID VARCHAR(5) FALSE REST_NAME VARCHAR(50) FALSE FOOD_TYPE VARCHAR(

HAVING vs WHERE 차이 정리 [내부링크]

가장 근본적인 차이점을 알아야 한다. WHERE은 SELECT 되기 전에, 조건에 맞지 않는 열을 거른다. HAVING은 SELECT 된 후에, 조건에 맞지 않는 열을 거른다. 거르는 시점에서 HAVING과 WHERE의 또다른 차이점이 생겨난다고 보면 된다. WHERE은 SELECT 전에 열들을 거른다. 이 말은 가장 처음의 어떤 조건도 적용되지 않았을 때의 표에 대해서 거른다는 말이다. 즉 WHERE은 집계함수(AVG, COUNT) 또는 컬럼의 별칭이 포함된 조건을 수행하지 못한다. 그러면 그냥 HAVING을 쓰면 되는거 아닌가 싶지만, HAVING은 SELECT된 후에 거르므로, SELECT된 행에 대해서만 조건을 거를 수 있다.

이분탐색 실수없이 구현하기 [내부링크]

이분 탐색(Binary Search) 헷갈리지 않게 구현하기 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 2021년 9월 28일 jinhan814 댓글 (11개) binary_search , lower_bound , upper_bound 개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo <= hi, lo < hi, lo + 1 < hi 중 어느 걸 선택해야 할 지, 정답이 lo인지 hi인지 (lo + hi) / 2인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 합니다. 이번 ... www.acmicpc.net 위의 방식에서 아이디어를 가져와 정리함.

G5 이분탐색 소재 정리 [내부링크]

3020: 개똥벌레 3020번: 개똥벌레 문제 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림) 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다. 위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가... www.acmicpc.net 그냥 1부터 N까지 모든 장애물을 고려하면 O(NH)고 시간초과다. 석순과 종유석끼리의 순서는 문제에 어떤 영향도 끼치지 않음을 알고 정렬해서 더 편해지면 편해졌지 더 어려워지지 않음은 확실하므로 우선 정렬한 후에 생각해보자. 이제 이분탐색으로 현재 높이보다 '크거나 같은 석순'과

G4 이분탐색 소재 정리 [내부링크]

2110: 공유기 설치 2110번: 공유기 설치 2110번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 공유기 설치 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 53670 18212 12847 36.380% 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x 1 , ..., x N 이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수... www.acmicpc.net

배낭문제 [내부링크]

배낭문제의 일반적인 풀이를 알고있다는 가정 하에 설명함. https://propercoding.tistory.com/50 [알고리즘] 배낭 문제 (Knapsack Problem) 목차 배낭 문제란? 배낭 문제란 담을 수 있는 최대 무게가 정해진 배낭이 있고 각각의 무게와 가치가 주어진 물건들이 주어졌을 때, 배낭에 담은 물건들의 가치가 최대가 되도록 하게 물건을 고르는 방법을 찾는 문제이다. 배낭 문제 예시 4가지의 물건 ABCD가 있고 배낭의 최대 무게는 5라고 가정하겠다. 무게가 1, 가치가 30인 물건을 A; 무게가 2, 가치가 20인 물건을 B; 무게가 3, 가치가 40인 물건을 C; 그리고 무게가 4, 가치가 10인 물건을 D라고 하겠다. 그리고 우리가 가진 가방의 최대 무게는 5이다. 이때 이 가... propercoding.tistory.com 일반적인 배낭문제 점화식 풀이에서 조금 다르게 풀어보려고 한다. ( 두 풀이 모두 많이 쓰인다 ) 출처: https://seun

2D Array DP [내부링크]

일반적인 DFS에서 메모이제이션만 하면 됩니다 1577번: 도로의 개수 문제 세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다. 따라서, 아래 그림과 같이 생겼다. 세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다. 세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 ... www.acmicpc.net 2096번: 내려가기 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된

LCS [내부링크]

9251번: LCS 9251번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 LCS 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.1 초 ( 하단 참고 ) 256 MB 61673 25006 18350 40.195% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알... www.acmicpc.net 5582번: 공통 부분 문자열 5582번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 공통 부분 문자열 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 13921 5595 4376 42.126% 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된

LIS, LDS [내부링크]

2565번: 전깃줄 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. < 그림 1 > 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서... www.acmicpc.net 11054번: 가장 긴 바이토닉 부분 수열 11054번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 가장 긴 바이토닉 부분 수열 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 40289 20542 16066 50.704% 문제 수열 S가 어떤 수 S k

해석의 가짓 수 [내부링크]

2011번: 암호코드 2011번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 암호코드 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 44471 8334 6101 19.842% 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시... www.acmicpc.net 2591번: 숫자카드 문제 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러

ETC [내부링크]

모든 문제에서 점화식 세우는 과정은 필수적이다 2225번: 합분해 2225번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 합분해 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 35507 15701 11501 42.718% 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째... www.acmicpc.net 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8

타일 [내부링크]

2133번: 타일 채우기 2133번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 타일 채우기 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 42408 15160 11981 35.574% 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다. 출처 Contest > Waterlo... www.acmicpc.net

양방향 DP [내부링크]

10942번: 팰린드롬? 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, ... www.acmicpc.net

사이클 [내부링크]

사이클이 생기는 경계에서 CASE를 나누고 관찰한다 17404번: RGB거리 2 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N... www.acmicpc.net 2482번: 색상환 문제 색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져

G5 그리디 탐욕 대상 [내부링크]

11000번: 강의실 배정 11000번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 강의실 배정 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 27028 7942 5836 29.084% 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 S i 에 시작해서 T i 에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, T i ≤ S j 일 경우 i 수업과 j 수업은 같이 들... www.acmicpc.net 1374번: 강의실 1374번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 강의실 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 3344 1405 1108 43.485% 문제 N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다

G4 그리디 탐욕 대상 [내부링크]

카드 정렬하기 - 1715 1715번: 카드 정렬하기 1715번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 카드 정렬하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 40173 13580 10469 33.713% 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶... www.acmicpc.net 파일 합치기 3 - 13975 13975번: 파일 합치기 3 13975번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 파일 합치기 3 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 3719 1777 1452 47.097% 문제

G3 그리디 탐욕 대상 [내부링크]

크게 만들기 - 2812 2812번: 크게 만들기 2812번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 크게 만들기 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 22659 5862 4218 25.833% 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 ... www.acmicpc.net 무조건 앞의 숫자가 커져야한다. 앞에서부터 스택의 마지막 요소보다 큰 숫자들을 K번 제거한다. 과제 - 13904 13904번: 과제 13904번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 과제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초

역방향 그래프 [내부링크]

파티 - 1238 1238번: 파티 1238번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 파티 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 32291 16003 10659 47.693% 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T i (1 ≤ T i ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서... www.acmicpc.net 다익스트라는 어떤 한 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘이다. 이 문제에서는 A. X에서 다른 모든 점들까지의 모든 최단거리와 B. 다른 모든 점에서 X까지의 최단거리를 구해야한다. ( 양방향 그래프가 아니므로 가는길과 오는길의 비용은 다를 수 있다 ) 한번의 다익

좌표계 다익스트라 최적화 [내부링크]

알고스팟 - 1261 1261번: 알고스팟 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)... www.acmicpc.net 내 소스코드의 쓸데없는 부분을 기록하려한다. 좌표계에서 다익스트라를 수행할 때 조금 더 간편할 듯 하다. 어떤 그래프의 노드 중 A, B, C라는 노드가 있다고하자. 어떤 시작점 노드가 있을 때 A까지 이동하는 최단거리를 2라고 하자. B까지 이동하는 최단거리를 3라고 하자. 우

AtCoder Beginner Contest 281 [내부링크]

A - Count Down A - Count Down AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 단순 출력문제 let N = Int(readLine()!)! for i in 0...N { print(N-i) } B - Sandwich Number B - Sandwich Number AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 다음 조건을 만족하면 Yes를 출력하고 아니면 No를 출력한다. 첫째자리가 영어 대문자 두번째 ~ 일곱번째가 100000부터 999999 사이의 수 여덟번째 자리가가 영어 대문자 let

DATABASE 공부 기록 [내부링크]

NULL 일때, 다른 문자 출력하기 - IFNULL(칼럼명, '내용') 날짜만 출력하기 - DATE_FORMAT(칼럼명, '%Y-%m-%d') 문자열 포함 - LIKE '%STRING%', (%는 와일드카드) 평균 - AVG(칼럼) 소수점 - round(소수) = 정수로 반올림, round(소수, 자릿수) = 자릿수만큼 반올림출력 TRUNCATE 함수 - 그냥 블로그 참고 제외 연산자 - <> (!= 와 같다) LIMIT a - 처음부터 a개 출력 LIMIT a b - a+1행부터 b행까지 출력

프로그래머스 LEVEL4 [내부링크]

서울에 위치한 식당 목록 출력하기 - SELECT 코딩테스트 연습 - 서울에 위치한 식당 목록 출력하기 다음은 식당의 정보를 담은 REST_INFO 테이블과 식당의 리뷰 정보를 담은 REST_REVIEW 테이블입니다. REST_INFO 테이블은 다음과 같으며 REST_ID , REST_NAME , FOOD_TYPE , VIEWS , FAVORITES , PARKING_LOT , ADDRESS , TEL 은 식당 ID, 식당 이름, 음식 종류, 조회수, 즐겨찾기수, 주차장 유무, 주소, 전화번호를 의미합니다. Column name Type Nullable REST_ID VARCHAR(5) FALSE REST_NAME VARCHAR(50... school.programmers.co.kr SELECT I.REST_ID, I.REST_NAME, I.FOOD_TYPE, I.FAVORITES, I.ADDRESS, ROUND(AVG(R.REVIEW_SCORE), 2) AS SCORE FROM R

AtCoder Beginner Contest 278 [내부링크]

A - Shift A - Shift AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp K번째 idx부터 N번째까지 출력 한 후 K > N임을 고려해, min(K, N)의 0을 출력한다. queue를 써도 된다. #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> tii; const int MAX = 105; int N, K, A[MAX]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); c

배수판정법 [내부링크]

큰 수를 나눌 때 불편함을 해소하기 위한 배수판정법 컴퓨터에서는 int나 long보다 큰 수를 string으로 다뤄야할 때 종종 쓰인다. 1: 생략 2: 일의자리가 2의 배수 3: 모든 자릿수의 합이 3의 배수 4: 마지막 두 자릿수가 00 or 4의 배수 5: 일의자리가 0 or 5 6: 2의 배수판정 && 3의 배수판정 7: 8: 마지막 자릿수가 000이거나 8의 배수 9: 모든 자릿수의 합이 9의 배수 10: 일의 자리가 0 11: 홀수자리 수의 합 - 짝수자리 수의 합 이 11의 배수

발전 [내부링크]

4948번: 베르트랑 공준 4948번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 베르트랑 공준 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 88497 33819 27135 38.125% 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17,... www.acmicpc.net 10달전 코드이다. import java.io.*; public class Main { public static void main(String [] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR

두 가지 소수 판정법 [내부링크]

PS에서 자주 사용하는 소수 판정법 두 가지를 소개한다. 문제에 따라 두 가지 중 어떤 판정법을 사용할지 결정해야 할지 시간복잡도를 통해 해결해보자 주제 Trial Division 직접 나누는 방식이다. 만약 N을 소수판정 한다고 할 때, 2부터 N-1까지의 모든 숫자로 나눠보며, 만약 한번이라도 나눠진다면 N은 소수가 아니다. 아니라면 소수다. 하지만 2부터 N-1까지 나누는 알고리즘은 사용할 필요가 없다. N이 100일 때, 20으로 나누는 상황을 생각해보자. 100 / 20 = 5 이다. 하지만 100은이전에 5로 나눔으로써, 100은 20으로 나눠짐이 확인되었으므로 굳이 나눌 필요가 없다. 때문에 sqrt(N), 즉 루트 N 까지만 나눠보면 된다. 2부터 sqrt(N)까지 1씩 증가하며 나누므로, 시간복잡도는 O(sqrt(N)) 이 된다. Sieve of Eratosthenes 에라토스테네스의 체다. 내가 아무리 설명해도 나무위키 보다 잘 설명할 자신이 없으므로, 나무위키를

미룬 공부 [내부링크]

11051번: 이항 계수 2 11051번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 이항 계수 2 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 49871 18496 14553 37.584% 문제 자연수 N \(N\) 과 정수 K \(K\) 가 주어졌을 때 이항 계수 ( N K ) \(\binom{N}{K}\) 를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N \(N\) 과 K \(K\) 가 주어진다. (1 ≤ N \(N\) ≤ 1,000, 0 ≤ K \(K\) ≤ N \(N\)... www.acmicpc.net #include <cstdio> int main(void) { int N,K,P=1,C=1,i=0; scanf("%d %d",&N,&K); while (K--) { C=(C*(N-i))%10007; P=(P*(i+1))%10007; i++; } while (C%P!=0) C+=10007; pr

BOJ 공약수 - 2436 [내부링크]

2436번: 공약수 2436번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 공약수 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 11554 3496 2523 29.872% 문제 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다. 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의... www.acmicpc.net 초등학생 수준의 수학으로 해결할 수 있는 문제다.(유클리드 호제법 제외) 최소공배수를 L, 최대공약수를 G라고 하자. 초등학생 때 저런식으로 G와 L을 구했던 기억이 있을것이다. A와 B를 나눌 수 있을 때까지 계속 나누고 나눈 수들의 곱을 G라고 하고 G x a x b = L 로 구할 수 있었다. G로

거의 소수 - 1456. 시간복잡도 [내부링크]

1456번: 거의 소수 1456번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 거의 소수 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 7358 1810 1232 23.674% 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다. 제한 1 ≤ A ... www.acmicpc.net 문제에 대한 풀이는 대부분 비슷한것 같으니, 따로 서술하지 않겠다. 처음에 sqrt(B)까지 Sieve of eratosthenes 알고리즘을 돌린다. 돌린 후, 1부터 sqrt(B)까지 순회를 돌리며 소수만 고려해준다. 어떤 분의 말에 의하면 1부터 B까지의 소수 개수는 대충 sqrt(B)개로 생

2023 KAKAO BLIND RECRUITMENT [내부링크]

시간복잡도, 중요포인트, 실수할만한 부분 위주로 설명하겠습니다. 개인정보 수집 유효기간 - LV. 1, 구현 코딩테스트 연습 - 개인정보 수집 유효기간 고객의 약관 동의를 얻어서 수집된 1~ n 번으로 분류되는 개인정보 n 개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다. 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야... school.programmers.co.kr 해설 보편적인 날짜 계산문제입니다. 여러 풀이를 봤지만 가장 쉬워보이는 풀이는 날짜를 모두 day로 변환해 비교함이 가장 편해보입니다. 또한 각 알바펫 별