ݺߣ

ݺߣShare a Scribd company logo
oj.uz 문제풀이2
amugona study 5회
전정완
2015-08-26
amugona2015
문제 4 - 로봇 심판의 님 게임
님 게임은 수학 문제에서 많이 사용되는 전략 보드 게임
무조건 컴퓨터가 이기는 님 게임
http://www.archimedes-lab.org/game_nim/play_nim_game.html
님 게임의 필승 전략은?
2
amugona2015
문제5 - 맛있는 과자
두 변의 길이가 a, b일때, N번 잘라 나온 𝟐 𝑵
개의 조각 중 K번째로 큰 한 조각
의 면적은?
3
a
b
N=0 N=1 N=2 N=3
amugona2015
문제5 - 맛있는 과자
입출력 예제 1
입력
3 4 1 1(빗변 아닌 두 변의 길이가 3, 4이고 1번 잘랐을 때 1번째로 큰 면적)
출력
1.345472366600
입출력 예제 2
입력
3 4 1 2
출력
0.770108221696
4
N=1
3
4
1번째로 큰 면적
2번째로 큰 면적
1.345472366600
0.770108221696
amugona2015
조건에 맞게 분배 후 각 상자 안에 든 정수들을 출력하라.
문제6 - 분배
5
2 𝐾
int 2 𝑁
단, 0 ≤≤
……
2 𝑁
2 𝐾
321
분배
각 상자에는 2 𝑁−𝐾
개의 서로 다른 정수가 들어 있게 됨
상자정수
amugona2015
입출력 예제
입력
2 1
출력
0 3
1 2
문제6 - 분배
6
0 1
21
2 3
22
2
1
각 상자에는 22−1개의 서로 다른 정수가 들어 있게 됨
한 상자 안에 들어있는 수들은 이진수로 나타냈을 때 1의 개수의 합이 동일한 것들임
상자
정수
0 3
1 2
amugona2015
문제10 - 최적의 능력 구성
능력들을 적절히 장착하여 얻을 수 있는 ‘피해량의 기대값’의 최대값은?
7
𝑝𝑖
𝑑𝑖
𝑝𝑖%의 확률로 능력 발동되어 𝑑𝑖만큼의 피해를 줌
(1-𝑝𝑖)의 확률로 능력 발동 X
𝑖번
𝑝1
𝑑1
1번
𝑝 𝑁
𝑑 𝑁
𝑁번
… …
능력 𝑁개
amugona2015
문제10 - 최적의 능력 구성
입출력 예제
입력
2(2개의 능력 장착, 다음 줄에는 각 능력들 정보)
(1번 능력이 발동될 확률)100 (피해량)1
(2번 능력이 발동될 확률)10 (피해량)20
출력
(저 두 능력들을 적절히 장착하여 얻을 수 있는 피해량 기댓값의 최대값)2.000000000000
8
10
20
2번
100
1
1번
능력 2개
-1번이 입힐 피해량의 기대값
1*1=1
-2번이 입힐 피해량의 기대값
0.1*20 =2
-최대값
2
amugona2015
문제10 - 최적의 능력 구성
입출력 예제 2
입력
3
12 10
11 11
10 12
출력
3.227420000000
9
?
amugona2015
문제10 - 최적의 능력 구성
기대값
각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 것
어떤 확률적 사건에 대한 평균
기대값 예
주사위를 1번 던질 때, 각 눈의 값이 나올 확률은 1/6
주사위값의 기대값 = 각 눈의 값에 그 확률을 곱한 값의 합
10
amugona2015
정리
초등학교 때 난 뭐 했는가?
중학교 때 난 뭘 했는가?
고등학교 때 난 도대체 무엇을 했는가?
그냥 보내버린 시간들이 지금 돌아와 날 괴롭게 함
원래 했어야 할 일을 지금부터라도 하는 게 좋을까
현재 위치에서 맞는 역할을 찾는 게 좋을까
11
amugona2015
스터디 6회 예정
http://jungol.co.kr/problemsetA.php?ctc=02
기초다지기 문제
실력키우기
~달팽이사각형 까지
12
끝
13

More Related Content

Featured (20)

2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing
Search Engine Journal
Storytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design ProcessStorytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design Process
Chiara Aliotta
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
OECD Directorate for Financial and Enterprise Affairs
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
SocialHRCamp
2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot
Marius Sescu
Everything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPTEverything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPT
Expeed Software
Product Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage EngineeringsProduct Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage Engineerings
Pixeldarts
How Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental HealthHow Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental Health
ThinkNow
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdfAI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
marketingartwork
Skeleton Culture Code
Skeleton Culture CodeSkeleton Culture Code
Skeleton Culture Code
Skeleton Technologies
PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024
Neil Kimberley
Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)
contently
How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024
Albert Qian
Social Media Marketing Trends 2024 // The Global Indie Insights
Social Media Marketing Trends 2024 // The Global Indie InsightsSocial Media Marketing Trends 2024 // The Global Indie Insights
Social Media Marketing Trends 2024 // The Global Indie Insights
Kurio // The Social Media Age(ncy)
Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024
Search Engine Journal
5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary
SpeakerHub
ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd
Clark Boyd
Getting into the tech field. what next
Getting into the tech field. what next Getting into the tech field. what next
Getting into the tech field. what next
Tessa Mero
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search IntentGoogle's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Lily Ray
How to have difficult conversations
How to have difficult conversations How to have difficult conversations
How to have difficult conversations
Rajiv Jayarajah, MAppComm, ACC
2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing
Search Engine Journal
Storytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design ProcessStorytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design Process
Chiara Aliotta
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
SocialHRCamp
2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot
Marius Sescu
Everything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPTEverything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPT
Expeed Software
Product Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage EngineeringsProduct Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage Engineerings
Pixeldarts
How Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental HealthHow Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental Health
ThinkNow
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdfAI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
marketingartwork
PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024
Neil Kimberley
Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)
contently
How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024
Albert Qian
Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024
Search Engine Journal
5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary
SpeakerHub
ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd
Clark Boyd
Getting into the tech field. what next
Getting into the tech field. what next Getting into the tech field. what next
Getting into the tech field. what next
Tessa Mero
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search IntentGoogle's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Lily Ray

Amugona 알고리즘 스터디5회

  • 1. oj.uz 문제풀이2 amugona study 5회 전정완 2015-08-26
  • 2. amugona2015 문제 4 - 로봇 심판의 님 게임 님 게임은 수학 문제에서 많이 사용되는 전략 보드 게임 무조건 컴퓨터가 이기는 님 게임 http://www.archimedes-lab.org/game_nim/play_nim_game.html 님 게임의 필승 전략은? 2
  • 3. amugona2015 문제5 - 맛있는 과자 두 변의 길이가 a, b일때, N번 잘라 나온 𝟐 𝑵 개의 조각 중 K번째로 큰 한 조각 의 면적은? 3 a b N=0 N=1 N=2 N=3
  • 4. amugona2015 문제5 - 맛있는 과자 입출력 예제 1 입력 3 4 1 1(빗변 아닌 두 변의 길이가 3, 4이고 1번 잘랐을 때 1번째로 큰 면적) 출력 1.345472366600 입출력 예제 2 입력 3 4 1 2 출력 0.770108221696 4 N=1 3 4 1번째로 큰 면적 2번째로 큰 면적 1.345472366600 0.770108221696
  • 5. amugona2015 조건에 맞게 분배 후 각 상자 안에 든 정수들을 출력하라. 문제6 - 분배 5 2 𝐾 int 2 𝑁 단, 0 ≤≤ …… 2 𝑁 2 𝐾 321 분배 각 상자에는 2 𝑁−𝐾 개의 서로 다른 정수가 들어 있게 됨 상자정수
  • 6. amugona2015 입출력 예제 입력 2 1 출력 0 3 1 2 문제6 - 분배 6 0 1 21 2 3 22 2 1 각 상자에는 22−1개의 서로 다른 정수가 들어 있게 됨 한 상자 안에 들어있는 수들은 이진수로 나타냈을 때 1의 개수의 합이 동일한 것들임 상자 정수 0 3 1 2
  • 7. amugona2015 문제10 - 최적의 능력 구성 능력들을 적절히 장착하여 얻을 수 있는 ‘피해량의 기대값’의 최대값은? 7 𝑝𝑖 𝑑𝑖 𝑝𝑖%의 확률로 능력 발동되어 𝑑𝑖만큼의 피해를 줌 (1-𝑝𝑖)의 확률로 능력 발동 X 𝑖번 𝑝1 𝑑1 1번 𝑝 𝑁 𝑑 𝑁 𝑁번 … … 능력 𝑁개
  • 8. amugona2015 문제10 - 최적의 능력 구성 입출력 예제 입력 2(2개의 능력 장착, 다음 줄에는 각 능력들 정보) (1번 능력이 발동될 확률)100 (피해량)1 (2번 능력이 발동될 확률)10 (피해량)20 출력 (저 두 능력들을 적절히 장착하여 얻을 수 있는 피해량 기댓값의 최대값)2.000000000000 8 10 20 2번 100 1 1번 능력 2개 -1번이 입힐 피해량의 기대값 1*1=1 -2번이 입힐 피해량의 기대값 0.1*20 =2 -최대값 2
  • 9. amugona2015 문제10 - 최적의 능력 구성 입출력 예제 2 입력 3 12 10 11 11 10 12 출력 3.227420000000 9 ?
  • 10. amugona2015 문제10 - 최적의 능력 구성 기대값 각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 것 어떤 확률적 사건에 대한 평균 기대값 예 주사위를 1번 던질 때, 각 눈의 값이 나올 확률은 1/6 주사위값의 기대값 = 각 눈의 값에 그 확률을 곱한 값의 합 10
  • 11. amugona2015 정리 초등학교 때 난 뭐 했는가? 중학교 때 난 뭘 했는가? 고등학교 때 난 도대체 무엇을 했는가? 그냥 보내버린 시간들이 지금 돌아와 날 괴롭게 함 원래 했어야 할 일을 지금부터라도 하는 게 좋을까 현재 위치에서 맞는 역할을 찾는 게 좋을까 11