The Way
5월 17일 백준 본문
* 코드는 맨 아래에 있습니다
울 학교 학생분께 ACM-ICPC 같이 나가자고 연락이 왔다
나랑 같은 휴학생이고 되게 열심히하실 것 같고 성격도 완전 천사같다
앞으로 더 열심히 해야겠다
# 백준 10799번: 쇠막대기
간단한 스택 문제. 스택에 막대 n개가 쌓여 있을 때 레이저가 자르면 n개의 조각이 더 생긴다.
# 백준 1406번: 에디터
특이하게 list를 사용하는 문제이다.
list에서 insert와 erase할 때 iterator 위치가 약간 헷갈릴 수 있으니 주의
# 백준 10820번: 문자열 분석
맨 마지막줄이 엔터가 있는지 없는지 참 아리까리하다..
이것 때문에 틀림 ㅠ
# 백준 11655번: ROT13
뭐... 엄청 많이 접해봤을법한 카이사르 암호이다.
오버플로우가 일어날 수 있으니 편하게 unsigned를 붙이자.
# 백준 10824번: 네 수
생각보다 약간 헤맸다. char을 저장해 그대로 처리해줬는데,
자리수가 다를 경우나 받아올림 등 신경써줄 게 상당히 많았다.
stack까지 가져다 쓰며 고생했다..
생각해보니까 두 개 붙여도 long long 범위라서 그냥 해도 됐을텐데 왜 그랬을까..
코드를 새로 짰다 그래서.
# 백준 11656번: 접미사 배열
문자열 처리 + 사전순 -> set<string>
# 백준 9613번: GCD 합
# 백준 2745번: 진법 변환
# 백준 11005번: 진법 변환 2
# 백준 11576: Base Conversion
생략
# 백준 15719번: 중복된 숫자
비트마스크를 사용하면 손쉽게 풀 수 있다.
그런데 XOR을 이용하는 정말 참신한 방법이 있다. 감동받음...
# 백준 2089번: -2진수
많이 복잡한 문제이다.
내가 사용한 알고리즘은,
수가 음수이면 1010...10(2k개)이 수보다 같거나 작아질 때까지 k를 증가시킨 뒤 뒤쪽 1은 다 버리고 1000..00을 더해주고,
수가 양수이면 10101..01(2k + 1개)이 수보다 같거나 커질 때까지 k를 증가시킨 뒤 뒤쪽 1은 다 버리고 100..00을 빼주었다.
말로 표현하기가 참 힘든데, 예시인 -13은 다음과 같은 과정을 거친다.
-13 (101010 = -42가 더 작으므로 -13 + 100000 = 19)
19 (10101 = 21이 더 크므로 19 - 10000 = 3)
3 (101 = 5가 더 크므로 3 - 100 = -1)
-1 (10 = -2가 더 작으므로 -1 + 10 = 1)
1 (1 = 1이랑 같으므로 1 - 1 = 0)
지금까지 사용한 수를 모두 or 해줌 (100000, 10000, 100, 10, 1) -> 110111이 답
0은 따로 예외처리를 해주어야 한다.
# 백준 6588번: 골드바흐의 추측
에라토스테네스의 체를 이용해서 미리 소수 전처리를 해놓고, 소수를 찾아주자.
골드바흐의 추측은 아직 반례가 나오지 않았으므로 굳이 예외처리를 하지 않아도 된다.
# 백준 11653번: 소인수분해
평범한 소인수분해 문제이다.
1이 입력일 때는 1을 출력하는 게 아니라 아무것도 출력하지 않아야 한다.
# 백준 2004번: 조합 0의 개수
항상 overflow에 유의
# 백준 1991번: 트리 순회
노드 이름이 char이라 저장하는 데 map을 사용했다.
# 백준 11725번: 트리의 부모 찾기
사실 dfs 문제이다. 트리에서 dfs를 많이 쓴다.
1406.cpp