본문 바로가기

■ 알고리즘 문제 풀이

 (74)
[BOJ] 백준 1074. Z ▶문제설명[BOJ] 백준 1074. Zhttps://www.acmicpc.net/problem/1074 ▶ 설계문제에서 주어진 그림을 관찰해보자. N이 2인 경우 순회하는 순서를 나타내는 그림이다. 변의 길이가 2^2 = 4이다. 4등분하여 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단을 순서대로 방문해야한다.즉, 변의 길이가 2^N인 사각형을 더이상 등분하지 못할 때까지 4등분할 수 있는지를 묻는 문제이다. 변의 길이가 2^N인 사각형을 가능한 한 4등분해서 Z가 시작되는 위치의 좌표와 변의 길이를 2로 나눈 값을 인자로 넣어서 재귀호출 하면 될 것으로 보인다. 규칙을 파악했다면 N이 3인 경우에는 어떻게 되는지 그려보자. 편의상 같은 숫자가 적힌 것으로 붙여넣었지만, 오른쪽 상단은 16~31, ..
[BOJ] 백준 2447. 별 찍기 - 10 ▶문제설명[BOJ] 백준 2447. 별 찍기 - 10https://www.acmicpc.net/problem/2447 ▶ 설계별이 찍힌 모습에서 규칙을 찾을 수 있다. N이 3인 경우 N이 9인 경우 N이 27인 경우 규칙이 보이는가? 잘 안보인다면 아래의 그림을 보자. N에 따라서 균등하게 9등분을 해보면 가운데 부분만 비어있는 모습을 볼 수 있고, 각 등분된 조각을 또 9등분 해보면 가운데 부분만 비어있는 것을 볼 수 있다. 더 이상 범위를 나눌 수 없을 때까지 나누면서 가운데 부분을 제외하고 재귀호출하면 문제를 해결할 수 있을 것으로 보인다. ▶ 구현우선 메인문을 작성해보자. 12345678910111213141516int main(){ scanf("%d",&N); for(int i=0; i
[BOJ] 백준 1654. 랜선 자르기 ▶문제설명[BOJ] 백준 1654. 랜선 자르기 https://www.acmicpc.net/problem/1654 ▶ 설계현재 K개의 랜선이 있는데 가지고 있는 랜선들을 일정한 길이로 잘라서 N개의 랜선으로 만들어야한다. 랜선을 N개 이상으로 만들 수 있는 랜선 길이의 최대값을 구하는 문제이다. 랜선 길이 len을 먼저 정하고 해당 길이로 N개 이상의 랜선을 만들 수 있는지 판단하는 방식으로 문제를 해결할 수 있을 것으로 보인다. len의 길이는 이분탐색으로 값을 정해주면 빠른 시간에 문제를 해결할 수 있게 된다. left는 가능한 랜선 길이의 최소값, right는 가능한 랜선 길이의 최대값으로 초기화 한다. 그리고 (left+right)/2에 해당하는 mid 값으로 N개 이상의 랜선을 만들 수 있는지 ..
[프로그래머스] 주식가격 ▶문제설명코딩테스트 연습 > 스택/큐 > 주식가격https://programmers.co.kr/learn/courses/30/lessons/42584 ▶ 설계prices의 길이가 2 이상 100,000이하이고,prices에 저장된 각 가격은 1 이상 10,000이하의 자연수이다. 2중 for문으로 일일이 확인하도록 구현하는 방법이 가장 먼저 떠올랐다.이렇게 나이브한 알고리즘으로 문제를 해결한다고 하면100,000개의 가격 각각에 대해 1초에 가격이 1부터 1씩 증가한다고 했을 때 최대 10,000번을 확인하게 된다.1부터 10,000까지 1씩 증가시키고 그 다음 또 1부터 10,000까지 1씩 증가시키는 것을 반복했다고 한다면따라서, 최악의 경우에 대략적으로 100,000 * 10,000 = 1,000,..
[프로그래머스] 네트워크 ▶문제설명코딩테스트 연습 > DFS/BFS > 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 ▶ 설계DFS로 해결이 가능한 문제이다. 2차원 벡터 매개변수인 computers는 인접행렬로 정점들 사이의 간선 여부를 나타낸다. 문제에서 연결 요소를 네트워크라고 표현했을 뿐, 그래프의 연결 요소의 개수를 세서 리턴하는 문제라고 생각하면 된다. 네트워크가 몇 개인지를 구하는 함수의 시그니처를 정의해보자. 123void findNetworkNum(int n, int nowComputer, const vector& computers, vector& visited){ }Colored by Color Scriptercs 매개변수명 의미 n 컴퓨터의 개수..
[프로그래머스] 카펫 ▶문제설명코딩테스트 연습 > 완전탐색 > 카펫https://programmers.co.kr/learn/courses/30/lessons/42842 ▶ 설계brown와 red의 값에 따라서 카펫의 가로, 세로 크기를 리턴해야 하는 함수이다.단순히 가능한 가로, 세로의 길이를 2중 for문으로 완전탐색하면 풀릴 것으로 보인다. ▶ 구현우선 2중 for문으로 가능한 가로, 세로 길이를 모두 탐색하도록 하자. 123456789vector solution(int brown, int red) { vector answer; for(int w=1; w
[프로그래머스] 단어 변환 ▶문제설명코딩테스트 연습 > DFS/BFS > 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 ▶ 설계DFS 탐색으로 문제를 해결해보자. 한 번에 한 개의 알파벳만 바꾸어서 word에 있는 단어 중 하나로 변환할 수 있는지 모든 경우를 탐색해보면 되는 문제이다. 복잡한 것 없이 문제에서 요구하는데로 재귀 함수만 잘 구현하면 간단히 해결될 것으로 보인다. ▶ 구현 우선 재귀함수의 매개변수와 리턴타입을 정해보자. 12345int findWord(string nowWord, const string& targetWord, const vector& words, int cnt){ int answer = 987654321; return answer;}C..
[프로그래머스] 소수 찾기 ▶문제설명코딩테스트 연습 > 완전탐색 > 소수 찾기 https://programmers.co.kr/learn/courses/30/lessons/42839 ▶ 설계number의 길이를 n이라고 하자. n개의 숫자들 중에 1 ~ k 개를 뽑아서 순열을 생성한 뒤 정수로 변환하고 해당 정수가 중복되지 않도록하여 소수인지 아닌지 판별해서 개수를 반환하는 함수를 구현해야 한다. 조합의 경우에는 순서를 고려하지 않고 k개를 뽑아내므로 조합만으로는 풀 수 없다. (간단히 예를 들면 1, 3, 2 를 뽑아낼 뿐이지 132, 123, 213, 231, 312, 321와 같이 순열을 뽑아내는 방법이 아니기 때문이다.) n개의 숫자들 중 k개를 뽑아서 순열을 만들기 위해서 재귀함수를 구현하면 될 것으로 보인다. 123456..

티스토리툴바