본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 4388번 : 받아올림 답 www.acmicpc.net/problem/4388 4388번: 받아올림 어린이에게 여러자리 숫자의 덧셈을 가르칠 때는 오른쪽 자리부터 왼쪽으로 하나씩 계산하는 방법을 가르쳐준다. 이때, 받아올림이 발생하게 되며 아이들은 여기서 혼란에 빠진다. 받아올림이 www.acmicpc.net 문자열을 적절히 처리하는 문제였습니다. 풀이방법 가장 긴 자리 수를 기준으로 일의자리부터 왼쪽으로 거슬러 올라가는 식으로 더해보고 비교해줍니다. 이 때 짧은 자리를 가진 수가 overflow가 나면 안됩니다. 1. 현재 자리 수가 짧은 자리 수에게도 있는 경우 a의 현재 자리 수 + b의 현재 자리 + 받아올림 여부(cnt) >= 10이라면 carry++, cnt = 1; else cnt = 0으로 초기화 2. 아닌 경우 a..
(C++) - 백준(BOJ) 1225번 : 이상한 곱셉 답 www.acmicpc.net/problem/1225 1225번: 이상한 곱셈 첫째 줄에 A와 B가 주어진다. 주어지는 두 수는 모두 10,000자리를 넘지 않는다. www.acmicpc.net 문자열 다루는 문제였습니다. 풀이방법 정답 변수에 O(N^2)의 시간복잡도로 모든 조합을 곱한 뒤 더해주면 됩니다. 1만자리까지 곱의 결과를 더하므로 int범위를 초과할 수 있기 때문에 ans의 자료형을 long long으로 해주시면 됩니다. 예를 들어 a,b string이 1만자리라면 나올 수 있는 경우의 수가 1만 * 1만 = 1억개가 됩니다. 따라서 a = "9999999..." b = "9999999..." 식으로 되어 있다면 81 * 1억 81억이 되므로 int범위인 21억을 초과합니다. Code #inc..
(C++) - 프로그래머스(고득점 kit - 스택/큐) : 프린터 답 programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 우선순위 큐와 큐를 사용해 푼 문제였습니다. 풀이방법 1. 우선순위 큐와 큐에 우선순위 정보를 push합니다. 2. 우선순위가 같다면 프린트 하고, 문서번호까지 같으면 정답입니다. Code #include using namespace std; int solution(vector priorities, int location) { int answer = 0, cnt = 0; queu..
(C++) - 백준(BOJ) 1063번 : 킹 답 www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 꼼꼼하게 구현해야하는 문제였습니다. 풀이방법 1. 먼저 움직였을 때 예상되는 킹의 row와 column을 먼저 구해줍니다. 그 후 킹을 이동해도 체스판 안인지, 유효한 이동인지 확인합니다. 아니라면 continue; 2. 다음으로는 돌과 킹을 움직인 후의 위치가 같은지를 확인합니다. 만약 같다면 해당 돌을 이동 시켰을 때 유효한지 확인합니다. 유효하지 않다면 conitnue; 유효하다면 돌을 이동 시킨 후 해당 위치로 돌..
(C++) - 백준(BOJ) 2346번 : 풍선 터뜨리기 답 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 간단한 dp문제였습니다. 풀이방법 1. 00타일 : 길이 2 1타일 : 길이 1 인 정보를 가지고 있습니다. 길이[i-1]인 타일을 만들 수 있는 경우의 수 = 다음에 1타일을 연결하면 길이 i가 됩니다. => 1타일사용 길이[i-2]인 타일을 만들 수 있는 경우의 수 = 다음에 00타일을 연결하면 길이 i가 됩니다. => 00타일사용 따라서 길이 i인 타일을 만들 수 있는 경우의 수 = 길이[i-1]인 타일을 만들..
(C++) - 프로그래머스(고득점 kit - Hash) : 베스트앨범 답 programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr map과 vector를 이용해 풀었던 문제입니다. 풀이방법 1. record맵을 선언해 한 장르에 해당하는 vector {플레이 수,index} 부분을 push해 줍니다. 2. 각 장르별 곡들의 총합 플레이 수를 구해 map변수 played에 저장합니다. 3. played가 각 장르별을 key로 하여 해당 장르의 총 플레이 수를 구했으므로 이번에는 totalPlayed ma..
(C++) - 프로그래머스(고득점 kit - Hash) : 위장 답 programmers.co.kr/learn/courses/30/lessons/42578?language=cpp 코딩테스트 연습 - 위장 programmers.co.kr map을 사용해 풀 수 있었던 문제였습니다. 풀이방법 1. 각 카테고리 별로 '입지 않음'라는 의상을 추가해 생각해봅니다. 2. 각 카테고리 당 의상 수 + '입지 않음' 만큼을 answer에 곱해줍니다. 이렇게 된다면 최소 의상을 1개 입는 경우도 ['입지 않음','안경'] 이런 식으로 표현될 수 있으므로 모든 경우를 구할 수 있습니다. 3. 모든 경우의 수 - 모두 '입지 않음'인 경우(1가지)가 답이 됩니다. Code #include using namespace std; int solution(vector clothes) { int ..
(SQL) - 프로그래머스(SQL 고득점 kit - SELECT) : 모든 레코드 조회하기 답 programmers.co.kr/learn/courses/30/lessons/59034 코딩테스트 연습 - 모든 레코드 조회하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 간단한 조회문(select)을 사용해보는 문제였습니다. 📕 풀이방법 📔 정답출력 ANIMAL_ID column을 오름차순으로 정렬하고 테이블의 모든 행을 보여주면 됩니다. 📕 Code Oracle, MySQL 공통 SELECT * from ANIMAL_INS OR..

티스토리툴바