본문 바로가기

C++

 (39)
imos법 이해하기 개인 기록용 느낌으로 글을 쓰기 때문에 나만의 해석이 첨가되어 있다 imos법이 뭔지에 대해선 나보다 훨씬 설명 잘 하는 사람들이 많으니 그사람들 글을 보기 바란다 이 글은 imos법이 다양한 문제에 활용되는 모습을 보면서, 그에 대한 내 고찰을 다룬다 imos법에 대한 내 생각은 누적합의 확장된 버전이라는 것이다 n차원 공간에서 쿼리를 처리할 때 그 구간의 시작점과 끝점만 기록해준 뒤, 마지막에 O(N)정도로 후처리를 해주면 그 쿼리 결과를 개빠르게구할수있다는 거였음 그 대표적인 문제들은 아래와 같다 https://www.acmicpc.net/problem/3020 https://school.programmers.co.kr/learn/courses/30/lessons/92344 https://www.a..
노션/깃헙 board를 활용한 알고리즘 공부 최근 대기업 공채를 집어넣으면서 웬만한 코딩테스트는 합격할 수 있다는 걸 확인했고, 취미로 조금 어려운 알고리즘들도 공부해보려고 한다. 어려운 알고리즘일수록, 1)어디서 키워드를 주워듣는다 2)그 키워드를 구글링하고 공부한다 3)문제풀이 이 순서로 학습하게 되는 것 같은데, 이러한 과정에서 이미 알고있던 알고리즘을 까먹었단 걸 발견하기도 하고 그렇다 이러한 문제점을 해결하기 위해 Notion이나 Github project에 있는 보드를 활용하면 좋다는 생각이 들어 실행으로 옮겼다 아예 모르는 키워드 아는데 까먹은 키워드 개념만 아는 키워드 구현까지 아는 키워드 문제풀이가 가능한 키워드 완벽히 아는 키워드 이렇게 구분해 놓았다 https://lavender-ball-df5.notion.site/65fc5e..
[BOJ 1918, 조금 어려움] 후위 표기식 (C++) 유명한 문제지만 나처럼 푼 사람은 아무도 없는 것 같아서 내 풀이를 가져왔다 개인적 난이도 : 조금 어려움 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 알파벳을 넣어줄 queue를 사용한다 연산자를 넣어줄 stack을 사용한다. 연산자와 그 연산자의 우선순위를 pair로 집어넣는다. 연산자의 우선순위 비교를 편하게 하기 위해, map을 사용했다. + 와 - 의 우선순위는 0으로 놓는다 * 와 / 의 우선순위는 1으로 놓는다 ( 여는 괄호..
Meta Hacker Cup 2023 (종료) 친구 소개로 처음 참여해봄 https://www.facebook.com/codingcompetitions/hacker-cup Meta Hacker Cup www.facebook.com 다른 온라인 저지 사이트들이나 경쟁 프로그래밍 사이트랑 다르게 제출이 좀 까다롭다 input 파일을 받아서 output 파일을 생성하고 소스코드랑 output 파일을 사이트에 제출하는 방식이다 https://www.facebook.com/codingcompetitions/hacker-cup/2023/practice-round/problems/A1 Problem A1: Cheeseburger Corollary 1 | Meta Hacker Cup - 2023 - Practice Round www.facebook.com #inc..
solved.ac Grand Arena #2 · Arena #2 / 3솔(2144) 백준과 solved ac 사이트가 힘을 합쳐 경쟁적 프로그래밍 컨텐츠가 생겼다 문제가 한국어로 출제되고, 백준 스타일의 문제에 익숙하므로 쉬울 줄 알았으나 글쎄요,,,,,,,,,,, 총평 : 1. 나는 경쟁적 프로그래밍을 잘 못하며 잘 하기 위해 태그가리기와 업솔빙을 많이 해야 함 2. 문제가 난이도순으로 정렬되어 있지 않아 다소 까다롭지만 스코어보드를 보면서 하면 됨 3. 풀이에 대한 증명(수학적/논리적)도 연습이 필요할 것 같다. C번 풀면서 느낌 4. 어렵지만 Atcoder보다는 친숙하고 할만하며, 업솔빙도 더 열심히 하게 될 것 같다 https://solved.ac/en/arena/2/editorial solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문..
저는 DP가 너무 어려워요 ㅠㅠ -> Atcoder Educational DP Contest 풀이 (A~H) (작성중) DP는 너무 어려운데 참 자주 보인다 그리고 DP랑 애드혹을 잘 풀어야 멋있어 보인다 Atcoder에서는 Educational DP Contest를 통해 자주 나오는 DP들의 유형과 그 에디토리얼을 제공하니 DP가 어려운 나 너 우리는 모두들 이 문제 셋을 풀어봤으면 좋겠다 Atcoder에 첨부된 에디토리얼은 일본어로만 존재하므로 구글링을 해보는 것이 좋다. 아님 아래 깃헙 코드를 참고하여라 https://github.com/mrsac7/atcoder-educational-dp GitHub - mrsac7/atcoder-educational-dp: Accepted solutions to the Atcoder Educational DP Contest Accepted solutions to the Atcod..
AtCoder Beginner Contest 310 후기 (ABC 310 3솔) /// 앳코더 잠시 중단 업솔빙 제대로 안하고 맨날 3솔따리 4솔따리 해서는 민트에 절대 못 갈 것 같다. E를 안정적으로 풀어낼 수 있을 때까진 수련이 필요할 것 같아 앳코더는 당분간 중단한다. 수련법 : 백준 골3~플5 그래프/다익/uf/TSP/자료구조 문제풀이 (정수론이랑 기하랑 dp도 많이 나오지만 코딩테스트엔 그리 많이 안나오니까 뒷순위로 미룬다) + 앳코더 D E 풀이 / D E 합쳐서 30분 잡고 안풀리면 답 보기 D가 어려웠다 백트래킹을 떠올리는건 어렵지 않은데 시간복잡도 최적화+ 경우의 수를 줄이기 위한 가지치기가 필요하다 그대로 백준으로 넘어온다면 골드 3이상을 부여하고 싶다 E는 개쉬워보이는데 D 버리고 E 풀걸 그랬다.... 수험생일 시절에도 그랬고 내가 풀 수 있는 문제인지 아닌지 판단하고 취사선택하는 게..
AtCoder Beginner Contest 307 후기 (ABC 307 3솔) C 개 드럽다 구현량 많고 실수하기 쉬운 순수 구현 문제이다 C를 못풀었는데도 레이팅 1021이 나와서 순방에 성공했다 C에 대부분의 시간을 사용했고 E는 쳐다볼 시간도 없었다 A - 걍풀면됨 B - 펠린드롬, 브루트포스, 문자열 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; bool ispel(string s){ int ssize = s.length(); int l = 0,r = ssize-1; while (l>N; vector v; for (int i = 0; i >S; // a번째랑 b번째 합쳐서 펠린드롬되면 yes v.push_..
AtCoder Beginner Contest 306 후기 (ABC 306 4솔) ABC305는 친구생일에 술먹고 노느라 스킵했다 ABC306은 또 Unrated처리되었다 왜이러냐증말 이번 앳코더 ABCD번 문제는 매우 쉬웠고 빨리 풀었다 대신 E는 뭔가 쉬운듯하면서 안 풀리고 F는 아이디어가 생각이 안남..,.. ABCDE를 안정적으로 풀고 F도 간간히 풀 수 있어야 민트에 올라갈 수 있을 텐데 말이다 앳코더 복기랑 업솔빙을 많이 해야 하는데 자꾸 귀찮아서 미룬다 A - 쉬움 문자열의 모든 원소를 순회하면서 2번씩 출력하기만 하면 된다 B - 오버플로우를 조심하자 / 비트연산 첫 제출에 실수해서 5분패널티를먹었다 2^63의 숫자를 표현하기 위해선 64비트짜리 자료형을 사용해야 하고 이 경우 C++에서는 uint64를 쓰거나 아님 파이썬으로 풀어야 한다 bigint??도 아마 가능할텐..
AtCoder Beginner Contest 304 후기 (ABC 304 4솔) 여러모로 아쉬웠음. C가 더러워 보여서 미루고 D로 넘어갔는데, D를 풀 아이디어가 생각나지 않아서 시간만 날렸다. E는 예상 외로 쉬웠다 그리고 이번 앳코더에는 체점 큐가 밀리는 사고가 있어서... 답이 틀려도 그게 틀렸는지 알고 싶으면 2~30분을 기다려야 했다. 주최측에서도 문제라고 생각했는지 시험 종료 1분전에 시험 시간을 20분 연장시켜 줬지만 추가된 시간 동안 다른 문제를 풀지는 못했음. 악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가량 올릴 수 있었는데!!악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가량 올릴 수 있었는데!!악!! 체점 큐가 밀리는 이슈 때문에 대회가 Unrated 처리되었다!! 이번에 30점가..

티스토리툴바