본문 바로가기

취업과 기본기 튼튼

 (76)
[BOJ] 적록색맹 문제 적록색약 (https://www.acmicpc.net/problem/10026) 풀이 1. 초기접근 문제 조건 해석 n
[프로그래머스] 거스름돈 문제거스름돈 (https://programmers.co.kr/learn/courses/30/lessons/12907) 풀이1. 초기접근문제 조건 해석n은 100,000 이하의 자연수입니다. 화폐 단위는 100종류 이하입니다. -> O(nm) 안에 풀어야함.문제 조건의 변수로, 다음이 주어짐.거슬러 줘야 하는 금액 n돈의 종류 money거슬러줘야하는 금액 n과 돈의 종류에 따른 경우의 수를 고려해야 하므로, 두 가지를 고려한 2차원 dp를 생각할 수 있음.2차원 dpd[j][i] = (money[0] 부터 money[j] 의 화폐를 가지고 i원을 낼 수 있는 방법의 수) 라고 하면, 목표하는 정답은 d[money.size()-1][n] 가 됨.먼저 어떤 화폐를 쓰던, 0원을 거슬러주는 방법의 수는 1이므로..
[프로그래머스] 보행자천국 문제여행경로 (https://programmers.co.kr/learn/courses/30/lessons/1832) 풀이1. 초기 접근문제 조건 해석city_map[i][j]의 상태(0, 1, 2) 에 따라 다음 경로를 처리해야함. -> dp? or dfs?주어지는 맵 크기 1 = m || y >= n ) return 0; if (city_map[x][y] == 0) { return go(x+1, y, m, n, DOWN, city_map) + go(x, y+1, m, n, RIGHT, city_map) % MOD; } else if (city_map[x][y] == 2) { if (d == DOWN) return go(x+1, y, m, n, DOWN, city_map) % MOD; else if (d..
[프로그래머스] 등굣길 문제 등굣길 (https://programmers.co.kr/learn/courses/30/lessons/42898) 풀이 1. 초기 접근 문제 조건 해석 m x n 격자 map이 등장한다. -> 이차원 배열 사용해야한다. m, n은 1 이상 100 이하인 자연수-> O(n^2) 으로 풀린다. 다만 효율성 테스트가 있으므로, 그 중에서도 가장 퍼포먼스가 좋은 알고리즘을 선택해야한다. 물에 잠긴 지역은 0개 이상 10개 이하입니다. -> 물 웅덩이 인지 아닌지 탐색하는 시간은 O(상수) 효율성 테스트 이러한 문제를 푸는 것은 재귀 나 DP가 있다. 효율적인 것을 고려한다면, 함수 호출이 적고 스택에 메모리 쌓아가는 부담이 없는 DP가 훨씬 좋다. 또한 1000000007로 나눠줘야함을 잊지 말자. 코드 #..
[프로그래머스] 베스트앨범 문제 베스트 앨범 (https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3#) 풀이 1. 초기 접근 문제 조건 해석 속한 노래가 많이 재생된 장르를 먼저 수록합니다 -> 장르별로 먼저 묶어서 정렬해야 한다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. -> 장르 내에서도 정렬해야 한다. 코드 (python) from operator import itemgetter def solution(genres, plays): answer = [] d = {} # make set according to genre. for i in range(0, len(genres)) : if genres[i] not in d : d[genres[i]..
[프로그래머스] 이중우선순위큐 문제이중우선순위큐 (https://programmers.co.kr/learn/courses/30/lessons/42628) 풀이1. 초기 접근문제 조건 해석입력 문자열의 형태 "I 16", "D 1" -> 문자열 파싱해야한다.주어지는 operation 길이 n이 1 이상 1000000 미만 -> 최대 O(n log n) 으로 해결해야함.최소, 최대 값을 뽑아내야 한다. -> 정렬 작업이 필요하다.코드#include #include #include #include ​ using namespace std; ​ vector solution(vector operations) { multiset ms; stringstream ss; int n = operations.size(); for (int i=0 ; i> ..
[프로그래머스] 여행경로 문제 여행경로 (https://programmers.co.kr/learn/courses/30/lessons/43164) 풀이 1. 초기 접근 문제 조건 해석 연속된 경로 출력 -> DFS 문제다. 주어지는 공항 수 n이 3 이상 10000 미만 -> O(n^2) 으로 해결가능하다. 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로가 정답 -> 정렬 작업이 필요하다. 코드 #include #include #include #include using namespace std; void dfs(string from, vector& tickets, vector& visit, vector& answer) { answer.push_back(from); for (int i=0 ; i2 1->3 3->1 위 ..
내 이력 하나씩 정리해보기 1. Data driven map 웹 어플리케이션 개발 기술 스택 : Mapbox GL JS, html5, css3, Flask, PostGIS, Navermap API 기간 : 2017. 12 ~ 2018. 01 주차장 정보 제공 및 공유 어플리케이션을 운영하는 ‘모두의 주차장’이라는 회사에서 방학 한 달 동안 3명이 한 팀이 되어 진행한 프로젝트였습니다. NSDI(국가공간정보포털)와 국토해양부에 오픈된 공공 데이터를 가지고, 서울에 있는 모든 주차장 데이터와 건물 데이터를 연결하여 데이터 간의 지리적 연관성을 분석할 수 있게 3D 데이터맵을 만드는 것이 목표였습니다. 이후, Carto 와 같은 웹 어플리케이션에 영감을 받아, 유저가 직접 다양한 데이터를 올릴 수 있도록 하고 레이어 층을 만들 수 있게..

티스토리툴바