문제 : https://www.acmicpc.net/problem/2493

스택 Stack

● 자료구조 스택을 이용하면 입력된 값을 역으로 순회하며 문제를 해결할 수 있다.

● 현재 스택이 비어있다면, 스택에 Push

● 스택에 값이 있다면, 스택의 top과 현재 값을 비교해 현재 값보다 스택의 top이 작다면 top에 해당하는 원소는 현재 값에 신호를 보내게 되므로 답을 갱신하고 스택을 pop하고 다시 이 과정을 반복한다.

( 답 갱신하는 과정을 위해 스택에 { 값, index } 를 같이 push 해준다. )

#include<iostream>
#include<stack>

using namespace std;

int N, list[500001], ans[500001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> list[i];

	stack<pair<int, int>> s;
	for (int i = N; i > 0; i--) {
		if (s.empty()) {
			s.push({ list[i], i });
		}
		else {
			while (s.top().first < list[i]) {
				ans[s.top().second] = i;
				s.pop();
				if (s.empty())
					break;
			}
			s.push({ list[i], i });
		}
	}
	for (int i = 1; i <= N; i++)
		cout << ans[i] << ' ';
	return 0;
}

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 17178 : 줄서기 - travelbeeee  (0) 2020.04.07
[BOJ] 2623 : 음악프로그램 - travelbeeee  (0) 2020.04.07
[BOJ] 14442 : 벽 부수고 이동하기 2 - travelbeeee  (0) 2020.04.06
[BOJ] 1005 : ACM Craft - travelbeeee  (0) 2020.04.03
[BOJ] 1516 : 게임 개발 - travelbeeee  (0) 2020.04.03

문제 : https://www.acmicpc.net/problem/14442

BFS 탐색

● 단순 BFS 탐색을 수행해서 (0, 0) 에서 ( N - 1, M - 1 ) 까지 이동이 가능한지 탐색하면 되는데 최대 K 개 만큼의 벽을 부셔도 되므로, visited 배열을 2차원이 아닌 3차원으로 visited[N][M][K] 로 만들어줘야합니다.

visited[X][Y][T] := (X, Y) 지점에 벽을 T개 부수고 도착한 적이 있는지 없는지.

● 큐에는 현재 내 위치 좌표와 몇 번 벽을 부수고 이동했는지, 이동 횟수 총 4가지 정보를 담습니다.

queue<pair<pair<int, int>, pair<int, int>> q;

● 내가 이동해야하는 곳이 '1' 벽이라면 현재 벽을 부순 횟수 + 1 이 K 이하인지 체크하고, visited[curX][curY][현재벽을부순횟수 + 1] 을 방문하지 않았다면 큐에 담아줍니다.

● 내가 이동해야하는 곳이 '0' 이라면 visited[curX][curY][현재벽을부순횟수] 를 방문하지 않았다면 큐에 담아줍니다.

#include<iostream>
#include<queue>

using namespace std;

int N, M, K, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool visited[1000][1000][10];
char map[1000][1001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	queue<pair<pair<int, int>, pair<int, int>>> q;
	visited[0][0][0] = 1;
	q.push({ {0, 0}, { 0, 0 } });

	bool flag = false;
	while (!q.empty()) {
		pair<pair<int, int>, pair<int, int>> temp = q.front();
		q.pop();
		int curX = temp.first.first, curY = temp.first.second;
		int curW = temp.second.first, curL = temp.second.second;
		
		if (curX == N - 1 && curY == M - 1) {
			cout << curL + 1 << '\n';
			flag = true;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nX = curX + dx[i], nY = curY + dy[i];
			if (!(0 <= nX && nX < N && 0 <= nY && nY < M))
				continue;
			if (map[nX][nY] == '0' && visited[nX][nY][curW] == 0) {
				visited[nX][nY][curW] = 1;
				q.push({ {nX, nY}, {curW, curL + 1} });
			}
			if (map[nX][nY] == '1' && visited[nX][nY][curW + 1] == 0 && curW + 1 <= K){
				visited[nX][nY][curW + 1] = 1;
				q.push({ {nX, nY}, {curW + 1, curL + 1} });
			}
		}
	}
	if (!flag)
		cout << -1 << '\n';
	return 0;
}

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 2623 : 음악프로그램 - travelbeeee  (0) 2020.04.07
[BOJ] 2493 : 탑 - travelbeeee  (0) 2020.04.06
[BOJ] 1005 : ACM Craft - travelbeeee  (0) 2020.04.03
[BOJ] 1516 : 게임 개발 - travelbeeee  (0) 2020.04.03
[BOJ] 1766 : 문제집 - travelbeeee  (0) 2020.04.03

안녕하세요, 여행벌입니다.

오늘은 웹 문서의 레이아웃을 짤 때 사용하는 div 태그에 대해서 포스팅해보겠습니다.

<div> 태그

 div 태그는 division 의 약자로 말 그대로 영역을 나누는 데 사용되는 태그입니다. 웹 페이지에서 논리적인 공간 구분을 정의하는 태그로 웹 사이트의 레이아웃을 만들 때 주로 사용합니다. 블록 라인 레벨 태그로 혼자 한 줄을 차지합니다.

예시 1) Header / Body / Footer

 div 태그를 이용해서 여러 가지 웹 사이트의 구조를 만들어보겠습니다.

 가장 심플한 웹 문서 구조는 Header / Body / Footer 3개의 영역으로 나눈 구조입니다. div 태그를 이용해서 나눠보도록 하겠습니다. 정확한 예시를 위해 CSS를 적용해서 예시를 다뤄보겠습니다.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        body{
            width : 100%;
            height : 500px;
            font-size : 3.5em;
            text-align : center;
        }
        .header{
            width : 100%;
            height : 20%;
            background-color : #C55A11;
        }
        .body{
            width : 100%;
            height : 60%;
            background-color : #F4B183;
        }
        .footer{
            width : 100%;
            height : 20%;
            background-color : #F8CBAD;
        }
    </style>
</head>
<body>
    <div class="header">Header영역</div>
    <div class="body">Body영역</div>
    <div class="footer">Footer영역</div>
</body>
</html>

 div 태그를 이용해서 Header, Body, Footer 영역을 설정하고 블록 레벨 태그이므로 width, height 속성을 적용해서 위의 예시와 같이 영역을 나눌 수 있습니다. 

예시 2)  Header / Body / LeftSideBar / RightSideBar / Footer 

 다음으로는 웹 문서 구조로 자주 쓰이는 Header / Body / LeftSideBar / RightSideBar / Footer 구조를 div 태그를 이용해서 나눠보겠습니다.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        body{
            width : 100%;
            height : 500px;
            font-size : 3.5em;
            text-align : center;
        }
        .header{
            width : 100%;
            height : 20%;
            background-color : #C55A11;
        }
        .body{
            display : flex;
            height : 60%;
        }
        .content{
            width : 60%;
            background-color: #F4B183;
        }
        .leftSideBar, .rightSideBar{
            width : 20%;
            background-color: #ED7D31;
        }
        .footer{
            width : 100%;
            height : 20%;
            background-color : #F8CBAD;
        }
    </style>
</head>
<body>
    <div class="header">Header영역</div>
    <div class="body">
        <div class="leftSideBar">LeftSideBar영역</div>
        <div class="content">Body영역</div>
        <div class="rightSideBar">RightSideBar영역</div>
    </div>
    <div class="footer">Footer영역</div>
</body>
</html>

이상으로 div 태그 포스팅을 마치도록 하겠습니다.

'Dev > HTML5 + CSS3' 카테고리의 다른 글

[HTML+CSS] 전체 선택자(*) 와 태그 선택자 - travelbeeee  (0) 2020.04.06
[HTML+CSS] 클래스(class) 와 아이디(id) 선택자 - travelbeeee  (0) 2020.04.06
[HTML+CSS] 드롭다운 목록 만들기 <select> 태그  (0) 2020.04.04
[HTML+CSS] 사용자의 입력을 받는 <input> 태그  (0) 2020.04.03
[HTML+CSS] 블록 레벨 요소 vs 인라인 레벨 요소 - travelbeeee  (0) 2020.04.02

안녕하세요, 여행벌입니다.

오늘은 드롭다운 목록을 만들 때 사용하는 select, optgroup, option 태그에 대해서 포스팅해보겠습니다.

<select> <option> 태그

 사용자가 내용을 입력하는 것이 아니라 여러 옵션 중에서 선택하도록 하고 싶을 때 드롭다운 목록을 사용합니다. 드롭다운 목록이란 클릭했을 때 옵션들이 요소 아래쪽으로 펼쳐지므로, 공간을 최소한으로 사용하면서 여러 옵션을 표시할 때 이용합니다.

 드롭다운 목록은 <select> 태그와 <option> 태그를 이용해 표시합니다. <select> 태그로 드롭다운 모곩의 시작과 끝을 표시하고 그 안에 <option> 태그를 사용해 원하는 항목들을 추가합니다.

<!-- 기본형 -->
<select 속성="속성값">
  <option value=""></option>
  <option value=""></option>
  <option value=""></option>
</select>

size 속성 ( <select> 태그 )

 화면에 표시될 드롭다운 메뉴의 항목 개수를 지정합니다.

<select size="5"> </select>

multiple 속성 ( <select> 태그 )

 브라우저 화면에 여러 개의 옵션이 함께 표시되면서 ctrl 키를 누른 상태로 드롭다운 메뉴에 있는 여러 항목을 선택할 수 있습니다.

<select multiple> </select>

value 속성 ( <option> 태그 )

 옵션을 선택했을 때 서버로 넘겨질 값을 지정합니다.

<option value="이값을서버로넘깁니다."></option>

selected 속성 ( <option> 태그 )

 화면에 표시될 때 기본으로 선택되어 있는 옵션을 지정합니다.

<option selected></option>

<optgroup> 태그 - 옵션끼리 묶기

 드롭다운 목록에서 여러 항목들을 몇 가지 그룹으로 묶어야 할 경우, <optgroup> 태그를 사용할 수 있습니다.

예시1) size와 selected 속성 사용

<!doctype html>
<html lang="ko">
<head>
	<meta charset="utf-8">
	<title> 웹 폼</title>
	<style>
		body {
			background-color: #fff;
		}

		form fieldset {
			margin-bottom: 25px;
		}

		form legend {
			font-size: 15px;
			font-weight: 600;
		}

		.reg {
			font-size: 14px;
			width: 110px;
			color: #390;
			font-weight: bold;
			float: left;
			text-align: right;
			margin-right: 10px;
		}

		form ul li {
			list-style: none;
			margin: 15px 0;
			font-size: 14px;
		}
	</style>
</head>

<body>
	<h1> 멋사 특강 신청</h1>
	<form>
		<fieldset>
			<legend>수강 신청인</legend>
			<ul>
				<li>
					<label class="reg" for="id">대학교</label>
					<input type="text" id="id" autofocus>
				</li>
				<li>
					<label class="reg" for="name">이름</label>
					<input type="text" id="name">
				</li>
				<li>
					<label class="reg" for="class">학과</label>
					<select size="3" id="class" multiple>
						<option value="math" selected>수학과</option>
						<option value="mechanic">기계공학과</option>
						<option value="indust">산업공학과</option>
						<option value="elec">전기전자공학과</option>
						<option value="computer">컴퓨터공학과</option>
						<option value="chemical">화학공학과</option>
					</select>
				</li>
			</ul>
		</fieldset>
	</form>
</body>

</html>

예시2) optgroup 사용

<!doctype html>
<html lang="ko">
<head>
	<meta charset="utf-8">
	<title> 웹 폼</title>
	<style>
		body {
			background-color: #fff;
		}

		form fieldset {
			margin-bottom: 25px;
		}

		form legend {
			font-size: 15px;
			font-weight: 600;
		}

		.reg {
			font-size: 14px;
			width: 110px;
			color: #390;
			font-weight: bold;
			float: left;
			text-align: right;
			margin-right: 10px;
		}

		form ul li {
			list-style: none;
			margin: 15px 0;
			font-size: 14px;
		}
	</style>
</head>

<body>
	<h1> 멋사 특강 신청</h1>
	<form>
		<fieldset>
			<legend>수강 신청인</legend>
			<ul>
				<li>
					<label class="reg" for="id">대학교</label>
					<input type="text" id="id" autofocus>
				</li>
				<li>
					<label class="reg" for="name">이름</label>
					<input type="text" id="name">
				</li>
				<li>
					<label class="reg" for="class">학과</label>
					<select id="class">
						<optgroup label="공과대학">
							<option value="archi">건축공학과</option>
							<option value="mechanic">기계공학과</option>
							<option value="indust">산업공학과</option>
							<option value="elec">전기전자공학과</option>
							<option value="computer">컴퓨터공학과</option>
							<option value="chemical">화학공학과</option>
						</optgroup>
						<optgroup label="인문대학">
							<option value="history">사학과</option>
							<option value="lang">어문학부</option>
							<option value="philo">철학</option>
						</optgroup>
					</select>
				</li>
			</ul>
		</fieldset>
	</form>
</body>
</html>

드롭다운 목록을 프론트 개발 시 자주 사용되므로 꼭 잘 익혀두세요!

이상으로 포스팅을 마치도록 하겠습니다 :)

'Dev > HTML5 + CSS3' 카테고리의 다른 글

[HTML+CSS] 클래스(class) 와 아이디(id) 선택자 - travelbeeee  (0) 2020.04.06
[HTML+CSS] 레이아웃을 잡아주는 <div> 태그  (0) 2020.04.05
[HTML+CSS] 사용자의 입력을 받는 <input> 태그  (0) 2020.04.03
[HTML+CSS] 블록 레벨 요소 vs 인라인 레벨 요소 - travelbeeee  (0) 2020.04.02
[HTML+CSS] HTML의 요소 구조 - travelbeeee  (0) 2020.04.02

+ Recent posts

티스토리툴바