마쏘's 개발 성장기

입력)

총 10개의 테스트 케이스

테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열

(0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점)

출력)

# 해당 테스트 케이스 번호, 지정된 도착점에 대응되는 사다리의 y index 출력

입, 출력 분석)

(생략)

핵심)

사다리를 그릴 때, 방향을 고려하여 그리는 것이 핵심이다.

한 칸씩 사다리를 타고 내려간다고 가정하고, 1의 여부를
자신의 아래,왼쪽,오른쪽 영역을 탐구한다고 가정했을 때,

회전하는 경우는
1) 1의 cnt가 2이고

2) 1인 영역이 (아래 또는 왼쪽), (아래 또는 오른쪽)을 가진다
    따라서 1인 영역을 발견했을 때 key를 두어,
    (아래 또는 왼쪽) : key = 0 + 1 -> 왼쪽

    (아래 또는 오른쪽) : key = 0 + 2 -> 오른쪽

    key < 3 일 때 회전한다.
    (key == 3일 때는 핑크색, cnt 가 2인 경우)

현재 어느 방향으로 오고 있었는지(dir) 확인하여, 회전하는 경우에 알맞게 방향을 바꾸면 된다.

예시 분석)

(생략)

실수) 

- 모든 경우의 수를 저렇게 따져보기 전에 복잡하고 내가 다루지 않았던 유형이라 기피했던 것 같다..
  (질질 끌다가 결국에 할 꺼면서...)

- 설계 초반에 핑크색 경우에서 cnt == 2 일 때를 cnt == 1로 잘못 계산했다.

- while(x<100)에서 x=99일 때 x+=dx[dir]; y+dy[dir]; 때문에 if(map[x][y] == 2)가 제대로 되지 않아서
  if(x==99) break; 문을 넣었다. (사실 map[x-1][y] == 2 해볼까 고민도 했다..ㅎ)

구현)

#include<iostream>
using namespace std;

int map[100][100]; // 100x100 크기의 이차원 배열
int dx[3] = { 1, 0, 0 };  // 0: 아래, 1: 왼쪽, 2: 오른쪽
int dy[3] = { 0, -1, 1 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽

int main(int argc, char** argv) {
	int test_case, T = 0, ans = 0;
	for (test_case = 1; test_case <= 10; ++test_case) {
		scanf("%d", &T);
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++)
				scanf("%d", &map[i][j]);
		}
		for (int j = 0; j < 100; j++) {
			if (!map[0][j]) continue;
			int x = 0, y = j, dir = 0; ans = j;
			while (x < 100) {
				int cnt = 0, key = 0;
				for (int i = 0; i < 3; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
					if (map[nx][ny]) {
						cnt++;	key += i; // 아래 0, 왼 1, 오 2
					}
				}
				if (cnt == 2 && key < 3) { // 회전
					if (dir == 0) dir = key;
					else dir = 0;
				}
				if (x == 99) break;
				x += dx[dir]; y += dy[dir];
			}
			if (map[x][y] == 2) {
				ans = j;	break;
			}
		}
		printf("#%d %d \n", T, ans);
	}
	return 0;
}

입력)

총 10개의 테스트케이스

1000개 이하의 빌딩의 높이가 주어진다.
이 빌딩의 높이는 최대 255이다.
맨 왼쪽 두 칸과 오른쪽 두 칸은 0이다. (건물이 지어지지 않기 때문)

출력)

#(테스트 케이스 번호) (해당 테케에서 조망권이 확보된 세대의 수)

입, 출력 분석)

(생략) int로 다루면 된다.

핵심)

해당 빌딩에서 조망권이 확보된 개수 = 해당 빌딩 높이 - 좌우 두 칸 사이에 제일 높은 빌딩의 높이

예시 분석)

index 2와 6을 통해 내 코드가 잘 구현이 되었는지 디버깅을 돌려보았다.

실수) 

- 좌우 두 칸 빌딩의 높이가 낮을 때만 조망권 개수를 계산하면 되는데,
  차이 구하는데 정신 팔려서  abs() 함수로 처리하고 있었다.

- 테스트 케이스 for문 안에서 갱신되어야 하는 변수를 밖에서 갱신해서,
   #1 691 #2 9092+691=>9783이 나왔다..
  (숫자보고 딱 어? 뭔가 밀렸다! 감잡아서 다행이지.. 시험장이었으면 멘탈 털렸을 것 같다..)

구현)

#include<stdio.h>
using namespace std;

int main(int argc, char** argv){
	int test_case = 1, cnt = 0;
	for (; test_case <= 10; ++test_case) {
		int heights[1000] = {0, }, total = 0;
		scanf("%d", &cnt);
		for (int i = 0; i < cnt; i++)
			scanf("%d", &heights[i]);
		for (int i = 2; i <= cnt-3; i++){
			int viewCnt = heights[i], temp = 0;

			for (int d = 1; d <= 2; d++){
				if(heights[i] <= heights[i+d] || heights[i] <= heights[i-d]){
					viewCnt = 0;	break;
				}				
				temp = heights[i] - heights[i + d];
				if(temp < viewCnt) viewCnt = temp;
				temp = heights[i] - heights[i - d];
				if (temp < viewCnt) viewCnt = temp;
			}
			total += viewCnt;
		}
		printf("#%d %d\n", test_case, total);
	}
	return 0;
}

입력)

1이상 100이하인 100개의 height이 주어진다.

덤프 횟수는 1이상 1000이하로 주어진다.

총 10개의 테스트 케이스가 주어지며,

[ 덤프 횟수 + 100개의 높이 ] 형식으로 들어온다.

출력)

#부호 최고점 - 처저점의 높이 차

입, 출력 분석)

width가 100이므로 배열의 크기도 100이다.

예시 분석)

(생략)

핵심)

최고점과 최저점을 빠르게 찾기 위해

height가 저장된 배열과 max값, min값의 index의 개념을 잘 알면 된다.

실수) 

printf인데 scanf 로 적어서 출력이 안 되는 황당한 실수를 했다.

구현)

#include<stdio.h>
using namespace std;

int main(int argc, char** argv) {
	int test_case;

	for (test_case = 1; test_case <= 10; ++test_case) {
		int heights[100] = {0,};
		int dump_cnt = 0, diff = 0;
		int maxIdx = 0, minIdx = 0; 
		scanf("%d", &dump_cnt);
		for (int w = 0; w < 100; w++){
			scanf("%d", &heights[w]);
			if(heights[maxIdx] < heights[w]) maxIdx = w;
			if(heights[minIdx] > heights[w]) minIdx = w;
		}
		
		for (int i = 0; i < dump_cnt; i++){
			--heights[maxIdx];
			++heights[minIdx];
			for (int w = 0; w < 100; w++) {
				if (heights[maxIdx] < heights[w]) maxIdx = w;
				if (heights[minIdx] > heights[w]) minIdx = w;
			}
		}
		diff = heights[maxIdx] - heights[minIdx];
		printf("#%d %d\n", test_case, diff);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

입력)

학생의 수 1000명

각 학생의 점수는 0점 이상 100점 이하의 값

출력)

최빈수를 출력

최빈수가 여러 개 일 때에는 가장 큰 점수를 출력

입, 출력 분석)

(생략)

예시 분석)
(생략)

핵심)

히스토그램을 한 번이라도 구현해본 적이 있다면 엄청 쉬운 문제다.

0부터 100까지의 점수를 index로 가지는 배열을 만들어 빈도수를 다루는 것이 핵심이다.

1000명의 점수를 읽으면서 배열[점수]에 해당하는 count를 올려주면,

해당 배열을 앞에서부터 count 같거나 크다면 갱신해주면 된다.

실수)
- 처음엔 빈도수가 같을 때 큰 수를 출력한다는 조건을 까맣게 잊고 있다가

   if(cnt < student[n]) => if(cnt <= student[n]) 로 수정하였다.

- 마지막으로 들어오는 입력이 테스트 케이스 번호 + 1000개의 숫자들이라서,

   scanf("%d", &test_case);를 삽입하였다.

구현)

#include<iostream>
using namespace std;
int N = 1000;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case) {
		scanf("%d", &test_case);
		int MODE = 0;
		int student[101] = {0,};
		int score = 0;
		for (int n = 0; n < N; n++) {
			scanf("%d", &score);
			++student[score];
		}
		int cnt = student[0];
		for (int n = 1; n < 101; n++) {
			if(cnt < student[n]) {
				MODE = n;	
				cnt = student[n];
			}
		}
		printf("#%d %d\n", test_case, MODE);
	}
	return 0;
}

배열과 index로 설계를 했지만 코딩을 하다보면 나도 모르게 헷갈리는 경우가 있는 것 같다.

그리고 개발자는 여러 경험들을 통해 만들어진 습관이나 편견을 조심 또 조심해야하는 것 같다.

모든 문제를 꼼꼼히 보고 기억하는 습관을 들이자!

입력) 

자연수 N(2 ≤ N ≤ 1,000,000)

각 날의 매매가를 나타내는 N개의 자연수들(10,000이하)

출력)

최대 이익을 출력

입, 출력 분석)

최대 이익 = 10,000이하의 자연수들 * 1,000,000개 

최악의 경우 10,000,000,000이 나온다.

예시 분석)

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

위 경우 2번째 날까지 사고(cost:2), 3번째 날에 팔았고(profit:3*2 - cost),

4번째 날에 사고(cost:1), 5번째 날에 팔았다면(profit:1*2 - cost),

이익은 (6-2)+(2-1) = 4+1 = 5이다.

위 경우  5번째 날까지 사고(cost:7), 6번째 날에 팔았다면(profit:4*5 - cost),

이익은 13이다.

핵심)

들어오는 수열에서 가장 큰 수를 찾아서,

'가장 큰 수 * 이전 수열까지의 개수' - '그 이전의 수열까지의 합'을 구하고,

이후 수열부터 이런 과정을 수열이 끝날 때까지 반복하면 된다.

핵심은 알았는데 1,000,000개의 수열에서 어떻게 제일 큰 수를 먼저 찾지..?
한참 고민하다가 힌트를 얻었다..ㅎ https://blog.naver.com/hongjg3229/221467996183

뒤에서부터 큰 수를 갱신해오면서 이익을 더해주니 금방 PASS 했다.

구현)

#include<iostream>
using namespace std;

int arr[1000000];
int N;

int main(int argc, char** argv){
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i){
			scanf("%d", &arr[i]);
		}
		long long profit = 0;
		int maxIdx = N-1;
		for (int idx = N-2; idx >= 0; --idx){
			if(arr[idx] < arr[maxIdx]) profit += arr[maxIdx] - arr[idx];
			else maxIdx = idx;
		}
		printf("#%d %lld\n", test_case, profit);
	}
	return 0;
}

상반기 끝나고 한 달 놀고 왔더니 머리가 단단히 굳은 것 같다....

앞으로 더 꾸준히 하면 된다! 아자아자!

Difficulty 단계별로 풀어보면서 공부를 해보려고 한다.

시작은 가볍게 D1 중 가장 추천을 많이 받은 문제로 열었다.

핵심) 짝수와 홀수의 개념이다.홀수는 2로 나눈 몫이 1인 수이고, 짝수는 2로 나눈 몫이 0인 수이다.

오늘은 무조건 스타트를 끊으리라 다짐했기에 보자마자 풀 수 있는 문제로 골랐지만,

내일부터는 D2 문제를 제대로 풀 것이다.

시작이 반이다! 할 수 있다!