Posted Updated 2 minutes read (About 288 words)

B2448

개요

백준 문제 2448번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 150분
https://www.acmicpc.net/problem/2448

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
                       *                        
                      * *                       
                     *****                      
                    *     *                     
                   * *   * *                    
                  ***** *****                   
                 *           *                  
                * *         * *                 
               *****       *****                
              *     *     *     *               
             * *   * *   * *   * *              
            ***** ***** ***** *****             
           *                       *            
          * *                     * *           
         *****                   *****          
        *     *                 *     *         
       * *   * *               * *   * *        
      ***** *****             ***** *****       
     *           *           *           *      
    * *         * *         * *         * *     
   *****       *****       *****       *****    
  *     *     *     *     *     *     *     *   
 * *   * *   * *   * *   * *   * *   * *   * *  
***** ***** ***** ***** ***** ***** ***** *****

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;

char star[3072][6144];
int N;
void printStarResult()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N*2-1;j++)
		{
			cout << star[i][j];
		}
		cout << "\n";
	}
}

void printStar(int height,int x,int y)
{

	if(height == 3)
	{
		star[y][x] = '*';
		star[y+1][x-1] = '*';
		star[y+1][x+1] = '*';
		star[y+2][x-2] = '*';
		star[y+2][x-1] = '*';
		star[y+2][x] = '*';
		star[y+2][x+1] = '*';
		star[y+2][x+2] = '*';
		//printStarResult(); 
		return;
	}
	printStar(height/2,x,y);
	printStar(height/2,x-(height/2),y+(height/2));
	printStar(height/2,x+(height/2),y+(height/2));


}

void solve()
{
	cin >> N;
	for(int i=0;i<N;++i)
	{
		for (int j = 0; j < 2* N; ++j)
		{
			if(j==2 * N -1)
			{
				star[i][j] = '\0';
			}
			else
			{
				star[i][j] = ' ';
			}
		}
	}
	printStar(N,N-1,0);

	printStarResult(); 

}


int main()
{
	solve(); 
}

풀이

분할정복임을 알고 접근하면
큰 삼각형부터 작은 삼각형까지 분할해 나가서
가장 작은 삼각형에서부터 별을 출력하면 되는 문제
가장 작은 삼각형이 아닌 한개의 별을 출력하려고 하니 규칙이 너무 많았고 2시간이 초과되어 포기한 문제
알고보니 삼각형을 중점적으로 분할하여 보면 보이는 문제였음.

배울 점, 메모

아직 규칙을 찾는다던지 접근방식,
처음에 알고리즘을 풀기위해 떠올린 아이디어가 잘 맞지않는다.
풀이보고 약간 벽느껴졌음,,더 열심히 해야겠음

Posted Updated 2 minutes read (About 264 words)

B1517

개요

백준 문제 1517번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ?분
https://www.acmicpc.net/problem/1517

문제

버블소트의 스왑을 몇번 일어나는지 체크하라

코드

https://justicehui.github.io/ps/2019/04/23/BOJ1517/
예전 코드가 간단해서 참고하였던 기억이 난다.

풀이

문제 설명에서는 버블소트가 있어서 버블소트로 풀려고 할 수 있지만
시간초과를 보면 그럴 이유가 없음
따라서 분할 정복을 사용하게되면 곧 합병 정렬로 귀결됨
합병 정렬의 과정 중에서 버블정렬의 오른쪽보다 왼쪽 값이 크면 스왑이 발생하는데,
합병 정렬에서 conquer에서 왼쪽 값이 큰 경우 스왑 발생을 판단하면 되는 문제

배울 점, 메모

학부 2학년 알고리즘 과제에서 풀어보라고 하여 풀어본 문제여서 기억이 났다.
그때도 풀이를 보고 풀었던 기억이 난다.

Posted Updated 4 minutes read (About 623 words)

B2261

개요

백준 문제 2261번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 180분
https://www.acmicpc.net/problem/2261

문제

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAX = 100000;
const int INF = 987654321;
int N;
vector <pair<int,int>> v;


int getCalDistance(int aIdx,int bIdx)
{
	int ax = v.at(aIdx).first;
	int ay = v.at(aIdx).second;
	int bx = v.at(bIdx).first;
	int by = v.at(bIdx).second;
	return pow(bx - ax,2) + pow(by-ay,2);
}

int getMinDistanceInRange(int start,int end)
{
	int result = INF;
	for(int i=start;i<=end;i++)
	{
		for(int j=i+1;j<=end;j++)
		{
			if(i!=j)
			{
				result = min(result,getCalDistance(i,j));
			}
		}
	}
	return result;
}

int dist(pair<int, int> p1, pair<int, int> p2) {
	return pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2);
}


int getIdxFromDLeft(int d,int mid)
{
	int midX = v.at(mid).first -d;
	for(int i=0;i<v.size();i++)
	{
		if(v.at(i).first > midX)
		{
			return i;
		}
	}
	return -1;

}

int getIdxFromDRight(int d,int mid)
{
	int midX = v.at(mid).first +d;
	for(int i=v.size()-1;i>=0;i--)
	{
		if(v.at(i).first < midX)
		{
			return i;
		}
	}
	return -1;
}


int binCal(int start,int end)
{
	int result = INF;
	if(end - start + 1 <= 3)
	{
		for (int i=start; i<end; i++)
		{
	    	for (int j=i+1; j<=end; j++)
	    	{
	    		result = min(result,dist(v[i], v[j]));
	      	}
	    }
	}
	else
	{
		int mid= (start + end)/2;
		result = min(binCal(start,mid-1),binCal(mid+1,end));
		vector<pair<int, int>> tmp;
   		tmp.push_back({v[mid].second, v[mid].first});

   		for (int i=mid-1; i>=start; i--) {
	    	if (dist({v[mid].first, 0}, {v[i].first, 0})  >= result)
	    	{
	    		break;
	    	}
	    	tmp.push_back({v[i].second, v[i].first});// y축 순으로 정렬
    	}

    	for (int i=mid+1; i<=end; i++) {
	    	if (dist({v[mid].first, 0}, {v[i].first, 0})  >= result)
	    	{
	    		break;
	    	}
	    	tmp.push_back({v[i].second, v[i].first});// y축 순으로 정렬
    	}
    	sort(tmp.begin(), tmp.end());// y축 정렬

    	for (int i=0; i<tmp.size()-1; i++) {
      		for (int j=i+1; j<tmp.size(); j++) {
       			if (pow(tmp[i].first - tmp[j].first, 2) >= result)
       			{
       				break;
       			}
        		result = min(result, dist(tmp[i], tmp[j]));
        	}
    	}
	}
	return result;
}




void solve()
{
	cin >> N;
	int x,y;
	for(int i=0;i<N;i++)
	{
		cin >> x >> y;
		v.push_back(pair<int,int>(x,y));
	}
	sort(v.begin(),v.end());
	cout << binCal(0,N-1);
}

int main()
{
	solve();
}

풀이

학부 3학년 알고리즘 시간 배운 문제로 분할정복을 이용해서 풀어야 하는 흐름은 다음과 같다.

  1. 전체 점에 대한 계산은 시간 문제가 크다.
  2. 분할 정복을 이용해서 계산할 점의 범위를 줄인 뒤 계산하여 합쳐야한다.
  3. 하지만 이 때 분할한 중심(이분 분할을 이용할 것이므로 중간값)을 기준으로 왼쪽과 오른쪽이 나뉘는데, 이 때 이 둘 사이의 거리가 큰 경우가 있을 수 있다.

배울 점, 메모

이분 분할을 기준으로 푸는데 접근한 것은 풀이 방법을 알고 있어 쉽게 접근할 수 있었음.
하지만 중간값에 대한 처리를 할 때 x축에 대해서 처리 한 것에 더해서 y축에 대해서도 처리해야 했는데 이 부분을 알 지 못했음.
또한 중간값에 대한 점들은 새로운 tmp라는 벡터로 관리를 하는데 기존 벡터에 더할려고 했어서 복잡해진 경향이 있음.

Posted Updated 2 minutes read (About 342 words)

B2447

개요

백준 문제 2447번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 120분
https://www.acmicpc.net/problem/2447

문제

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.
예를 들어 N이 27의 패턴은 예제 출력 1과 같다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;


void printStar(int i,int j,int n)
{
	if((i /n) % 3 == 1 && (j /n)% 3 ==1)
	{
		printf(" ");
	}
	else
	{
		if(n == 1)
		{
			printf("*");
		}
		else
		{
			printStar(i,j,n/3);
		}



	}

}

void solve()
{
	int n;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			printStar(i,j,n);
		}
		cout << endl;
	}


}

int main()
{
	solve();

}

풀이

  1. 분할은 N에서 3씩 나누면서 3 혹은 1에서 출력을 하는 식으로 풀 수 있음.
  2. 출력은 한 줄씩 해야하는 방향으로 구현해야 함.
  3. 중간의 비어있는 별 모양은 예외처리 할 것.

배울 점, 메모

분할에 있어서 출력하는 조건문이 처리를 어떻게 할 지 고민했는데 결국 1시간 반이 지나서 인터넷에서 찾아봤다.
문제를 잘 풀기 위해서 다음을 계속 생각해야함.

  1. 분할을 어떻게 구현할 지 생각해야함.
  2. 1 이루고자 하는 목적을 분할함으로서 어떤 이점이 있는지 생각
  3. 어떤식으로 합칠 것인지 생각
Follow

Categories

Recents

Archives

Tags

CRF3
algorithm72
book_report2
database1
java26
jpa1
pet project12
pet_project1
retrospect1
springboot3
web3
web pet project2
write3

Subscribe for updates

×