박기완 코딩교육/코딩테스트 대비 썸네일형 리스트형 프로그래머스 더 맵게 문제 풀이 안녕하세요! 오늘은 프로그래머스 문제 더맵게 를 풀었습니다. programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 문제 자체는 heap에 대한 이해만 있다면 충분히 쉽게 풀 수 있는 문제인데요, 전 힙 stl이 익숙하지 않아서 직접 구현했습니다. 1. 우선 스코빌 지수가 가장 작은값이 루트로 와야하므로, 최소힙을 구성했습니다. 2. 최소힙을 만들고, 맨위 원소 2개를 뽑아 계산후, 다시 힙에 삽입. 이 두과정을 .. 더보기 프로그래머스 소수 찾기 문제 안녕하세요! 오늘은 프로그래머스 소수찾기 문제를 풀었습니다. programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 � programmers.co.kr 이 문제는 모든 경우의수를 따지기만해도 충분히 풀 수 있습니다. numbers 길이가 최대 7이고, numbers는 숫자 0~9로 이루어져있기에 최대 가능한 숫자가 9,999,999 입니다. 에라토스테네스의 체를 이용해 소수를 파악하고, numbers 길이가 최대 7이므로 나올 수 있는 모든 숫자 .. 더보기 프로그래머스 단어 변환 문제 안녕하세요! 오늘은 프로그래머스 단어 변환 문제를 풀었습니다. programmers.co.kr/learn/courses/30/lessons/43163# 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 이 문제의 묘미는 주어진 단어들을 이용해 그래프로 만들 수 있냐 였습니다. 단어끼리 변환이 가능하다면 그래프 상에 연결됐다란 처리를 해서, 출발지부터 목적지까지 bfs 탐색을 진행해 최소거리를 찾으면 해결 끝! #include #include #include using .. 더보기 프로그래머스 네트워크 문제 안녕하세요! 오늘은 프로그래머스의 네트워크 문제를 풀었습니다. 전형적인 union find문제기도 했지만, 한편으론 단순히 dfs돌리면서 같은그룹인지 확인할 수 있는 문제였습니다. programmers.co.kr/learn/courses/30/lessons/43162# 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 접근과정으로 1. computers 배열에 들어온 데이터를 갖고 하나씩 순회하면서, 연결관계를 파악했습니다. 2. 두 지점이 연결되있으면 union find를 실행해 하나의 네트워크로 묶.. 더보기 프로그래머스 타겟 넘버 문제 안녕하세요! 오늘은 프로그래머스의 '타겟 넘버'를 풀어보았습니다. programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 단순히 각 숫자를 더하냐 빼냐를 최대 20번 반복하는 형태여서 2의 20승. 최대 백만번 호출로 정답을 찾을 수 있었습니다. 전체탐색 방법으로 반복문을 돌리든, 재귀함수를 돌리든 편한걸 택하면 되는데, 전 재귀함수가 좀더 직관적인거같아 재귀로 구현했습니다. .. 더보기 프로그래머스 가장 먼 노드 문제 안녕하세요! 오늘도 프로그래머스 문제 가장 먼 노드를 풀어보았습니다. 사실 이 문제는 가중치가 없는 그래프에 최단거리 이야기까지 나왔으니 100% bfs를 이용하면 쉽게 풀 수 있습니다. bfs의 특징을 이용하면 한단계 한단계씩 다음 노드로 접근하게될거고, 마지막 접근한 노드들만 쭉 찾아서 갯수세주면 바로 해결! 조금 특이한건 bfs탐색을 위한 발견여부 배열에 해당 점을 발견한 당시 거리값을 저장시켰다는 점입니다. 마지막에 거리 최대값을 가진 애들만 쭉 반복문돌리며 갯수 세는식으로 만들기위해 ㅎㅎ. 그럼 오늘도 파이팅입니다! #include #include #include using namespace std; int solution(int n, vector edge) { //간선이용해 그래프 표현 vec.. 더보기 프로그래머스 입국심사 문제 안녕하세요! 오늘은 프로그래머스 입국심사 문제를 풀어보았습니다. programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 처음에 이문제를 보고 시간 흐름에 따라 반복문 노가다를 하면 되지않을까 싶었습니다. 하지만 입국심사 기다리는 사람수를 10억이라 치고 심사관 1명이라 했을때 문제해결과정으로 1초가 넘어갈게 뻔했습니다. 어떻게하면 좋을까 생각하다가 가능한 시간의 min과 max를 구해서 이진탐색을 돌리면 어떻게든 되지않을까 싶었.. 더보기 프로그래머스 스킬트리 문제 오늘은 프로그래머스 스킬트리 문제를 풀어보았다. programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 처음엔 스킬트리 컨셉이여서 위상정렬 관련된 이야기인가 싶었다. codeup.kr/problem.php?id=3212 위상 정렬(topological sort) 첫째 줄에 정점의 개수 v (2 더보기 프로그래머스 기능개발 문제 오늘은 프로그래머스 기능개발 문제를 풀었습니다. 문제 이해만 된다면, 정말 쉽게 해결가능한 문제였습니다. programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 �� programmers.co.kr 문제풀이 접근과정은 1. 작업당 필요 시간을 계산하고, 2. 누적된 시간보다 필요시간이 같거나 작다면, 이번 배포할 갯수에 추가 3. 누적된 시간보다 필요시간이 크다면, 배포할 갯수를 결과벡터에 담고, 누적된 시간 추가, 배포할 갯수 0으로 초기화후 한개 추가.. 더보기 프로그래머스 주식 가격 문제 오늘은 프로그래머스 주식가격 문제를 풀었습니다. programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr [1차 실수] 처음엔 이문제를 이진탐색 트리를 만들어 풀려고했습니다. prices벡터를 뒤에서부터 앞으로 탐색하면서, 이진탐색트리를 만들고, 당장 들어온 값보다 작은 애를 찾으려했죠. 근데 고려하지못한 부분으로 당장 들어온 값보다 작다면 가장 최근에 추가된 애를 찾아야하는건데, 그저 당장.. 더보기 이전 1 다음
