본문 바로가기

Algorithm/Implementation

 (750)
(C++) - 프로그래머스(월간코드챌린지) : 쿼드압축 후 개수 세기 programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 재귀함수를 구현하는 문제였습니다. 풀이방법 1. 부분 정사각형의 면적이 모두 같은 영역인지 확인합니다. 2. 정사각형의 영역이 모두 같은 수(0,1)로 되어 있다면 압축이 가능합니다. 반대..
(Javascript) - 프로그래머스(2019 카카오 겨울 인턴) : 징검다리 답 programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 구현하는 문제였습니다. 풀이방법 1. 인형을 뽑을 때의 위치(행)를 구한다. 2. 뽑은 인형을 배열에 담고 연속인지 판별해 상태를 갱신한다. 3. 답출력 Code function getDollPos(board,oneMove){ for(let i = 0; i < board[0].length; i++){ if(board[i][oneMove]) return i; } return -1; } function u..
(C++) - 백준(BOJ) 15686번 : 치킨배달 답 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 비트마스킹을 이용해 m개 이하의 치킨집을 연 후 치킨거리를 게산하여 최솟값을 출력하는 문제였습니다. 풀이방법 시간복잡도 : (살릴 치킨집을 고르는 시간) * (다 고른 후 도시의 치킨 거리를 구하는 시간) = (2^m) * n^2 1. n^n의 격자에서 입력 받을 때 집의 좌표와 치킨집의 좌표를 각자 저장합니다. 2. 비트마스킹을 이용해 치킨집이 열려있는 상태를 표시할 수 있습니다. 2-1..
(C++) - 백준(BOJ) 17219번 : 비밀번호 찾기 답 www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번�� www.acmicpc.net map을 이용해 간단히 풀 수 있는 문제였습니다. 풀이방법 1. map에 site주소와 비밀번호를 key,value 쌍으로 저장합니다. 2. n만큼 찾고자하는 site주소를 key로 접근하여 value를 출력해주면 답이 됩니다. Code #include #include #include using namespace std; int main(){ map siteInfo; int m..
(Javascript) - 백준(BOJ) 11005번 : 진법 변환 2 www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 �� www.acmicpc.net 진법을 변환해보는 문제였습니다. 풀이방법 1. parseInt함수로 10진수로 입력된 문자열을 parseInt로 만들어주고 나온 결과를 toString함수에 넣어 b진수로 변환한 결과를 저장합니다. 2. 그 결과의 길이만큼 loop를 돌며 출력하는데 알파벳 소문자에 해당하는 부분이 나오면 toUpperCase함수를 사용해 대문자로 수정해서 출력해줍니다. Code process.stdin.resume(..
(C++) - 백준(BOJ) 11286번 : 절댓값 힙 답 www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0� www.acmicpc.net make_pair를 이용해 priority queue를 사용하는 문제였습니다. 풀이방법 priority queue의 기본 자료구조는(선언시 3번째 인자로 아무것도 설정하지 않거나 less설정을 줬을 때)은 max heap입니다. 이는 priority queue에 들어가는 원소가 pair의 형태를 하고 있어도 같습니다. 따라서 greater로 min heap을 인자로 줌으로써 min hea..
(C++) - 백준(BOJ) 9375번 : 패션왕 신해빈 답 www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 자료구조 map을 이용해 푸는 문제였습니다. map은 key,value가 한 쌍으로 이루어진 자료구조입니다. map header를 추가(#include )해주시면 map이라는 자료구조와 내장함수를 사용할 수 있습니다. map변수이름.내장함수명으로 해당 멤버함수를 사용할 수 있습니다. Member 설명 begin() 첫 ..
(C++) - 백준(BOJ) 17608번 : 막대기 답 www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 간단한 구현 문제였습니다. 풀이방법 오른쪽에서 봤을 때 가장 앞 원소는 오른쪽 끝에 있는 막대기고 이 막대기의 높이만큼 나머지 막대기를 볼 시야를 가리고 있습니다. 따라서 보이는 막대기의 수는 무조건 오른쪽 막대기부터 시작하여 높이를 확인해가면서 왼쪽 막대기를 보고, 오른쪽 막대기보다 왼쪽 막대기가 더 크다면 이 왼쪽 막대기는 보인다고 할 수 있습니다. 그렇다면 오른쪽 막대기부터 시작해 왼쪽 막대기로 순차적으로가며 ..

티스토리툴바