코테
-
프로그래머스 Lv.3) 등굣길 (DP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 4. 14:45
등굣길 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 전에 풀었던 방법과 오늘 푼 방법이 같다. 다만, 차이점이 있다면 처음에는 map을 생성하고, 모든 길을 1로 적어뒀다. 그런 뒤에, 입력받은 웅덩이 위치를 0으로 표시하고, 웅덩이에 막힌 길을 0으로 표시했다. 맵이 완성되면 맵을 돌면서 갈 수 있는 방법을 더해가며 답을 구했다. 오늘 푼 풀이도 위와 같다고 보면 된다. 처음부터 dp 배열을 생성하고, 웅덩이만 -1로 표현해줬다. 그리고 dp를 돌면서 위와 왼쪽 길이 웅덩이인지 아닌지만 ..
-
BOJ) 부분수열의 합 2알고리즘/백준 2020. 6. 3. 23:23
부분수열의 합 2 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 오늘 문제가 너무 안풀려서 하나만 더 풀어보자 하고 기출문제와 유사한 문제라고해서 풀어봤다. 오랜만에 백준 문제를 풀어서 그런지 어려웠다. 그리고 백준이 바로 코딩하기에 친절하지가 않아서 처음 구조를 잡아나갈 때를 제외하고는 ide힘을 빌려야했다.. ㅠ N개의 정수로 이루어진 배열에서 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제다. N은 40 이하의 수, S는 -1,000,000 ~ 1,00..
-
프로그래머스 Lv.3) N으로 표현 (DP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 3. 18:30
N으로 표현 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 고득점 Kit의 DP에 있는 문제다. 예전에 풀었을 때, DP로 풀지 않고 DFS로 풀었기 때문에 DP로 풀고자 했지만, 실패했다. 그래서 검색을 해봤더니 4중 for문을 돌리면서 답을 찾는 글들만 보였다. 좌표를 탐색하는 시뮬레이션 문제가 아닌 이상은, 4중 for문이 가독성이 더 떨어지고 이해하기 힘들다는 주관적인 의견이다. 물론, 머리가 좋으신 분들은 이해하시는데 문제가 없겠지만, 나같은 사람들이 범접할 수 있는 영역이 아닌 것 같았다. DFS의 방법은 만들 수 있는 모든 수를 가지고 4칙 연산을 진행하는 것이다. 문제의 조건에 따라 문자 N 사용 횟수가 8이 넘어가면 -1을 반환하기 때문에, DFS가 가능했다. 또한..
-
프로그래머스 Lv.2) 주식가격 (Stack & Queue)알고리즘/프로그래머스 고득점 Kit 2020. 6. 2. 21:09
주식가격 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 풀이 프로그래머스 고득점 Kit 중에 Stack, Queue에 해당하는 문제다. 이 문제도 전에 풀었지만, 포스팅을 한 적이 없어서 새롭게 포스팅을 한다. 우선 문제의 조건을 살펴보면, 특정 날의 주가가 이후에 가격이 떨어지지 않은 기간을 구하는 문제이다. 먼저, 첫번째로 풀었던 방법에 대해 기억나는대로 되짚어 본다면 반복문을 돌면서 특정 날의 주가에 대해 주가 하락 시점을 Stack에 저장한 것 같다. 하락 시..
-
프로그래머스 Lv.2) 기능 개발 (Stack&QUEUE)알고리즘/프로그래머스 고득점 Kit 2020. 6. 1. 18:14
기능 개발 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 �� programmers.co.kr 풀이 아침에 머리를 깨우기 위해 레벨 2부터 한 문제 풀고 시작하려고 문제를 봤는데, 새로운 문제가 없어서 풀었던 문제를 다시 풀었다. 키자마자 예전에 짰던 코드를 지우고, 새롭게 코드를 짜보았다. 전보다 더 효율적으로 코드를 짜서 행복했다 ㅎㅎㅎㅎ 하지만, 오늘 아침에 짠 코드보다 더 효율적인 코드가 있을 것이라고 생각한다. 아무튼, 블로그에 올린 적이 없던 문제기 때문에 기억을 최대한 살려 설명하겠습니다. 코드 1 = 처음 풀었을 때 ..
-
프로그래머스 Lv.3) 기지국 설치알고리즘/프로그래머스 2020. 6. 1. 17:48
Summer/Winter Coding(~2018) 기지국 설치 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 두번의 수정을 거쳤고, 푸는데 20분? 30분?정도 걸린 것 같다. 우선, 문제의 조건에 N이 2억 이하의 자연수 임을 보고 배열은 안된다는 판단을 내렸다. 된다 하더라도 효율이 안좋을 것이기 때문에 사용을 안하려고 마음먹었다. 다음으로 stations 배열은 오름차순으로 정렬되어 있다는 것을 보고, 이전에 설치된 5G망과 현재 설치된 5G망 사이에 커버하지 못한 아파트 세대..
-
프로그래머스 Lv.3) 숫자 게임알고리즘/프로그래머스 2020. 6. 1. 17:27
Summer/Winter Coding(~2018) 숫자 게임 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 풀이 처음에 문제가 쉽다고 생각하고 대충 풀었을 때, 30점 정도 나왔다. 처음 풀고 한 다섯시간 지나서 다시 풀기 시작했는데, 같이 공부하는 형이 풀어던 문제였고, B 배열이 정렬이 안되어 있다는 것을 알았다. ( 물론 혼자 풀었어도 눈치 챘을거다 ^^) 아무튼, 배열 정렬만 해주니까 바로 70점이 되었고, 나머지 30점이 시간 초과였다. 다시 수정하기가 귀찮아서, LinkedLis..
-
프로그래머스 Lv.3) 배달알고리즘/프로그래머스 2020. 5. 31. 23:03
배달 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 풀이 문제를 보고 많은 생각이 스쳐 지나갔다. MST가 먼저 떠올랐는데, 모든 경로를 잇는 것이 중요한 문제가 아니기 때문에 아니라고 생각했다. 다음은, 최단 거리 알고리즘이었다. 다익스트라(dijkstra) 이름이 기억나지 않았지만, 이 로직이 떠올랐다. 하지만, 처음에 풀었을 때는 edge를 따로 저장하지 않고, 주어진 road만 돌면서 우선순위 큐에 저장하고 최소 비용으로 잘 잇는다면 가능하지 않을까 싶었다. 결과는 40점, ..