프로그래머스
-
[프로그래머스] 숫자 게임 (08.29)algorithm/프로그래머스 2020. 8. 29. 22:16
문제 https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 접근법 A팀의 출전 순서가 공개가 되었기 때문에 A팀에 맞게 B팀을 조정해주면 된다. 정렬을 해야 비교하기 편하기 때문에 일단 둘다 정렬을 했다. A팀의 공개된 순서와 상관없이 B팀이 A팀을 이길 수 있는 경우의 수 중 최대값을 찾으면 된다. A팀을 조회할 인덱스와 B팀을 조회할 인덱스로 나눠서 while 문을 사용해서 풀었다. 코드 im..
-
[프로그래머스] 보석 쇼핑(08.22)algorithm/프로그래머스 2020. 8. 22. 17:56
문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 접근법 처음에는 이중 포문을 사용해서 풀었는데 역시나 시간 초과가 났다. 고민을 오랫동안 했는데도 풀지 못해서 결국 다른 코드를 참고했다. 슬라이딩 윈도우 프로토콜 방식으로 풀어낼 수 있었다. 앞에서 부터 순서대로 보석들을 고르다가 중복된 보석이 나오면 시작 인덱스를 하나씩 밀어주는 방식을 사용했다. 자세한 설명은 코드에 주석을 포함하였다. 코드 import java.util.*; class Solutio..
-
[프로그래머스] 하노이의 탑 (08.09)algorithm/프로그래머스 2020. 8. 9. 20:02
문제 https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대�� programmers.co.kr 접근법 하노이 탑이 재귀의 대표적인 예시임에도 풀기가 힘들었다. https://shoark7.github.io/programming/algorithm/tower-of-hanoi '하노이의 탑' 이해하기 '하노이의 탑' 문제를 이해하고 문제 해결을 위한 핵심 통찰을 살핀 뒤 코드로 작성합니다. 이후 탑의 개수에 따른 총 이동 횟수를..
-
[프로그래머스] 줄 서는 방법 (08.06)algorithm/프로그래머스 2020. 8. 6. 18:45
문제 https://programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 접근법 처음에는 재귀로 모든 경우의 수를 찾고 k 번째 경우의 수에서 재귀를 멈췄다. 이런 방법으로 하면 k가 long으로 선언된 변수이므로 너무 많은 재귀가 돌아갔다. 그래서 찾은 방법은 k를 줄여나가는 방식이다. 숫자가 n 개인 경우에 정렬할 수 있는 모든 경우의 수 점화식은 dp[n] = dp[n-1] * n 이다. 숫자가 1개일 때는 ..
-
[프로그래머스] 불량 사용자 (08.04)algorithm/프로그래머스 2020. 8. 4. 18:05
문제 https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 �� programmers.co.kr 접근법 응모자 아이디를 돌면서 불량 사용자의 아이디와 일치하는 경우를 찾았다. dfs를 사용했다. 문자열을 비교하는 것은 정규표현식을 사용하였다. 중요한 포인트는 중복되는 경우들을 어떻게 처리하느냐였다. 시간이 좀 걸릴 것을 알았지만 데이터가 적었기 때문에 가능한 조합을 오름차순으로 나열해서 set에 넣었다 그러면 crodo frodo 가 되던 frodo..
-
[프로그래머스] 방문길이 (08.02)algorithm/프로그래머스 2020. 8. 2. 16:58
문제 https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 접근법 고려했던 것은 두 가지다. 1. 방문한 경로를 어떤 방식으로 체크할 것인가? 2. 지나친 경로의 중복 체크를 어떻게 할 것인가? 1번은 List를 사용했다. 출발하는 x,y 좌표 + 도착하는 x,y 좌표를 String 값으로 해서 List에 저장하고 경로를 체크했다. 2번은 경우에는 list의 contains 함수를 사용하였다. 만약 (0,0) -> (1,0) 의 경로에서 다시 (1,0) -> (0,0)로 갈 경우 두 번 이동했지만 처음 이동한 경로는 하나가 된다. 결국 내가 사용한 방법은 출발하는 x,y 좌표 + 도착하는 x,y..
-
[프로그래머스] 멀리 뛰기 (08.01)algorithm/프로그래머스 2020. 8. 1. 16:32
문제 https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2�� programmers.co.kr 접근법 처음에 규칙을 찾으려고 했다. 총 1칸인 경우에는 1칸을 건너뛰는 방법 1가지 뿐이고 2칸일 경우 1칸을 두 번 뛰는 경우와 2칸을 한번에 뛰는 경우 2가지이다. 3칸일 때는 2칸을 뛰었을 때 1칸을 뛰는 경우의 수와 1칸을 뛰었을 때 2칸을 뛰는 경우의 수가 있다. 점화식을 도출해보면 d..
-
[프로그래머스] 저울 (07.30)algorithm/프로그래머스 2020. 7. 30. 17:34
문제 https://programmers.co.kr/learn/courses/30/lessons/42886 코딩테스트 연습 - 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들 programmers.co.kr 접근법 무게 1짜리 추로는 무게 1밖에 표현할 수 없다. 무게 1짜리 두 개의 추로는 1과 2를 표현할 수 있다. 무게 1짜리 두 개와 2짜리 한 개로는 1, 2, 3, 4 를 표현할 수 있다. 그러나 5는 표현할 수가 없다. 이미 사용할 수 있는 추들을 모두 사용하여 만든 최대의 무게에 +1을 하게 된다면 그 무게는 구할 수 없게 되는 것이다. 결국은 추들..