티스토리

코드를 찢다
검색하기

블로그 홈

코드를 찢다

jaeseo0519.tistory.com/m

싱클레어, 대부분의 사람들이 가는 길은 쉽고, 우리가 가는 길은 어려워요. 우리 함께 이 길을 가봅시다.

구독자
24
방명록 방문하기
공지 앞으로의 일정에 대하여.. 모두보기

주요 글 목록

  • [Programmers] 퍼즐 조각 채우기 (Level 3) 1. 문제 설명  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr코테의 근본은 C++하지만 최근 기업 코테에서 C++을 받아주질 않는 추세다.이유가 뭔고 하니 C++로 해킹을 하는 사람들이 있다고......:(그것도 있고 기업 코테의 목적이 알고리즘 그 자체보단, 언어의 이해도를 측정하는 구현 능력에 초점을 맞추면서 겸사겸사 제한하는 것 같다. 덕분에 코테도 자바로 하는데, 손에 안 익어서 죽을 맛이다. 2. 아이디어 생각 이상으로 시간을 너무 잡아먹었다.3월 이후로 개발에 몰두한다고 코테 손 좀 놨더니 바로 폼 떨어져버림. 1️⃣ 블록 탐색일단 처음 보자마자.. 공감수 0 댓글수 0 2024. 6. 19.
  • [Programmers] 징검다리 (Level 4) 1. 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백준 플래티넘 찍고, 아무튼 취업 준비 해야 하니 요새 코테 트렌드에 맞는 프로그래머스 줄창 풀고 있었는데 이 문제는 너무 얼탱이 없어서 정리해둔다. 15분 컷내고 다른 문제 풀려고 넘어가는데 내 발목을 1시간이나 붙잡았다. ㅡㅡ 23년 이후로 테스트 케이스가 추가된 것 같다. 다른 사람들은 어떻게 풀었는지 궁금해서 뒤져봤는데, 지금 돌려보면 전부 틀린 풀이라고 나온다. 2. 아이디어 애초에 문제 카테고리가 이분 탐색이었으니, 사용할 알고리즘을 알면 문제 해결을 위한 구현은 쉬웠다. left .. 공감수 0 댓글수 0 2024. 2. 27.
  • [C++] 1774 - 우주신과의 교감 (골드 3) 1. 문제 설명 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 2. 아이디어 💡 사이클을 이루지 않는 최소 비용의 간선 찾기 => MST 보자마자 최소 신장 트리를 만들어야 겠다는 건 떠올리지 못 했고, 한참을 문제를 째려보다가 탐욕법으로 접근하면 되겠다 싶긴 했는데 구현이 막혔다. (각 노드가 선택할 수 있는 경로 중에 가장 비용이 작은 간선을 선택하면 되므로 탐욕법 접근이 가능하다 판단했다.) 구현이 막혔던 이유는 처음에 모든 정점의 좌표를 이용해서 간선에 대한 비용을 계산해두.. 공감수 1 댓글수 0 2023. 11. 21.
  • [C++] 1613 - 역사 (골드 3) 1. 문제 설명 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 푸는데 시간을 많이 소모하긴 했지만, 재밌는 문제라서 오히려 좋은 시간이었다. 2. 아이디어 보자마자 Union-find 문제라고 생각해서 15분 만에 기계적으로 코드 작성해서 제출했다. 하면서 '나...좀 천재?'이러고 있었는데, 지금 생각해보면 왜 틀린 것도 아니고, 런타임 에러가 났는지가 의문이다. 여튼 50%까진 성공했으니, 배열 크기를 잘못 잡았나 싶어서 어떤 케이스에서 오작동이 되나 살펴보던 중 그냥 아이디어 자체가 틀렸음을 알.. 공감수 0 댓글수 0 2023. 11. 3.
  • [C++] 16236 - 아기 상어 (골드 3) 1. 문제 설명 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 조건 하나 잘못 읽었다가 시간 왕창 빼앗김.. 난이도 자체는 어렵지 않다. 2. 아이디어 bfs 돌리면 되겠다 싶은 건 보자마자 알 수 있을 거고 문제는 움직일 target이 여러 개가 존재할 수 있기 때문에, 그 중 최적값만 찾아야 한다. 흐름은 다음과 같이 진행될 것이다. 현재 위치에서 bfs로 다음 먹이의 위치와 위치까지 이동 거리를 계산한다. 만약, 이동하지 않았다면 반복문을 멈춘다. 아기 상어를 다음 먹이의 위치로 이동시킨다... 공감수 0 댓글수 0 2023. 11. 2.
  • [C++] 14658 - 하늘에서 별똥별이 빗발친다 (골드 3) 1. 문제 설명 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 시험 끝나면 코테 매일 한 문제씩 풀려고 벼르고 있었는데, 뭔 놈의 과제랑 쪽지 시험이 계속해서 쏟아진다. 그래서 쪽지 시험 반 쯤 던지고 풀었는데, 이딴 게 골드 3 2. 아이디어 가장 처음 보자마자 별 하나씩 트램펄린 꼭짓점에 두고 4방향을 뒤지면 될 거라고 생각했다. 이걸 문제를 보자마자 떠올렸는데, 가장 최근에 공부한 게 탐욕법이라서 그런가. 그런데 상식적으로 점 .. 공감수 1 댓글수 0 2023. 10. 30.
  • [C++] 10265 - MT (플래티넘4) 1. 문제 설명 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 이제 MT 갈 때 됐으니, MT 문제를 풀어보라던 스터디원의 권유로 보게 된 문제. 오랜만에 코테 문제 푼다고 새벽 3시까지 못잤다. 장장 10시간 정도를 풀었던 것 같다. 🤮 물론, 그 사이에 프로젝트 때문에 개발을 멀티로 수행했다는 것도 문제였던 거 같기도 한데, 문제만 봤어도 금방은 못 풀었을 것 같다. 2. 아이디어 보자마자 위상정렬(Topological Sort) 문제겠거니 했다. "내가 가려면 누군가(선행조건)가 가야 한다."식의 문제이므로, '나'의.. 공감수 0 댓글수 0 2023. 8. 29.
  • [C++] 2533 - 사회망 서비스(SNS) (골드3) 1. 문제 설명 요새 너무 바빠서 문제 하나 풀 여유조차 없다는 게 너무 서러워서 골드 문제라도 오랜만에 풀어봤다. 플래티넘은 푸는데 시간이 얼마나 소요될 지 감이 안 잡혀서 ㅠㅠ 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 2. 아이디어 이 문제를 처음 보자마자 vertex cover 문제로 접근하면 되겠구나 싶었다. (그러면 이분 매칭 문제로 바뀐다.) 하지만 조금 더 생각을 해보자. 가중치가 따로 존재하진 않으므로, 유량을 1로 전부 고정시키고 포스 풀커슨 알고리즘을.. 공감수 1 댓글수 2 2023. 3. 15.
  • [C++] 15721 - 번데기 (실버5) 1. 문제 설명 15721번: 번데기 예를 들어 7명이 있고, 16번째 등장하는 “뻔”을 부른 사람의 번호를 알고 싶다면 입력은 7 16 0이다. 4명이 있고 6번째 등장하는 “데기”를 부른 사람의 번호를 알고 싶다면 입력은 4 6 1이며, 이 www.acmicpc.net 2. 아이디어 심심해서 구글링 하면서 놀다가 우연히 발견한 문제였는데 문제 유형은 브루트 포스라고 되어 있고 실제로 그렇게 해도 상관 없지만, 수학적으로 최적화가 가능할 것 같아서 풀어봤다. (꽂히면 해봐야 하는 타입) 근데 문제가 워낙 간단해서 별다른 성과를 얻지는 못했다. 잘 생각해보면 이 문제는 T번 째 0 혹은 1의 위치만 알면 인원수의 나머지를 구하면 답이 나온다. result = T_index % A 그럼 이 문제는 "T번 .. 공감수 0 댓글수 0 2023. 1. 31.
  • [C++] 6549 - 히스토그램에서 가장 큰 직사각형 (플래티넘5) 1. 문제 설명 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 테스트 케이스가 한 개 뿐인 동일한 티어의 문제가 또 있다. 경험치 2배 이벤트 댕꿀~ algospot.com :: .. 공감수 0 댓글수 0 2023. 1. 4.
  • [C++] 16234 - 인구 이동 (골드5) 1. 문제 설명 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 아이디어 처음 보자마자 무식한 방법으로 로직은 떠오르는데 탐색이 너무 많이 필요해서 통과가 될까 싶었지만 입력 조건에 인구 이동 발생 일수가 최대 2,000번밖에 되지 않는다고 했으므로 개의치 않아도 된다고 판단했다. N은 MAX 50이므로 최대 2,500크기 인접 행렬 그래프를 그릴 수 있는데, 2,000번 반복한다고 해도 5,000,000번 이므로 시간 복잡도에 걸리지 않는다. 즉, 그래프를 순회하면서 인구 차이가 L이상 R.. 공감수 0 댓글수 0 2023. 1. 1.
  • [C++] 21608 - 상어 초등학교 (골드5) 1. 문제 설명 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 2. 아이디어 구현 문제는 아무래도 생각할 게 많아서 귀찮다. 예외처리라던가 이런 것들. N의 최대가 20이므로 시간복잡도는 사실상 고려하지 않아도 될 정도로 작은 수다. 즉, 알고리즘이고 뭐고 구현만 할 수 있는 논리적인 아이디어만 도출한다면 귀찮은 문제지, 어려운 문제는 아니다. 나는 처음 받은 학생의 번호 순서대로 그래프를 긁으면서 배치부터 시작했다. 이건 그냥 튜플 안에다가 현재 위치에서 {좋아하는 친구 숫자, 빈 자리 숫자, y.. 공감수 0 댓글수 0 2023. 1. 1.
  • [C++] 14503 - 로봇청소기 (골드5) 1. 문제 설명 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 2. 아이디어 멘토 활동을 하다가 삼성 기출은 어떤 식으로 나오나 싶어서 몇 문제 풀어보던 중 발견한 문제. 문제에 모든 로직을 제공해줘서, 사실상 코드로 구현만 하면 되는 간단한 문제다. 이 문제가 쉽게 풀리지 않는다면 구현력 자체가 떨어지거나, 심한 경우엔 독해력이 떨어지는 것. 조롱의 의미가 아니라 후자의 경우면 문제를 꼼꼼하게 읽고, 논리적으로 분석하려는 노력을 남들보다 몇 배로 연습한다면 충분히 극복 가능하다. 각각의 로직을 어떻게 처리.. 공감수 0 댓글수 0 2022. 12. 25.
  • [C++] 1014 - 컨닝 (플래티넘4) 1. 문제 설명 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 2. 아이디어 처음 보자마자 dynamic programing을 사용하면 풀 수 있을 것이라 생각하고 접근 중이었는데, 풀다가 심심해서 알고리즘 분류표를 봤더니 최대 유량이 태그에 있었다. 이 문제를 최대 유량으로 해결할 수 있다고..??? 뒤져보니 컨닝 2는 dp와 비트마스킹으로 풀어야 시간복잡도 내에 해결 가능하지만, 컨닝 1은 최대 유량으로 해결 가능하다는 글을 보자마자 일단 dp 풀이는 미루고 최대유량으로 접근하는 방법을 찾아보았다. 하지만 도저히 해결 .. 공감수 0 댓글수 0 2022. 11. 1.
  • [C++] 1067 - 이동 (플래티넘1) : FFT(고속 푸리에 변환) 1. 문제 설명 1067번: 이동 N개의 수가 있는 X와 Y가 있다. 이때 X나 Y를 순환 이동시킬 수 있다. 순환 이동이란 마지막 원소를 제거하고 그 수를 맨 앞으로 다시 삽입하는 것을 말한다. 예를 들어, {1, 2, 3}을 순환 이동시키면 www.acmicpc.net 컴공 복전 2학년 수업으로 데이터 통신을 듣다가 교수님께서 FFT라는 알고리즘을 언급하셨는데, 너무 어려운 내용이라 보통 석사 과정에서 배우는 내용이라 로직을 알 필요는 없다고 하셨다. 하지만...'내가 모르는 알고리즘?'이라는 생각이 뇌리에 꽂히면서 이 로직과 원리를 분석하는데 무려 3일이란 시간이 소모됐다. (교수님께서 하지 말라는 데는 다 이유가 있다.) 지금도 증명 단계에서 정확이 알고 있다고 할 수는 없다. 이산 수학을 공부한.. 공감수 1 댓글수 1 2022. 9. 29.
  • [C++] 1006 - 습격자 초라기 (플래티넘3) 1. 문제 설명 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 2. 아이디어 문제도 너무 잘 이해되고, 아이디어도 바로바로 떠올라서 뭐지? 싶었는데, 예전에 다른 알고리즘을 검색해보다가 언뜻 봤었던 걸 아직까지 기억하고 있었다... 갑자기 코드 짜다가 생각나서 구글 뒤져봤더니 아니나 다를까 내 아이디어가 아니었다. 차라리 중간에 찾아보지라도 말 걸..ㅠㅠ 그래도 조금 다른 관점으로 흘러가다가 확인해버렸더니 그대로 머리가 굳어버려서 다른 방법을 시도하다가 더 나은 .. 공감수 1 댓글수 1 2022. 9. 24.
  • [C++] 12736 - Fireworks (다이아몬드1) 1. 문제 설명 12736번: Fireworks 불꽃놀이는 축제에서 가장 재미있는 행사 중 하나이다. 불꽃놀이에서 가장 중요한 것은 한 스위치에 도화선으로 연결된 모든 폭약이 계획된 시각에 동시에 폭발해야 한다는 것이다. 폭약들은 www.acmicpc.net 다이아쯤 가면 어떤 문제를 풀까 궁금해서 접근했다가 죽는 줄 알았다. 구현 + 수학 + 알고리즘을 모두 합친 문제라고 해야하나.. 심지어 APIO 2016 킬러 문제인 줄 알았으면 호기심도 안 가졌을 것. 🙄 문제를 풀었다기 보다는 공부나 연구했다가 더 맞는 말이므로 코드는 따로 올리지 않겠다. 어찌저찌 구현은 했지만 핵심 코드는 다른 분들의 코드를 분석하면서 참조(암기)해버렸기 때문에, 나중에 이 문제가 잊혀질 때쯤 다시 풀게 된다면 그때 코드를 .. 공감수 1 댓글수 2 2022. 9. 5.
  • [C++] 1209 - 단조수열 만들기 (플래티넘4) 1. 문제 설명 1209번: 단조수열 만들기 음이 아닌 정수로 이루어진 수열 $A_1, A_2, \dots , A_N$이 있다. 단조수열 $B_1, B_2, \dots , B_N$을 만들어서 $|A_1-B_1| + |A_2-B_2| + \dots + |A_N-B_N|$을 최소로 하는 프로그램을 작성하시오. 단조수열이란 $B_1≤B www.acmicpc.net 로직은 극단적으로 쉬우나 수학이 문제다.. 2. 아이디어 BOJ 1209 단조수열 만들기 : O(NlgN) https://www.acmicpc.net/problem/1209 최근 CF에 똑같은 문제가 출제되었는데, 짱짱맨 분들이 O(nlgn)에 풀어주신 덕분에 오랜 난제(http://koosaga.myungwoo.kr/110) 가 해결됐다. http.. 공감수 0 댓글수 0 2022. 9. 3.
  • [C++] 15678 - 연세워터파크 (플래티넘5) 1. 문제 설명 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 2. 아이디어 보자마자 dp인 건 이제 감으로 알겠는데, 아무리 생각해도 타임 오버가 날 것 같았다. 그렇다면 다른 자료구조를 섞어 써야 한다는 말인데..찾아보니 세그먼트 트리나 단조 큐를 쓰라고 한다. ..? 단조 큐를 여기서요...?? 대체 여기 어디에 덱을 쓸만한 구석이 있다 한참을 분석해본 결과 개요는 다음과 같다. 관점을 '건너 간다'가 아니라 '건너 온다'라고 바꾸었더니 술술 풀렸다. 입력값을 차례로.. 공감수 0 댓글수 0 2022. 9. 3.
  • [C++] 11003 - 최솟값 찾기 (골드1) 1. 문제 설명 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제를 푸는 것보다 이해하는 데 더 오래 걸린 거 같다. 컴퓨터 언어만 파더니 한국어가 더 힘들어지나 보다.... 2. 아이디어 다른 문제를 풀다가 아이디어를 참고하고 싶어 해결한 문제다 보니 이미 큐를 사용해야 하는 문제라는 걸 알고 있어서 쉽게 해결했다. 처음에는 queue로 문제를 해결하려 했지만, 자료구조 특성상 큐는 자료를 제거하는 쪽과 넣는 쪽이 각각 한 곳밖에 존재하지 않는다. 이 문제는 L이라는 값에 .. 공감수 0 댓글수 0 2022. 9. 2.
  • [Python] 3736 - System Engineer (플래티넘2) 1. 문제 설명 3736번: System Engineer There are two data sets. In the first case, the number of jobs n is 2, numbered 0 and 1. The sequence of requests for job 0 is: 0: (1) 2, meaning that job 0 requires 1 sever, the server numbered 2. The sequence of requests for job 1 is: 1: (1) 2, meaning t www.acmicpc.net 2. 아이디어 호프크로프트 카프 알고리즘 (Hopcroft-Karp Algorithm) (수정: 2020-09-30) 아마 플로우 관련 게시글 중엔 드디어 마지막이 될.. 공감수 0 댓글수 0 2022. 8. 6.
  • [C++] 2130 - 수조 (플래티넘5) 1. 문제 설명 2130번: 수조 N(1≤N≤50,000)개의 수조가 있다. 각각의 수조는 3차원 공간상에 존재한다. 수조에 대한 정보는 수조가 위치한 높이 b(0≤b≤1,000,000), 수조 자체의 높이 h(1≤h≤40,000), 수조의 가로길이 w(1≤w≤40,000) www.acmicpc.net 2. 아이디어 이 문제를 모자마자 떠올린 방법은 지면부터 가장 위의 수조 상단부까지를 잘게 쪼개는 것이었다. 시간 복잡도에 걸리지는 않을까? 걱정을 했었는데 처음 입력받을 때부터 바닥을 인덱스 0으로 잡고 해당 인덱스에 존재하는 수조의 용량을 계산한다. 그러면 이후 해결 단계에서는 입력된 정보를 1번 인덱스부터 물을 채워보면 된다. 물을 채운다는 의미는 곧 처음 주어진 물의 양이 현재 인덱스의 수조 부피만.. 공감수 0 댓글수 0 2022. 8. 6.
  • [C++] 13334 - 철로 (골드2) 1. 문제 설명 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 2. 아이디어 [C++] 2170 - 선 긋기 (골드5) 1. 문제 설명 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다... jaeseo0519.tistory.com 이전과 마찬가지로 스와핑 알고리즘을.. 공감수 0 댓글수 0 2022. 8. 5.
  • [C++] 2170 - 선 긋기 (골드5) 1. 문제 설명 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 2. 아이디어 스와핑 관련 문제를 처음 봐서 찾아봤었다. 그렇게 어려운 로직이 아니었다. 일단 값을 입력받고 시작점 기준으로 정렬을 한 번 수행한다. 그 뒤로 길이를 체크해줄 left와 right 변수를 -INF로 설정해주고 right와 시작점을 비교한다. 시작점이 현재 right의 위치보다 작다면 right의 값을 끝점으로 옮길 것이지만, 그게 아니라면 입력받은 right와 left의 차이만큼 결과값에 저장하고 le.. 공감수 0 댓글수 0 2022. 8. 5.
  • [C++] 1708 - 볼록 껍질 (플래티넘5) 1. 문제 설명 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 2. 아이디어 이때는 몰랐는데 기하 알고리즘의 입문 절차나 다름없는 문제였다. 이쪽 분야 알고리즘은 처음 풀어봐서 꽤 힘들었었다. CCW(Counter Clockwise) 세 점이 일직선, 가운데점을 기준으로 반시계, 시계 방향으로 놓여있는 경우를 판단하는 알고리즘과 컨백스 헐(Convex Hull) 2차원 평면상의 여러 점중에 다른 모든 점을 포함할수 있는 볼록 다각형을 찾는 알고리즘 이 두 가지를 알고 있어야 해결할 수 있.. 공감수 0 댓글수 0 2022. 8. 5.
  • [C++] 10999 - 구간 합 구하기 2 (플래티넘4) 1. 문제 설명 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 아이디어 Lazy Propagation(게으른 전파)라는 알고리즘을 처음 접했던 문제였는데 진짜 신박하고 재밌는 알고리즘이었다. 세그먼트 트리(Segment Tree)에 대한 선행 지식이 필요하지만, 난 따로 포스팅을 해놓은게 없다..(곧 할 거다 ㅠ) 여긴 아이디어를 작성하는 곳이지 알고리즘을 설명하는 목적은 아니니까 자세한 내용은 따로 다룰 것이다. Lazy Propagat.. 공감수 0 댓글수 0 2022. 8. 5.
  • [C++] 2208 - 보석 줍기 (골드2) 1. 문제 설명 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 2. 아이디어 경우의 수를 묻는 문제는 보통 dp로 찔러보면 된다. 연속합과 관련된 문제인 건 알겠는데, 생각보다 까다로운 문제였었다. 내가 사용한 방법은 우선 차례대로 모든 보석을 주웠을 때의 합을 차례로 구한다. 그 후, m간격 만큼 이동하면서 이전의 값을 빼주면 계속해서 m구간 만큼의 구간합을 알 수 있다. 이렇게 했을 때, 최대값을 출력하면 해결되는 문제였다. 3. 코드 #include #include using namespac.. 공감수 0 댓글수 0 2022. 8. 5.
  • [C++] 2056 - 작업 (골드5) 1. 문제 설명 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 2. 아이디어 이전에 음악 프로그램인가? 몇 번 접해본 유형의 문제라 위상 정렬 알고리즘을 쓰면 되겠다는 걸 금방 캐치했다. 당시에 C++을 얼마 써보지 않아서 동적할당 연습 겸 배열을 사용했는데, 나중에 SCPC에서 알게 된 거지만 배열은 크기가 100,000까지로 제한되어 있어서 벡터에 충분한 크기의 공간을 상수로 넣어주는 게 훨씬 편하다. 위상 정렬인 것만 알면 그 후로 로직 자체는 간단하다. 선행 조건이 없는 작업부터 큐에 담고 .. 공감수 0 댓글수 0 2022. 8. 5.
  • [C++] 11657 - 타임머신 (골드4) 1. 문제 설명 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 아이디어 다익스트라 알고리즘인 줄 알았는데 타임머신을 쓰면 음의 가중치가 더해진다. 최적의 해를 찾기 위해서는 비용이 적게 드는 간선을 골라야 하는데 음의 가중치가 있으면 '되돌아간다'의 개념이 아니라 '음의 비용'으로 이동하게 되기 때문에 최적의 해를 찾을 수 없게 된다. 이 경우엔 다른 알고리즘이 필요할 것 같아서 찾아보니 역시나 벨만 포드 알고리즘이란 걸 써야 한다. 다익스트라.. 공감수 0 댓글수 0 2022. 7. 14.
  • [C++] 2494 - 숫자 맞추기 (골드1) 1. 문제 설명 2494번: 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net 2. 아이디어 벽장문 문제나 카드 게임 문제 같은 이런 문제들은 갈림길에서 어떤 선택을 하느냐에 따른 모든 경우의 수를 판단하도록 요구한다. 그리고 이런 요구의 해답에 보통 DP는 기본으로 들어간다. 하지만 난 DP로 접근했다가 실패했다. (어떻게 구현하려면 할 수 있을 것 같긴 하다.) C++이 익숙치 않아서 복잡하게 풀기가 싫다보니, 다른 방법을 고민하다가 그냥 가장 위에서부터 나사를 돌려보기로 했다. 생각해보면 나사를 밑에서 맞추는 건 의미.. 공감수 0 댓글수 0 2022. 7. 14.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.