solved.ac
덤프버전 : (♥ 0)
1. 개요[편집]
알고리즘 트레이닝 사이트 Baekjoon Online Judge(BOJ)에 수록된 문제들의 난이도를 측정하는 커뮤니티 프로젝트. 해결한 문제들을 바탕으로 사용자의 티어를 계산하고, 학습의 게임화를 통해 알고리즘 문제해결 학습 동기를 부여한다. 2020년에 서강대학교 컴퓨터공학부 학생인 박수현(shiftpsh)에 의해 개설되었다.
2020년 이전의 BOJ에는 '난이도'라는 개념이 존재하지 않았다. 문제 번호가 난이도 순서가 아닌 BOJ의 특성상 초심자들이 좌절하는 일이 잦았고, 기존 알고리즘 학습자 입장에서도 연습문제를 고르기 어려웠다는 단점이 있었다. 이런 단점을 거의 완벽하게 보완하여 유저들의 찬사를 받고 있다.
BOJ와 연동하여 해결한 문제에 난이도 의견을 제출할 수 있다. 일정 티어 이상이 되면 난이도 의견이 문제 난이도에 반영되며[요구_티어], 모인 난이도 의견은 공식을 거쳐 문제의 난이도가 된다. 이렇게 정해진 문제 난이도는 solved.ac에서 확인할 수 있으며, BOJ에서도 추가 연동 과정을 거치면 확인할 수 있다.
프로그래밍 문제들에 대규모 커뮤니티의 집단지성을 이용해 난이도를 매기는 시도는 국내에서 이 사이트가 최초다.
2. AC 레이팅[편집]
해결한 문제들을 바탕으로 사용자의 티어를 계산해 주는 시스템이 있다. 해결한 문제 수로 랭킹을 산정하는 BOJ와 다르게 어느 순간부터는 쉬운 문제로 레이팅이 올라가지 않으며, 어려운 문제를 해결해야 레이팅이 올라가므로 어려운 문제를 해결할 동기를 마련해 준다.
레이팅 시스템인 'AC 레이팅'으로 티어를 결정한다. AC 레이팅은 다음 요소들의 합이다.
- 자신이 해결한 문제들의 난이도 합 - 어려운 순으로 정렬해 최대 100개까지 (최대 3,000[4])
- Bronze V는 1점, Bronze IV는 2점, ..., Ruby I는 30점이다.
- 일부 문제는 레이팅을 주지 않는다.[3]
- CLASS에 따른 보너스 (최대 250)
- 푼 문제 수에 따른 보너스 - (175 (1 − 0.995푼 문제 수))를 반올림 (최대 175)
- 기여 수에 따른 보너스 - (25 (1 − 0.9기여 수))를 반올림 (최대 25)
푼 문제 수 보너스는 1,169문제를 풀면 만점이고, 기여 수 보너스는 38문제에 기여하면 만점이다.
[보너스 자세히 보기]
CLASS에 따른 보너스는 아래와 같다.
2.1. 티어[편집]
달성한 레이팅에 따라 Unrated부터 Master까지의 티어가 결정된다. 레이팅에 따른 티어 컷은 아래와 같다.
달성 인원 수는 2023년 5월 8일 기준이다.
2.2. 경험치[편집]
2021년 2월 28일까지는 경험치로 티어를 결정했었다. 2023년 6월 5일 시즌 3 업데이트로 경험치는 완전히 삭제되었다.
6월 5일 이전에는 해결한 문제의 난이도에 따라 다음과 같은 경험치를 획득할 수 있었다.
3. 태그[편집]
유저들에 의해 분류되는 태그들이다. 문제를 해결하는 데 사용하는 알고리즘과 자료 구조, 방법론 등으로 분류되어 있다. 하위 분류의 태그를 가진 문제들은 모두 상위 분류의 태그를 갖지만, 상위 태그를 가진 문제들은 하위 태그로 반드시 분류될 필요는 없다. 하나의 태그가 두 개 이상의 상위 분류를 가질 수도 있다.
3.1. 태그 레이팅[편집]
AC 레이팅과 마찬가지로 태그에도 레이팅이 붙는다.
- 자신이 해결한 문제들의 난이도 합 - 어려운 순으로 정렬해 최대 50개까지 (최대 3,000)
- Bronze V는 2점, Bronze IV는 4점, ..., Ruby I는 60점이다.
- 일부 문제는 레이팅을 주지 않는다.[19]
- 푼 문제 수에 따른 보너스 - (200 (1 − 0.99푼 문제 수))를 반올림 (최대 200)
푼 문제 수 보너스는 597문제를 풀면 만점이다.
[보너스 자세히 보기]
태그 레이팅은 500문제 이상 수록된 태그에 부여되며, 그 중에서 프로필에 표시되는 8개의 태그는 볼드체로 표시했다. 문제 수와 만점은 2023년 9월 10일 기준.
3.2. 태그 목록[편집]
- 수학
- 구현
- 시뮬레이션
- 다이나믹 프로그래밍
- 트리에서의 다이나믹 프로그래밍
- 비트필드를 이용한 다이나믹 프로그래밍
- 분할 정복을 사용한 최적화
- 커넥션 프로파일을 이용한 다이나믹 프로그래밍
- 덱을 이용한 다이나믹 프로그래밍
- 함수 개형을 이용한 최적화
- 커누스 최적화
- 단조 큐를 이용한 최적화
- 그래프 이론
- 자료구조
- 문자열
- 파싱
- UTF-8 입력 처리
- KMP
- 라빈-카프
- 접미사 배열과 lcp 배열
- 정규 표현식
- 매내처
- Z
- 로프
- 파싱
- 그리디 알고리즘
- 브루트포스 알고리즘
- 정렬
- 기하학
- 피타고라스 정리
- 볼록 껍질
- 3차원 기하학
- 4차원 이상의 기하학
- 선분 교차 판정
- 다각형의 넓이
- 볼록 다각형 내부의 점 판정
- 오일러 지표
- 회전하는 캘리퍼스
- 오목 다각형 내부의 점 판정
- 보로노이 다이어그램
- 최소 외접원
- 반평면 교집합
- 델로네 삼각분할
- 픽의 정리
- 트리
- 이분 탐색
- 병렬 이분 탐색
- Aliens 트릭
- 애드 혹
- 구성적
- 많은 조건 분기
- 비트마스킹
- 백트래킹
- 커누스 X
- 분할 정복
- 히르쉬버그
- 스위핑
- 두 포인터
- 최대 유량
- 최소 비용 최대 유량
- 최대 유량 최소 컷 정리
- 서큘레이션
- 게임 이론
- 스프라그-그런디 정리
- 임의 정밀도 / 큰 수 연산
- 오프라인 쿼리
- Mo's
- 오프라인 동적 연결성 판정
- 재귀
- 매개 변수 탐색
- 배낭 문제
- 런타임 전의 전처리
- 좌표 압축
- 해싱
- 포함 배제의 원리
- 작은 집합에서 큰 집합으로 합치는 테크닉
- 무작위화
- 중간에서 만나기
- 볼록 껍질을 이용한 최적화
- 제곱근 분할법
- 슬라이딩 윈도우
- 물리학
- 외판원 순회 문제
- 가장 긴 증가하는 부분 수열: O(n log n)
- 순열 사이클 분할
- 비트 집합
- 삼분 탐색
- 휴리스틱
- 이중 연결 요소
- 벌래캠프-매시
- 비둘기집 원리
- 홀의 결혼 정리
- 인터프리터
- 헝가리안
- 선형 계획법
- 매트로이드
- 일반적인 매칭
- 키타마사
- 쌍대성
- 담금질 기법
- 안정 결혼 문제
- 베이즈 정리
- 계산 이론
- 생성 함수
- 춤추는 링크
- 보이어-무어 다수결 투표
- 상수 최적화
- 차분 공격
4. 새싹 티어와 새싹 문제[편집]
solved.ac가 프로그래밍 문제해결 입문을 위해 큐레이션한 문제들이다. 프로그래밍 언어를 새로 시작할 때 풀어보기 좋은 문제들로 구성되어 있다. 입문자라면 CLASS 1에 도전하기 전에 풀고 넘어가면 좋을 것이다.
새싹 티어 문제들을 해결하면 Bronze V의 레이팅을 받으며, 일부 문제들은 CLASS 1과 겹친다.
5. CLASS[편집]
solved.ac에서 수준별로 엄선한 문제로, 2022년 8월 현재 CLASS 10까지 존재한다. 대부분 자료구조/알고리즘 기본 문제들과 비슷한 수준에서 도전해 보면 좋을 만한 문제들로 구성되어 있다.
CLASS 1은 초보자들이 따라하기 쉬운 문제들로 구성되어 있으나, CLASS 3만 가도 머리를 싸매야 하는 문제들이 나온다. 주어진 개수만큼 문제를 풀면 해당 CLASS를 획득할 수 있으며, 에센셜 태그가 붙은 문제를 다 풀면 은장이, 모든 문제를 풀면 금장이 추가로 붙는다.
CLASS 9부터는 이전 CLASS를 통과해야 취득할 수 있다.
일반적인 실무를 위해서는 CLASS 3까지만 획득해도 충분하며, CLASS 4까지 취득하는 것은 구현력에 도움이 될 수 있다. 프로그래밍 대회에 등장하는 기초 알고리즘들을 배우고 싶다면 CLASS 5부터 차근차근 올라가보는 것도 도움이 된다.
아래 표는 각 CLASS에서 새롭게 다루는 내용들을 정리한 것이다. 이 내용들에 추가로 이전 CLASS까지들에서 다뤘던 내용이 심화된 문제들로 구성되어 있다.
6. 다음 업데이트 예측[편집]
오직 이슈 트래커로만 보고 예측했으며, 부정확할 수 있습니다.
길라잡이 기능 추가
기여자가 한 명일 때 난이도를 5단계 이상 차이나게 수정하는 경우 의견 강제 작성 시스템이 동작하는 버그를 수정.
문제 스크린 GUI 업그레이드
주간/일간 퀘스트(!!!) [21]
태그별 랭킹
배경 뽑기
승급 축하 메시지/이펙트
새싹 올솔브 배경
시즌 3 업데이트 이슈에 들어간 배경은 무대 위의 별.
5월 10일 기준으로 경험치 삭제 리서치, 알림 기능이 들어가 있다.
7. 프로필 꾸미기 요소[편집]
자세한 내용은 solved.ac/프로필 꾸미기 요소 문서를 참고하십시오. 8. 기여[편집]
solved.ac 최초 연동 후 14일이 지나면 문제에 난이도 의견을 제출할 수 있다. Platinum V 티어가 된 후부터 남긴 기여는 문제의 난이도에 실제로 반영된다.
다만, 태그 기여의 경우는 Platinum V 이상이 되지 않아도 문제에 반영된다.
9. 이벤트[편집]
비정기적으로 문제 해결 이벤트가 열린다.
문제를 많이 풀면 빼빼로를 모을 수 있고, 순위에 따라 실제 빼빼로를 얻을 수 있다. 첫 이벤트이자 오로지 문제 수로만 순위가 결정되었던 마지막 이벤트다.
【자세한 이벤트 내용】 - 문제를 풀면서 '재료'를 획득한다.다크 초콜릿 × 3 + 막대 과자 → 빼빼로
브론즈 5에서 브론즈 1 레이팅의 문제를 풀면 다크 초콜렛 x1을 준다.
실버 5에서 실버 1 레이팅의 문제를 풀면 화이트 초콜렛 x1을 준다.
골드 5에서 골드 1 레이팅의 문제를 풀면 막대 과자 x1[1]을 준다.
플래티넘 5에서 다이아몬드 1 레이팅의 문제를 풀면 민트 초콜렛 x1을 준다.
루비 레이팅의 문제를 풀면 루비 초콜렛 x1을 준다.
화이트 초콜릿 × 3 + 막대 과자 → 쿠키&크림 빼빼로
민트 초콜릿 × 3 + 막대 과자 → 민트초코 빼빼로
루비 초콜릿 × 3 + 막대 과자 → 루비 빼빼로
[1] 빼빼로 재료가 많아도 이게 없으면 못 만든다.
- 여름 엽서 꾸미기: 2022년 6월 26일 오전 6시 - 8월 1일 오전 6시 링크
문제를 풀고 스티커를 받아, 이 스티커의 조합에 따른 숨겨진 조건을 만족해 높은 점수를 달성해야 한다.
문제를 풀면 난이도에 따라 최대 점수가 정해진 카드를 한 장 받을 수 있다. 카드를 뒤집으면 1부터 최대 점수 사이의 랜덤한 수가 하나 나오고, 이 수들의 합을 10000점에 가깝게 만들어야 한다. 10000점이 넘으면 버스트되어 처음부터 다시 시작해야 한다.
- 나중에 이 게임의 일반화된 버전이 2022 서강대학교 프로그래밍 대회 문제로 출제되었다. 이벤트에서 9900점을 넘기 위한 최적 전략은 카드를 44.5장 사용한다. BOJ 26096
- 트리 꾸미기: 2022년 12월 16일 오전 6시 - 12월 26일 오전 6시 링크
자작 보드게임 동아리의 트리 만들기 보드게임 룰을 활용한 이벤트를 진행하였다. 크리스마스 트리와 자료구조의 트리가 이름이 같은 것에서 착안한 이벤트다.
또한 국제 프로그래밍 대회 ICPC와 IOI에 진출한 국내 참가자들을 응원하는 이벤트도 열린다. 대회 종료 시각까지 응원 메시지를 남길 수 있으며, 응원 메시지를 남기면 프로필 배경을 준다.
- ICPC 2021 Moscow: 2021년 10월 5일까지 링크
- IOI 2022 Indonesia: 2022년 8월 12일까지 링크
- ICPC 2022 Dhaka: 2022년 11월 10일까지 링크
10. 아이템[편집]
아이템은 별조각, 코인, 알쏭달쏭 스트릭 그래프 염색 컬러칩, 스트릭 프리즈, 한별 이모티콘이 있다.
오전 5:30분 부터 오전 6:30분 까진 운영을 안하니 유의하자.
10.1. 아이템 설명 & 획득 경로[편집]
별조각 - 많이 모아서 코인, 배경을 살 수 있다
파일:sparkle-small.svg
획득 방법
1. 문제 풀기
2. 코인에서 별조각으로 환산 (환율이 매일 변동된다.)
3. 이벤트
4. solved.ac 최초 연동, 코인 최초 획득
코인 - 대략 별조각 1400 ~ 1700개의 가치를 가지고 있다. 거의 모든 걸 살 때 필요하다.
파일:coin-small.svg
획득 방법
1. 환산
스트릭 프리즈 - 미리 장착해 두면 어제 문제 푸는 걸 잊었더라도 스트릭이 깨지지 않는다. 단, 스트릭 길이가 늘어나지는 않는다. 인벤토리에서 장착해서 사용.
파일:freeze-small-simple.svg
획득 방법
1. 0.99 코인으로 샵에서 획득 가능
알쏭달쏭 스트릭 그래프 염색 컬러칩 - 사용하면 스트릭 그래프 색상을 랜덤으로 바꾼다.
파일:grass-color-randomizer.svg
획득 방법
1. 0.15 코인으로 샵에서 획득
한별 이모티콘 팩 - 사용하면 기여 창에 사용할 수 있는 한별 이모티콘을 15개 중 랜덤으로 얻는다.
획득 방법
1. 0.20 코인으로 샵에서 획득
뽑았을 때 모습 - 파일:스크린샷 2023-04-08 오후 9.49.17.png
스트릭 리페어 - 사용하면 깨진 스트릭을 복구한다.
파일:repair-small-simple.svg
획득 방법 - 4월 8일 쯤에 서버 이슈 때문에 모든 유저의 스트릭이 초기화돼서 2개를 주었다.
[1] 알파 버전 2019년 6월 6일, 베타 버전 2019년 7월 13일[기준] A B C 2023년 5월 8일[2] Bronze V 이상만을 포함[요구_티어] Platinum V를 넘어가면 된다[3] 다른 문제랑 완전히 똑같은 문제, 번외 문제 등등[4] 문제들의 난이도 합의 경우 Ruby I 문제가 100개가 되지 않기 때문에 2023-04-21 기준 사실상의 이론치는 2,867이다.[5] Bronze V 이상 기준[6] Bronze V 이상 기준[7] 사이트 기준 (Bronze V를 상위 100%로 둠)[8] 1문제 이상을 푼 인원은 112,520[9] Bronze V 문제를 17개 풀면 달성된다. (문제 레이팅 +17, 푼 문제 보너스 +14)[10] 보통 50문제를 풀고(+39), CLASS 1(+25)를 얻고 해결한 문제들의 난이도 평균을 Bronze III(+150)로 맞추면 된다.[11] 보통 100문제를 풀고(+69), CLASS 3(+100)를 얻고 상위 100문제 평균을 Silver IV(+700)로 맞추면 된다.[12] 보통 400문제를 풀고(+151), CLASS 4(+150)를 얻고 상위 100문제 평균을 Gold III(+1,300)로 맞추면 된다.[13] 보통 푼 문제 수 보너스(+175)와 기여 보너스(+25)를 전부 챙기고, CLASS 5(+200)를 얻고 상위 100문제 평균을 Platinum III(+1,800)로 맞추면 된다.[14] 보통 푼 문제 수 보너스(+175)와 기여 보너스(+25)를 전부 챙기고, CLASS 8(+230)을 얻고 상위 100문제 평균을 Diamond III~IV(+2,270)로 맞추면 된다.[15] 보통 푼 문제 수 보너스(+175)와 기여 보너스(+25)를 전부 챙기고, CLASS 10(+250)을 얻고 상위 100문제 평균을 Diamond I~Ruby V(+2,550)로 맞추면 된다.[16] 번외 문제, 기타 모종의 사유로 인해 난이도를 매길 수 없는 문제들. Solved.ac에서도 이 난이도를 제안할 수 있으며 이 제안이 많아질 경우 운영자 측에서 이 난이도를 매기게 된다.[17] 아직 레이팅되지 않은 경우.[18] 0으로 나눌 수 없기 때문이다.[19] 다른 문제랑 완전히 똑같은 문제, 번외 문제 등등[20] 일반적인 방법으로 입력을 받으면 상당히 느리기 때문에 올바른 알고리즘을 구현해도 시간 초과를 받을 수 있다. 이 문제에서는 프로그래밍 문제에서 사용해야 하는 입출력 방법을 소개한다.[21] 예시 내용 예측 - A/B문제를 아희 언어로 푼다. (+350 별조각),자기 레이팅 이상 or 2단계 작은 문제를 틀렸습니다를 2개 이하 받고 성공한다,(+750 별조각)와쿠 컵의 문제를 3개 이상 푼다. (+500 별조각), 모든 퀘스트를 해결 한다. (배경 or 1~4코인 or 700+ 별조각)
이 문서의 내용 중 전체 또는 일부는 2023-11-06 21:49:27에 나무위키 solved.ac 문서에서 가져왔습니다.