728x90 반응형 전체 글97 [백준]2325번: 자료구조는 정말 최고 https://www.acmicpc.net/problem/23253 23253번: 자료구조는 정말 최고야 위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다. www.acmicpc.net 처음 이 문제를 풀때 더미의 순서를 일정하게 유지하는 부분이 힘들었다. 이에 다양한 접근법을 시도하면서 vector를 통해 해결했다. 접근 방법 1) 우선 순위 큐를 선언한다. 이때 오름차순으로 정렬될 수 있게 설정한다. 2) 우선 순위 큐에 해당 책과 어느 더미 몇 번째에 위치하는지 저장한다. 3) lis라는 vector를 통해 각 더미의 현재 위치를 추적하는데 사용한다. 즉 lis의 각 요소 해당 더미의 현재 위치를 나타내.. 2023. 12. 22. 컴퓨터 메모리 저장 방식과 2차원 for문 관계 질문 아래 코드와 같이 2차원 배열이 있고 두 개의 이중 for문이 있을 때 어떤 접근이 더 효율적일까? (모든 상황은 다 동일하고 단순 두 개의 코드 차이만 있다고 가정한다.) 답변 당연히 1번 이중 for문 즉 행 접근이 더 효율적일 것이라 생각했다. 근거 1) 컴퓨터 메모리는 일렬로 구성되어 있다, 즉 row 우선 순서로 저장된다. 2) 따라서 이차원 배열이라도 row 여러개가 순차적으로 저장된 뒤 그 다음 column으로 이동해 row를 채우지 않을 까 생각했다. 3) 그렇기에 CPU 캐시 효율성을 높이는 접근 방법은 row먼저 접근하는 1번 이중 for문이라고 생각했다. 찾아 본 결과 내 접근이 맞았다!!! 더 나아가 2번의 경우 메모리 접근의 불연속이 생겨 CPU 캐시 미스가 더 자주 생길 수.. 2023. 12. 14. [백준]1296번: 팀 이름 정하기 https://www.acmicpc.net/problem/1296 1296번: 팀 이름 정하기 연두는 프로그래밍 대회에 나갈 팀 이름을 정하려고 한다. 미신을 믿는 연두는 이환이에게 공식을 하나 받아왔고, 이 공식을 이용해 우승할 확률이 가장 높은 팀 이름을 찾으려고 한다. 이환 www.acmicpc.net 푸는데 나름 재밌는 문제였어서 풀이를 올리려 합니다. 접근 아이디어는 다음과 같습니다. 1) vector를 통해 (이길 확률, 팀명)을 저장 받습니다. 또한 loveArry를 통해 LOVE 순서대로 개수를 카운팅 한다. 2) LOVE를 개수를 연두 이름과 팀명을 받아 카운팅 해주는 CountLove 함수를 선언한다. 3) 카운팅 된 값을 기준으로 확률을 연산하여 pair의 first값에 해당 팀명에 .. 2023. 12. 13. [백준]25497번: 기술 연계마스터 임스 https://www.acmicpc.net/problem/25497 25497번: 기술 연계마스터 임스 $1$, $2$, $S$ - $K$, $2$로 스킬을 성공적으로 총 4번 사용했다. www.acmicpc.net 자료구조 알고리즘 중 stack을 이용한 문제다. 푼 사람이 적어 내가 고민한 아이디어를 공유해보려 한다. string을 통해 기술을 입력 받는다면 사실상 N은 필요없다. 접근 아이디어는 다음과 같다. 스킬을 보면 SK와 LR은 세트다. 즉 S가 먼저 나와야 K가 가능하고 L이 먼저 나와야 R이 가능하다. 그렇다면 이 두개의 세트를 담을 stack을 준비한다. 각 stack은 SK와 LR만을 담는다. 이때 lrCombo stack은 LR만을 skCombo stack은 SK 기술만을 처리한다... 2023. 12. 6. [백준]2018: 수들의 합 5 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 투 포인터 개념에 대해 처음 접해봤다. 사실상 반복문에서 범위를 빠르게 정해가며 계산하기 위한 개념임을 배웠다. 즉 while 문을 도는데 start와 end 변수를 활용해 start ~ end까지 합을 구해가며 주어진 N과 비교하는 방법이다. start, end, cnt 변수를 준비하고 start = 1, end = 1, cnt = 1에서 시작한다. start + end =.. 2023. 12. 5. [백준]11501번: 주식 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 주어진 예시에서 주가가 10 7 6이면 최대 이익이 0이고 주가가 1 1 3 1 2 면 최대 이익이 5다. 접근 방법은 다음과 같다. 1) 배열에 주가를 담아놓는다. ex) 1 1 3 1 2 2) 최대 주가(maxStock)와 최종 이익(totalProfit) 변수를 선언한다. maxStock은 가장 큰 주가를 의미하며 totalProfit은 최대 이익을 의미한다. 3-1) maxSt.. 2023. 11. 27. 이전 1 2 3 4 5 6 ··· 17 다음 728x90 반응형