ZeroWiki - User contributions [en]

1R/2015 09 12

2016-09-12T15:17:30Z

223.62.229.32:

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/2250|트리의 높이와 너비]

= 참가자 =
* 15이원준
= 코드 =
== 15이원준 ==
#include<iostream>

using namespace std;

int level[20000][2] = {0, };
int arr[20000][2];
int ex[20000][2] = { 0, };
int myNum[20000] = {0, };
int maxDep = 0;
int checkNum(int child){
if(arr[child][0] != -1){
ex[child][0] = checkNum(arr[child][0]);
}
if(arr[child][1] != -1){
ex[child][1] = checkNum(arr[child][1]);
}
return ex[child][0] + ex[child][1] + 1;
}
void fill(int now){
if(arr[now][0] != -1){
myNum[arr[now][0]] = myNum[now] - ex[arr[now][0]][1] - 1;
fill(arr[now][0]);
}
if(arr[now][1] != -1){
myNum[arr[now][1]] = myNum[now] + ex[arr[now][1]][0] + 1;
fill(arr[now][1]);
}
}
void answer(int dep, int now){
if(dep > maxDep){
maxDep = dep;
}
if(arr[now][0] != -1){
if(myNum[arr[now][0]] < level[dep][0]){
level[dep][0] = myNum[arr[now][0]];
}
if(myNum[arr[now][0]] > level[dep][1]){
level[dep][1] = myNum[arr[now][0]];
}
answer(dep + 1, arr[now][0]);
}
if(arr[now][1] != -1){
if(myNum[arr[now][1]] < level[dep][0]){
level[dep][0] = myNum[arr[now][1]];
}
if(myNum[arr[now][1]] > level[dep][1]){
level[dep][1] = myNum[arr[now][1]];
}
answer(dep + 1, arr[now][1]);
}
}

int main(){
int N, root = -1;
cin>>N;
for(int i = 1; i<=N; i++){
level[i][0] = N+1;
level[i][1] = -1;
ex[i][0] = 0;
ex[i][1] = 0;
int a;
cin>> a;
cin>> arr[a][0] >> arr[a][1];
arr[arr[a][0]][0] = -1;
arr[arr[a][0]][1] = -1;
arr[arr[a][1]][0] = -1;
arr[arr[a][1]][1] = -1;
if(arr[a][0] == root || arr[a][1] == root || root == -1){
root = a;
}
}
ex[root][0] = checkNum(arr[root][0]);
ex[root][1] = checkNum(arr[root][1]);
myNum[root] = ex[root][0] + 1;
fill(root);
level[1][0] = myNum[root];
level[1][1] = myNum[root];
answer(2, root);
int max = 0, bigLevel = 0;
for(int i = 1; i<maxDep; i++){
int tmp = level[i][1] - level[i][0] + 1;
if(max < tmp){
bigLevel = i;
max = tmp;
}
}
cout<< bigLevel << " " << max;
}
== 박인서 ==
#include <iostream>
#define LEN 10001

using namespace std;
int tree[LEN][2],maxgap[LEN],mingap[LEN];
int cnt=0,maxdep=0;

//왼쪽자식->자기자신->오른쪽 자식 순으로 cnt를 세가며 위치를 지정(너비도 같이 생각)
void solve(int node, int depth)
{
//초기화 및 maxdep 설정
if(depth>maxdep) maxdep=depth,mingap[depth]=1001,maxgap[depth]=-1;
if(tree[node][0]!=-1) solve(tree[node][0], depth + 1);//왼쪽 자식 호출
cnt++;//node 1개 증가
//maxgap,mingap 설정
if(mingap[depth]>cnt) mingap[depth]=cnt;
if(maxgap[depth]<cnt) maxgap[depth]=cnt;
if(tree[node][1]!=-1) solve(tree[node][1], depth + 1);//오른쪽 자식 호출
}

int main()
{
int a, i, num, res=-1, index=0;
//입력
cin>>num;
for(i=1; i<=num; i++)
{
cin>>a;
cin>>tree[a][0]>>tree[a][1];
}
//함수 번호 매기기
solve(1, 1);
//너비가 가장 큰 것 찾기
for(i=1; i<=maxdep; i++)
if(res<maxgap[i]-mingap[i]) res=maxgap[i]-mingap[i],index=i;
//출력
cout<<index<<" "<<res+1<<'\n';
return 0;
}

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==
# 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
== 박인서 ==
== 곽정흠 ==

1R/2015 09 12

2016-09-12T15:12:03Z

223.62.229.32:

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/2250|트리의 높이와 너비]

= 참가자 =
* 15이원준
= 코드 =
== 15이원준 ==
#include<iostream>

using namespace std;

int level[20000][2] = {0, };
int arr[20000][2];
int ex[20000][2] = { 0, };
int myNum[20000] = {0, };
int maxDep = 0;
int checkNum(int child){
if(arr[child][0] != -1){
ex[child][0] = checkNum(arr[child][0]);
}
if(arr[child][1] != -1){
ex[child][1] = checkNum(arr[child][1]);
}
return ex[child][0] + ex[child][1] + 1;
}
void fill(int now){
if(arr[now][0] != -1){
myNum[arr[now][0]] = myNum[now] - ex[arr[now][0]][1] - 1;
fill(arr[now][0]);
}
if(arr[now][1] != -1){
myNum[arr[now][1]] = myNum[now] + ex[arr[now][1]][0] + 1;
fill(arr[now][1]);
}
}
void answer(int dep, int now){
if(dep > maxDep){
maxDep = dep;
}
if(arr[now][0] != -1){
if(myNum[arr[now][0]] < level[dep][0]){
level[dep][0] = myNum[arr[now][0]];
}
if(myNum[arr[now][0]] > level[dep][1]){
level[dep][1] = myNum[arr[now][0]];
}
answer(dep + 1, arr[now][0]);
}
if(arr[now][1] != -1){
if(myNum[arr[now][1]] < level[dep][0]){
level[dep][0] = myNum[arr[now][1]];
}
if(myNum[arr[now][1]] > level[dep][1]){
level[dep][1] = myNum[arr[now][1]];
}
answer(dep + 1, arr[now][1]);
}
}

int main(){
int N, root = -1;
cin>>N;
for(int i = 1; i<=N; i++){
level[i][0] = N+1;
level[i][1] = -1;
ex[i][0] = 0;
ex[i][1] = 0;
int a;
cin>> a;
cin>> arr[a][0] >> arr[a][1];
arr[arr[a][0]][0] = -1;
arr[arr[a][0]][1] = -1;
arr[arr[a][1]][0] = -1;
arr[arr[a][1]][1] = -1;
if(arr[a][0] == root || arr[a][1] == root || root == -1){
root = a;
}
}
ex[root][0] = checkNum(arr[root][0]);
ex[root][1] = checkNum(arr[root][1]);
myNum[root] = ex[root][0] + 1;
fill(root);
level[1][0] = myNum[root];
level[1][1] = myNum[root];
answer(2, root);
int max = 0, bigLevel = 0;
for(int i = 1; i<maxDep; i++){
int tmp = level[i][1] - level[i][0] + 1;
if(max < tmp){
bigLevel = i;
max = tmp;
}
}
cout<< bigLevel << " " << max;
}
== 박인서 ==
#include <iostream>
#define LEN 1001

using namespace std;
int tree[LEN][2],maxgap[LEN],mingap[LEN];
int cnt=0,maxdep=0;

//왼쪽자식->자기자신->오른쪽 자식 순으로 cnt를 세가며 위치를 지정(너비도 같이 생각)
void solve(int node, int depth)
{
//초기화 및 maxdep 설정
if(depth>maxdep) maxdep=depth,mingap[depth]=1001,maxgap[depth]=-1;
if(tree[node][0]!=-1) solve(tree[node][0], depth + 1);//왼쪽 자식 호출
cnt++;//node 1개 증가
//maxgap,mingap 설정
if(mingap[depth]>cnt) mingap[depth]=cnt;
if(maxgap[depth]<cnt) maxgap[depth]=cnt;
if(tree[node][1]!=-1) solve(tree[node][1], depth + 1);//오른쪽 자식 호출
}

int main()
{
int a, i, num, res=-1, index=0;
//입력
cin>>num;
for(i=1; i<=num; i++)
{
cin>>a;
cin>>tree[a][0]>>tree[a][1];
}
//함수 번호 매기기
solve(1, 1);
//너비가 가장 큰 것 찾기
for(i=1; i<=maxdep; i++)
if(res<maxgap[i]-mingap[i]) res=maxgap[i]-mingap[i],index=i;
//출력
cout<<index<<" "<<res+1<<'\n';
return 0;
}

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==
# 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
== 박인서 ==
== 곽정흠 ==

1R

2016-09-12T15:01:15Z

223.62.229.32:

# 1일 1알고리즘 문제 ~~1A여야 되지만 넘어갑시다~~
# ~~알고리즘 대회 1라운드라도 통과하자~~

__TOC__
= 내용 =
방학동안 잉여로움을 즐기는 것도 잠시 '''내가 이렇게 살아도 되나?''' 라는걸 느꼈습니다. 그래서 '''하루에 한 알고리즘 문제'''라도 풀어서 '''"내가 오늘도 무언가를 했다"'''라는 '''자기 위로'''를 하는 '''스터디'''

= 방학 이전 =
== 계획 ==
방학동안 코드그라운드의 연습문제를 난이도, 번호 순으로('''easy난이도 ,작은 번호 부터 시작''') 한 문제 씩 풀 예정입니다. (이후 문제가 부족하거나 풀 수 없는 문제만 남으면 다른 사이트 문제를 풀 예정)

== 진행 방식 ==
월~금 시간은 그 날 자신이 원하는 시간
각자 '''온라인'''으로 문제를 풀고 그날의 wiki페이지에 자신의 코드를 공유한다.(코드에 주석을 달아 주면 좋음)
아무리 풀어도 모르겠다면 이미 푼 사람의 코드를 몰래 보지말고 이름만 보고 개인 적으로 힌트를 구한다.
'''오프라인으로 따로 만나지는 않을 것입니다.(아마도...)'''

= 방학 이후 =
== 계획 ==
ACM ICPC 2016 본선 진출을 위해서 하루에 '''적어도''' 1문제씩 푸는 것을 목표로 달립니다.

== 진행 방식 ==
매일 정해진 가이드대로 문제를 푼다.(추석때도 안 쉴 예정)

= 참가자 =
* [[15이원준]], [[박인서]] - 재합류합니다
* [[황창재]] - 2016.07.10부터 합류, 방학 이후 빠짐
* [[곽정흠]] - 2016.09.09부터 합류

= 진행 사항 =
* 코드 그라운드
* 백준 Online Judge

= 진행 사항 =
* 코드 그라운드
{| class="wikitable"
|-
| 난이도
| 번호
| 문제명
| 코드 공유
|-
| ★
| 1
| [https://www.codeground.org/practice/practiceProbView.do?probId=1|숫자 골라내기]
| [[1R/2016_07_04]]
|-
| ★
| 2
| [https://www.codeground.org/practice/practiceProbView.do?probId=2|프로그래밍 경진대회]
| [[1R/2016_07_05]]
|-
| ★
| 3
| [https://www.codeground.org/practice/practiceProbView.do?probId=3|시험 공부]
| [[1R/2016_07_06]]
|-
| ★
| 4
| [https://www.codeground.org/practice/practiceProbView.do?probId=6|미궁 속의 방]
| [[1R/2016_07_07]]
|-
| ★
| 5
| [https://www.codeground.org/practice/practiceProbView.do?probId=11|개구리 뛰기]
| [[1R/2016_07_08]]
|-
| ★
| 6
| [https://www.codeground.org/practice/practiceProbView.do?probId=12|방속의 거울]
| [[1R/2016_07_11]]
|-
| ★★
| 7
| [https://www.codeground.org/practice/practiceProbView.do?probId=5|이항계수의 합]
| [[1R/2016_07_12]]
|-
| ★★
| 8
| [https://www.codeground.org/practice/practiceProbView.do?probId=7|좋은 수]
| [[1R/2016_07_13]]
|-
|
|
| SCPC 2차 예선 관계로 채점을 할 수 없어서 쉽니다.
| 1R/2016_07_14
|}
* 백준 Online Judge
{| class="wikitable"
|-
| 날짜
| 문제 번호
| 문제명
| 코드 공유
|-
| rowspan="2" | 9/9, 9/10
| 1260
| [https://www.acmicpc.net/problem/1260|DFS와 BFS]
| rowspan="2" | [[1R/워밍업문제]]
|-
| 1965
| [https://www.acmicpc.net/problem/1965|상자 넣기]
|-
| 9/11
| 1932
| [https://www.acmicpc.net/problem/1932|숫자 삼각형]
| [[1R/2016_09_11]]
|-
| 9/12
| 2250
| [https://www.acmicpc.net/problem/2250|트리의 높이와 너비]
| [[1R/2015_09_12]]
|-
| 9/13
| 1238
| [https://www.acmicpc.net/problem/1238|파티]
| [[1R/2016_09_13]]
|}

= 코멘트 =