일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 자바
- 알고리즘
- 부스트코스
- CS 스터디
- 비트마스크
- 2018 KAKAO BLIND RECRUITMENT 1차
- 2019 카카오 개발자 겨울 인턴십 코딩테스트
- 삼성 SW 역량테스트
- 2018 KAKAO BLIND RECRUITMENT
- map
- 2018 카카오
- 2019 KAKAO BLIND RECRUITMENT
- 카카오 공채
- set
- 젠킨스
- 2019 카카오 공채
- gcp
- 2020 KAKAO BLIND RECRUITMENT
- 2018 카카오 공채
- 카카오
- 백준
- Baekjoon
- Java
- gradle
- c++
- 2020 카카오 공채
- 삼성 SW 기출문제
- 프로그래머스
- bfs
- dfs
- Today
- Total
목록알고리즘/프로그래머스 (38)
아무코딩
오랜만에 티스토리 블로그에 글을 쓴 이유는 소스코드를 올렸을때 깃에서 에러가 나서 올렸습니다.. 나중에 원인을 찾으면 올릴예정입니다.😂 문제설명 길 찾기 게임 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다. 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 ..
문제풀이 set 을 이용 하는 데 많은 공부가 되었던 문제이다. 원래 4차원 배열을 이용하여 저장해도 됐지만 set을 사용하고 싶어 사용하다가 자연스레 하나 배워간 문제이다. 먼저, set을 사용할때 key가 객체일경우 객체안의 값이아니라 객체자체를 비교하게 된다 그래서 같은객체가 아니라면 값이 같아도 다르게 판단한다. 그래서 hashcode를 오버라이딩하여 수정 할 필요가있다. 객체안의 값이 같은경우 같은 해시코드를 반환하게 해주면 객체 값을 가지고 비교할 수 있다. 그리고 문제풀 때 주의할점이 방향성이 없는 선이라서 나같은 경우에는 양방향으로 set에 다추가해준 뒤 /2 를 통해 길의 개수를 판단해 주었다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..
문제풀이 자바의 map사용법을 익히기 위해 풀어본 문제이다. map으로 푸는게 맞는지는 모르지만 나는 map을 사용하였다. 현재 스킬의 사용 가능 여부 -> map을 이용. 매번 map을 초기화 하여 스킬트리가 가능한지 체크한다. 그리고 매번 검사시 그다음 찍어야될 스킬을 따로 검사하여 해당 스킬이 나올시 map을 변경후 다음 스킬로 포인터를 옮긴다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 import java.util...
문제풀이 next_permutation 으로 그냥 돌리고 해당 index에서 반환하는 방식을처음 썼는데 시간초과가 났다. 효율성 문제였다. 순열의 특징을 이용하여 앞자리부터 계산해 나간다. 첫자리가 같은 경우의 가짓수는 (n-1)! 이다. 이개념을 바탕으로 아래에 코드를 작성하였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include #include using namespace std; vector people; vector solution(int n, long long k) { vector answer; long long factorial = 1; for(i..
문제풀이 트라이를 이용한 문제이다. 실제 공채때는 이렇게 풀지 못해서 많이 효율성 부분에서 점수가 많이 깎였었다. 특이한 점은 ?가 있다는 점인데 트라이를 이용하기 좋게 접미사나 접두사로만 물음표가 주어진다. 자리수 별, 앞뒤 별 트라이 구조를 모두 만들어서 ?가 나오자마자 카운트를 반환하게 한다. 끝의 ?유무를 확인하여 reverse한 트라이를 쓸지 그냥 쓸지 정하면 된다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ..
문제풀이 그냥 회전을 시키면 시간초과가 나는문제이다. 인덱스와 food time을 포함한 구조체(food)를 만들어 정렬한뒤 food time이 낮은거 부터 삭제해나간다. food time 이 낮은수는 그다음 높은 food time 에서 빼가며 계산해 주는걸 잊어서는 안된다. 왜냐하면 그만큼은 다 돌았기 때문에 이러한 점을 고려하여 돌다가 차이만큼 뺄 수없을때 모듈러 연산을 진행한다. 말이 너무 복잡하니 코드를 보면 이해가 쉬울거 같다. ' accumulate는 누적된 시간이라 생각하면되고 spend는 한번에 넘길 턴? 한번에 소비할 시간이라 보면된다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2..
문제풀이 크게 문제풀이는 유일성을 확인 -> 유일성을 만족하는 것중 최소성을 만족하는것을 구하기 순으로 풀이하였습니다. 비트마스크를 이용하였고 비트마스크를 적용하니 이전보다 문제풀이가 훨씬 깔끔해졌습니다. 1. 유일성 확인방법 vector을 키로가지는 Set을 만들어 여러 경우의 키를 가지는 경우를 넣어서 set 의 사이즈가 레코드의 개수와 같을때 유일하다 판단합니다. 여기서 키로 선택된 칼럼은 비트로 1 아닌건 0으로해서 계산하는데 유일성이 만족되면 해당 값을 벡터에 저장합니다. 2. 최소성확인방법 유일성을 만족하는 벡터를 차례로 돌며 & 연산을 진행합니다. a == a&b 일때 a는 b의 부분집합입니다. 그래서 b는 최소성을 만족할수 없기때문에 제외시킵니다. 이와같은 방법으로 모두 비교하여 최소성을 ..
문제풀이 정렬하는 문제이다. 실패율이 같은 경우 번호 순서라서 이미 정렬된 상태라서 stable_sort를 이용하여 따로 번호정렬을 하지않았다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include using namespace std; typedef struct Stage{ int num; int arrival; int not_clear; Stage(){} Stage(int n){ num = n; arrival = 0; not_clear = 0; } }Stage; v..