본문 바로가기

전체 글

 (336)
프로그래머스 - [3차]압축 (C++, Java) https://school.programmers.co.kr/learn/courses/30/lessons/17684?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문자열 구현 문제이다. 지문을 이해하는 것이 가장 핵심이고 주어진 알고리즘을 그대로 구현할 수 있는지 물어보고 있다.이런 종류의 문제는 난이도 있는 코딩테스트의 1번으로 주어질만하다. 그리고 설명을 그대로 따라하지 않으면 분명 예외 케이스가 있기 때문에 본인의 자아를 빼고 있는 그대로 구현하는 것이 핵심이다. 개인적으로 항상 이런 디테일을 요하는 문제에서 한번에 AC를 받지..
프로그래머스 - 방문 길이 (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. 방문체크 배열에서 방문하지 않..
백준 2458번 키 순서 (Java) https://www.acmicpc.net/problem/2458 한 노드에서 다른 노드의 대한 정보를 알 수 있는가를 묻는 문제이다. 방법은 두개가 있다. 1. 각 지점에서 모두 dfs해보며 갈 수 있는지 검사한다. 2. 플로이드 워셜을 사용한다.  이 문제의 의도는 2번이기 때문에 2번의 의미를 알아보도록 하자 플로이드 워셜은 다익스트라와 달리 각 모든 노드들의 최단거리를 알아볼 수 있는 알고리즘이다. 예를들어 A 노드에서 B노드로 가는 방법에는 두가지가 있을 것이다.  1. A -> B로 바로 가는 경우2. A -> C - > B 어떤 노드를 경유할 경우 그리고 이 둘 중 작은 값이 최단거리가 된다. dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]) ..

티스토리툴바