본문 바로가기

Algorithm

 (2139)
(MYSQL) - 프로그래머스 (Summer/Winter Coding(2019)) : 우유와 요거트가 담긴 장바구니 https://programmers.co.kr/learn/courses/30/lessons/62284 코딩테스트 연습 - 우유와 요거트가 담긴 장바구니 CART_PRODUCTS 테이블은 장바구니에 담긴 상품 정보를 담은 테이블입니다. CART_PRODUCTS 테이블의 구조는 다음과 같으며, ID, CART_ID, NAME, PRICE는 각각 테이블의 아이디, 장바구니의 아이디, 상품 종류, 가 programmers.co.kr left outer join, group by를 사용하는 문제였습니다. 풀이방법 1. 같은 테이블을 left outer join합니다 2. outer table의 name이 'Yogurt'고 inner table의 name이 'Milk'인 경우거나 outer table의 name이 ..
(C++) - 백준(BOJ) 3055번 : 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net bfs 구현문제였습니다 풀이방법 1. '*'들 즉 물이 있는 위치를 행,열 형태로 queue에 저장합니다. 2. bfs를 통해 물이 어떤 특정 타일에 도착하는 거리들을 모두 구합니다. 3. bfs를 통해 고슴도치가 특정 타일에 도착하는 거리들을 모두 구합니다. 4. 'D'의 위치에서 인접한 상하좌우칸을 확인하며 탈출 가능여부를 판단합니다. 4-1. 탈출 경로가 존재하고 물보다 빨리 'D'의 인접칸에 도착할 수..
(C++) - 백준(BOJ) 1969번 : DNA https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 입력을 모두 받으면 N행 M열의 형태로 문자열들이 저장되게 됩니다. 2. 열 단위로 세로로 보면서 가장 많이 나왔고 그것이 여러개라면 그 중 가장 앞의 알파벳을 찾습니다. 최다 빈도의 알파벳을 출력할 문자열 정답 변수 minWord뒤에 붙여주고 최다 빈도의 알파벳을 제외한 다른 알파벳들의 빈도 수들을 모두 ans변수에 ..
(C++) - 백준(BOJ) 3896번 : 소수 사이 수열 https://www.acmicpc.net/problem/3896 3896번: 소수 사이 수열 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다. www.acmicpc.net 소수 찾기 + 이분탐색문제였습니다 풀이방법 1. 100000번째 소수까지 모두 구해놓습니다. 에라토스테네스의 체 방식을 이용하면 O(루트N)으로 빠르게 구할 수 있습니다. 2. 소수라면 0을 출력, 이분탐색으로 해당 수보다 큰 가장 가까운 소수에 해당하는 인덱스를 찾습니다. 그 후 해당인덱스 - (해당인덱스 - 1)의 값을 출력합니다. Code #include using namespa..
(C++) - 백준(BOJ) 12904번 : A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 반대로 생각해야하는 문자열 처리문제였습니다. 풀이방법 A를 추가하거나 뒤지고 B를 추가하여 t를 만드는데 brute force를 생각할 수 있으나 매번 2배씩 분기되기 때문에 2의 1000(문자열 최대길이)승 정도의 시간복잡도로 시간초과가 납니다. 1. 생각전환 : 반대로 생각하면 풀립니다. t->s로 문자를 만든다고 생각해봅니다. 이를 만드는데는 2가지 조건..
(Python) - 백준(BOJ) 16428번 : A/B - 3 https://www.acmicpc.net/problem/16428 16428번: A/B - 3 첫째 줄에 A와 B가 주어진다. (-1010000 ≤ A, B ≤ 1010000, B ≠ 0) www.acmicpc.net 큰 수에 대해 나눗셈 연산을 구현하는 문제였습니다. 풀이방법 파이썬은 기본적으로 큰 수(long long 범위 초과하는)의 사칙연산을 지원합니다. 두 가지 방법으로 구현하는 법이 있습니다. 1. 그냥 나눠 몫과 나머지를 구하는 방법 : 기본으로 지원해주므로 양수 / 음수인 경우에만 if문으로 처리하는 것 외에 몫을 c, 나머지를 d변수에 저장해 출력합니다. 2. 함수 이용 : divmod(정수1,정수2)함수를 이용하게 되면 정수1을 2로나눈 몫과 나머지가 튜플 형태로 반환됩니다. 이를 이..
(C++) - 백준(BOJ) 15989번 : 1, 2, 3 더하기 4 https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net dp문제였습니다. 풀이방법 특정한 규칙을 수학적으로 찾으면 답을 도출할 수 있습니다. 1111은 22로 교체될 수 있습니다. 222는 33으로 교체될 수 있습니다. 적절히 규칙을 찾으면 점화식을 구할 수 있습니다. Code(Top down, 주석은 bottom up) #include #define ll long long using na..
(C++) - 백준(BOJ) 5427번 : 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 구현 문제였습니다. 풀이방법 매 테스트케이스마다 적절히 입력을 받고 초기화를 한 다음을 시행합니다. 1. 불이 갈 수 있는 지점까지의 거리가 곧 해당 지점이 타는 시간초입니다. 따라서 불이 각 지점에 퍼지는 시간초를 bfs를 시행하며 visitedFire배열에 저장합니다. bfs를 시행하는 도중 만약 다음지점이 빌딩 밖이라면 현재 지점은 탈출할 수 있는 구역이므로 행,열 좌표를 저장하는 구조체 Coor..

티스토리툴바