IT
[프로그래머스] 구명보트
오늘 리뷰할 문제는 구명보트이다. 대표적인 그리디 기출문제인데, 대부분 그리디는 정렬을 먼저 하고 시작하게 된다.1. 문제 해설무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모..
블로그 이전(velog -> tistory)
벨로그를 티스토리로 이전하기로 결정했다. 취준생때 개설해놓고 티스토리는 잘 쓰지 않았는데, 벨로그 보다는 티스토리가 장기적으로블로그를 운영하는데에 적절하다고 생각이 들었다. 데일리 로그나 여행 게시글도 막 포스팅 하고싶은데 벨로그와는 분위기가 맞지 않다. ㅋㅋㅋㅋ 그래서 게시글을 하나씩 이전중인데, 쉽지않다. 완전 노가다 작업이다... 하지만 소중한 블로그를 업그레이드 하기 위해 하나씩 옮기는 주 이다. https://velog.io/@munang munang (Munang) / 작성글 - velog velog.io 도메인도 새로 만들었다. 이전에 공부하려고 가비아에서 도메인을 구매해놓고 쓰지를 않았다. ㅋㅋㅋㅋ 그래서 티스토리와 연결했다. 벨로그는 이것도 아직 지원하지 않는다. 약간의 감성이 부족하단..
![[프로그래머스] 게임 맵 최단거리](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc0g8p0%2FbtsIULETkUD%2Fmue9Gj0hzQYgy1UNXY9LD1%2Fimg.png)
[프로그래머스] 게임 맵 최단거리
이 문제는 전형적인 BFS문제이다. BFS로 푸는건 맞는데 내가 BFS를 모른다는 생각이 들었다. 왜냐면 문제에서 최소 거리를 구하라고 했는데, BFS 자체가 왔던 길을 다시 되돌아 가지 않기 때문에 최소 거리가 보장된다는 것이다.1. 문제 해설이러한 지도가 있다고 하면, 다음과 같은 경로가 있을 수 있다. 이때 하단의 경로 중에서 첫 번째 경로가 가장 최소의 경로가 된다.이때 지나가는 경로의 가중치를 모두 1이라고 한다면 최소 가중치의 합을 구하면 된다.2. 어려웠던 점1) 최소길이를 BFS로BFS는 완전탐색의 일종인데, 내가 생각했던 BFS는 큐에 해당 점을 넣고 인접한 모든 점을 탐색한다. 그래서 최소가 아니라고 생각이 들었다.위의 그림에서 첫 번째 예시와 두 번째 예시는 다르게 카운팅 되기때문에 ..
[개념 정리] 파이썬 set
파이썬에서 사용하는 자료구조 set에 대해 알아볼 것이다. 매번 set자료구조를 사용하는 일은 많은데, 효율성 있게 활용해야 하고 기억해두고 싶어서 포스팅 한다. 1. Set파이썬에서 set은 집합 자료형으로 사용된다. 주된 특징으로는 순서를 보장하지 않고, 중복된 원소를 포함하지 않는다. 특징으로 유추하면 set은 해시테이블로 구현되어 있음을 생각해볼 수 있다. 순서를 보장하지 않는다.중복된 원소를 포함하지 않는다.set() 생성자 혹은 {}를 이용해 생성한다.mutable 객체이다.2. 교집합, 합집합, 차집합1) 교집합교집합은 말 그대로 두개의 set에 중복으로 존재하는 원소를 말한다. s1 = set([1, 2, 3, 4, 5])s2 = set([4, 5, 6, 7, 8])# 교집합 메서드 int..
![[개념정리] 파이썬 다중 집합의 교집합, 합집합](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb4FbYO%2FbtsIUgrMOge%2FpZ8lZrPcKmAda2BfkvKKY0%2Fimg.png)
[개념정리] 파이썬 다중 집합의 교집합, 합집합
코테 연습할때마다 잊을만 하면 나오는 다중집합이다. 굳이 몰라도 되지만, 모른채 쓰려면 머지소트를 구현해야 하는 굉장한 번거로움이 있기때문에 알아두는게 좋을 것 같아서 포스팅 한다.1. 다중 집합이란?기존에 파이썬에서 집합은 보통 set으로 사용한다. 그리고, set의 특징은 중복된 원소를 허용하지 않는다는 점이 있다.하지만, 중복된 원소를 포함하기 위해 사용되는 개념이 다중집합이고 개념만 다중집합이며 실제로는 리스트에 담아서 나타낸다.a = [1,2,2,3,4,5]b = [1,1,2,3,4,6]일반 집합의 합집합: [1,2,3,4,5,6]일반 집합의 교집합: [1,2,3,4]다중 집합의 합집합: [1,1,2,2,3,4,5,6] 다중 집합의 교집합: [1,2,3,4]이렇게 된다. 나는 처음에 다중 집합의..
![[프로그래머스] 큰 수 만들기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FMKDRB%2FbtsIUzkjDfP%2F6D1A4So05wq4rNm8oIzi11%2Fimg.png)
[프로그래머스] 큰 수 만들기
스택을 활용한 문제이다. 처음에는 그냥 조합을 이용해서 풀었는데 예상했지만 역시나 시간초과가 발생했다. 저번주에 필기시험이 있어서 잠시 코테를 쉬었더니 알손실이 왔다. 그래서 바로 풀지 못했다. (TMI..)아무튼 내가 스택을 활용한 풀이에 약한 것 같다. 문제를 보고 스택을 활용한 풀이라는 것은 이해가 갔지만, 막상 적용이 안됐다.맨 뒤의 원소를 비교하는 것은 for루프를 돌면서 while루프를 돌리면 되는데, 왜 생각이 안났을까...? 아무튼 문제 해설을 시작한다.이 문제와 유사하게 스택을 활용하는 문제들을 뽑아놨다. 이번주 주말에 코테보기 전에 꼭 풀어봐야겠다.큰 수 만들기, 괄호변환, 같은숫자는 싫어, 나누어 떨어지는 숫자, 짝지어 제거하기, 문자열 압축1. 문제 설명number로 숫자가 문자열 ..
[프로그래머스] H-Index
저번에 다리를 지나는 트럭이랑 비슷한 느낌이다. 문제 설명이 애매모호한.1. 문제 설명나는 처음에 문제를 잘못이해했다. 배열의 원소 하나하나를 정답이 되는 인용횟수중 하나라고 생각하고 풀었다.근데 그게 아니었다. 그냥 1부터 세면 된다. [3,4,9,10] 배열에서 1번 이상 인용된 논문은 4개다. 그리고 1번 이하로 인용된 논문의 개수는 4개 이하이다.1은 H-Index의 후보가 될 수 있다.이 문제에서는 최대값을 구하면 된다.2. 어려웠던 점문제 해설이 그냥 어려웠다.. 3. 풀이처음에 이렇게 풀이했다. 아마 나처럼 문제 잘못 이해한 사람들은 다 이렇게 풀었을 것 같다.def solution(citations): citations.sort() result = [] for i in ci..
![[프로그래머스] 순위 검색](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FEFjUk%2FbtsIUMKwgD8%2FiybEtqrZWgKnMAQskt7Yk1%2Fimg.png)
[프로그래머스] 순위 검색
효율성 문제가 어려웠던 ... 역시 카카오 문제라고 생각했던 문제이다. 보면 단순 구현 같은데 생각보다 깊은 개념을 요구하는 문제였다. 그래서 나는 효율성 못품1 문제 설명info로 지원자의 정보가 주어지면 다음과 같이 나타낼 수 있다.이 지원자들을 query변수로 받은 조건으로 필터링 하여 확인한다.다음과 같이 진행한다.* "java and backend and junior and pizza 100" : java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 100점 이상 받은 지원자는 1명 입니다.* "python and frontend and senior and chicken 200" : python으로 코딩테..