본문 바로가기

프로그래머스 풀이

 (90)
프로그래머스 - 방문 길이 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 구현문제다. 방문 알고리즘이라고 봐야할까 싶다. 주어진 대로 이동하는 경로를 새야하는데 단순히 방문체크만해서는 풀 수 없다. 3차원 배열을 선언하고 A노드에는 4방향으로 들어올 수 있기 때문에 각 방향마다 방문체크를 해줘야한다. 그리고 중요한 것은 A -> B로 이동했다면 B -> A 도 지난 길이 되기 때문에 체크해놓아야한다. 이것을 눈치채지 못해 풀지 못했다.. #include #include u..
프로그래머스 - 주식 가격 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=cpp# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 큐, 스택을 사용하는 문제는 코딩테스트에 빈출로 출제된다.  이 문제의 예제를 통과시키는 것은 쉽다. O(N^2)으로 이중 반복문을 쓰면 간단하게 풀린다. 하지만 이렇게하면 N의 크기가 10만이기 때문에 시간초과가 발생할 수 있다. 다행히 이 문제에선 그렇지 않지만 스택이나 큐를 사용해서 최적화를 반드시 해줘야한다. 스택을 사용해 최적화할 수 있는데 언제나 스택이나 큐에 먼저..
프로그래머스 - 롤케이크 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 너무 어렵게 생각하는걸까? 아이디어를 떠올리는 것이 아직도 미숙하다. 레벨2로 평이한 난이도임에도 DP에 꽂혀서 말도안되는 점화식을 찾으려고 노력했다. 반성하자. 안되는 것 같으면 바로 돌아나오는 것도 실력이다. 이 문제는 right left 맵을 나누어서 풀이하는 것이 가장 편하고 쉬운 방법이다. 처음엔 모두 right에 값을 넣어두고 0부터 left로 옮겨보는 식으로 풀..
프로그래머스 - 모음사전 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 중복순열을 연습하기 좋은 문제다.  중복순열은 AAAAA AAAAB ... 등으로 이뤄지기 때문에 순열이나 조합을 선택했을 때 처럼 방문체크를 할 필요가 없다. 이정도 난이도는 코딩테스트 1~2번으로 충분히 나올 수 있다. #include #include #include using namespace std;int answer = 0;string alpha = "AEIOU";bool flag = fal..
프로그래머스 - 쿼드 압축 후 개수 세기(C++ / Java) https://school.programmers.co.kr/learn/courses/30/lessons/68936?language=cpp 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 코딩테스트에도 1~2번 정도로 나올 수 있는 재귀문제이다.  위의 배열이 들어왔을 때 만약 모든 원소가 0 or 1 이 아니라면 4부분으로 나누어 재귀에 들어가야한다. 이 재귀를 할 범위를 찾는 것이 은근히 까다로운데, 여기서 정리하고 가도록 하자. 1. 먼저 기준점을 잡는다. 보통 왼쪽 상단이 편리하다.2. 그리고 지금 사각형의 한 변의 길이가 필요하다. 왼쪽 상단부터 변의 ..
프로그래머스 - 소수 찾기 (Java) https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 완전탐색 + 소수  판별 문제이다. 이 문제는 17 -> 1, 17, 7, 71 을 알아내면되는 문제이다. 즉 순열을 찾아내는 것이 관건이다. 순열 조합 문제는 완전탐색으로 조금만 N이 커도 쓸 수 없다. 하지만 이 문제는 최대 길이가 9이기 때문에 충분히 순열을 찾아낼 수 있다.  9! / (9 - k)! 아주 작다.  순열은 dfs 백트래킹으로 구현할 수 있다. 1. 방문체크 배열에서 방문하지 않..
프로그래머스 - N으로 표현 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정말 수준높은 DP문제라고 생각한다. 동적계획법은 언제나 어렵고 나를 힘들게한다.. 먼저 이 문제 분류를 통해 동적계획법을 알고 들어가긴 했지만 DP를 써야하는 이유는 역시나 이전의 값을 다시 재사용하게 된다는 점이다. 처음 접근할 때 DP[1]~ DP[32001] 를 각 N이 만들 수 있는 점화식을 구하여 보려 했으나 44퍼센트에서 틀렸다.. 아주 어림없는 도전은 아니었다고 생각하는데 아쉽다. ..
프로그래머스 - 재구매가 일어난 상품과 회원 리스트 구하기 https://school.programmers.co.kr/learn/courses/30/lessons/131536 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그룹화를 사용해야하는 문제이다. 요구사항은 유저와 상품 아이디를 함께 세는 것이다. 그러므로 두 컬럼을 그룹화하고 그 갯수를 새어 2개 이상이면 select 하도록 쿼리를 짠다. SQL문제를 풀 땐 어떤 컬럼끼리 연관이 있는지, 그 컬럼을 어떤 조건으로 빼내올지를 잘 생각해야한다. 이 문제를 풀기 위해서는 그룹화를 생각하고 그룹화한 컬럼들을 having 절로 어떻게 데려올지를 생각해내는 문제였다..

티스토리툴바