본문 바로가기

취업과 기본기 튼튼/코딩 테스트 노트

 (37)
[프로그래머스] 보행자천국 문제여행경로 (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 위 ..

티스토리툴바