본문 바로가기

algorithm

 (135)
백준 1713_후보 추천하기(C++) www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 � www.acmicpc.net [문제 풀이] 단순 구현을 통해 문제를 해결했습니다. 이 문제의 경우 스케줄러를 구현하는 것과 비슷한 형태였습니다. 문제를 해결하기 위해 사진틀을 map을 통해 구현하였습니다. N(사진틀)의 범위가 20 이하이므로 추천 횟수 하나마다 map을 순회하는 형식으로 구현하였습니다. [코드] #include #include using namespace std; map LRU; int N, M; int main(..
백준 1920_수 찾기(C++) www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net [문제 풀이] 이분 탐색을 이용하여 풀었습니다. 이 문제의 경우 정렬이 되어있지 않으면 완전 탐색을 이용해야 합니다. 하지만 완전 탐색을 이용한다면 시간 초과가 날 것이라 생각하였기 때문에 정렬을 해주고 이분 탐색을 이용하여 문제를 풀어주었습니다. 아래 링크를 들어가시면 이분 탐색에 대한 자세한 내용을 정리해 두었습니다. steady-life.tistory.com/5..
백준 10942_팰린드롬?(C++) https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [문제 풀이] DP를 이용하여 문제를 해결했습니다. 이 문제의 경우 완전탐색으로 풀 경우 0.5초의 시간을 넘어가기 때문에 DP를 이용하였습니다. 세 가지의 경우로 나눠서 dp배열에 메모제이션 해주었습니다. 첫 번째 경우 문자열의 길이가 1인 경우 항상 팰린드롬은 성립하므로 dp[i][i] = 1로 메모제이션 해주었습니다. 두 번째 경우 문자열의 길이가 2인 경우 앞뒤 문자가 같은지 판별하여 같은 경우 dp[i][i+1] = 1로 메모..
이분 탐색 이분 탐색 이분 탐색은 탐색 기법의 하나입니다. 탐색 범위를 두 부분으로 분할 하며 탐색한다 하여 이분 탐색이라고 이름 지어졌습니다. 이분 탐색의 핵심은 왼쪽 경계, 오른쪽 경계, 가운데를 어떻게 두느냐가 핵심입니다. 설명의 편의를 위해 left(=왼쪽 경계) , right(=오른쪽 경계) , mid(=가운데) 라고 하겠습니다. 탐색 방법은 아래와 같습니다. 1. left 값을 탐색 범위의 최소 인덱스로 지정합니다. 2. right 값을 탐색 범위의 최대 인덱스로 지정합니다. 3. mid의 값을 (left + right)/2로 지정합니다. 4. 찾으려는 값이 mid와 같은지 비교해줍니다. (같을 시 반복 종료) 5. 찾으려는 값이 mid보다 높다면 left = mid + 1로 초기화한 후 1 ~ 4의 s..
백준 14889_랜선 자르기(C++) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [문제 풀이] 이 문제를 풀기에 앞서 이분 탐색에 대한 정확한 이해를 하시고 푸는 것을 권장해 드립니다. https://steady-life.tistory.com/57 이분 탐색 이분 탐색 이분 탐색은 탐색 기법의 하나입니다. 탐색 범위를 두 부분으로 분할 하며 탐색한다 하여 이분 탐색이라고 이름 지어졌습니다. 이분 탐색의 핵심은 왼쪽 경계, 오른쪽 경계, 가운데를 s..
프로그래머스_DATETIME에서 DATE로 형 변환(MySQL) https://programmers.co.kr/learn/courses/30/lessons/59414 코딩테스트 연습 - DATETIME에서 DATE로 형 변환 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [코드] select ANIMAL_ID, NAME, date_format(DATETIME, '%Y-%m-%d') from ANIMAL_INS order by ANIMAL_ID; -- date_format(DATETIME, '%Y-%..
프로그래머스_오랜 기간 보호한 동물(2)(MySQL) https://programmers.co.kr/learn/courses/30/lessons/59411 코딩테스트 연습 - 오랜 기간 보호한 동물(2) ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [코드] select O.ANIMAL_ID as ANIMAL_ID, O.NAME as NAME from ANIMAL_INS I, ANIMAL_OUTS O where I.ANIMAL_ID = O.ANIMAL_ID order by I.DATETI..
프로그래머스_중성화 여부 파악하기(MySQL) https://programmers.co.kr/learn/courses/30/lessons/59409 코딩테스트 연습 - 중성화 여부 파악하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [코드] select ANIMAL_ID, NAME, case when SEX_UPON_INTAKE like '%Neutered%' or SEX_UPON_INTAKE like '%Spayed%' then 'O' else 'X' end 중성화 from ..

티스토리툴바