본문 바로가기

분류 전체보기

 (386)
백준 17143번 - 낚시왕(C++) https://www.acmicpc.net/problem/17143 구현문제로 엄청난 사고력을 요하는 문제는 아니지만 시간 복잡도 때문에 수학적인 테크닉이 필요한 문제이다. 아무래도 구현문제이기 때문에 사람마다 풀이가 매우 다를 것이다. 하지만 기본적인 아이디어는 비슷할 것이다. 1. 낚시왕이 물고기를 낚는다.2. 상어가 이동한다.  그러므로 난 우선 처음 상어를 입력받을 때 사냥가능한 상어를 먼저 사냥하고 인덱스 1부터 솔루션을 시작했다. 그리고 상어의 정보를 담고 있는 벡터를 선언했는데, 상어가 사냥되거나 다른 상어에 의해 먹혔다고 해서 벡터에서 없애버리는 것은 구현이 어렵고 시간도 더 걸린다. 그래서 life 변수로 살았는지 죽었는지 체크해주었다. 또한 상어들을 이동하고서 같은 곳에 모두 쌓아놓고 ..
프로그래머스 - 오픈 채팅방(C++) https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 카카오 2019년 기출문제로 코딩테스트에서 자주 출제되는 맵을 적절히 사용해야하는 문제이다. Insert가 들어오면 맵에 만약 유저 아이디가 존재하면 갱신하고 없으면 추가한다.체인지가 들어오면 맵 유저 아이디 key에서 닉네임을 교체한다. 그리고 insert와 leave가 들어오면 순서 벡터에 유저 아이디와 나가고 들어감을 표시해둔다.그리고 이후 순서 벡터대로 결과를 출력하면 된다. 그렇게 어렵진 않..
백준 13460번 - 구슬 탈출2 https://www.acmicpc.net/problem/13460  골드1은 참 어렵다.. 그래도 내가 많이 해본 bfs문제이기도 하고 구현의 난이도와 시뮬레이션으로 골드1 난이도를 받은 문제라 다행히 풀어낼 순 있었다. 단연 중요한 건 어떻게 방문체크를 할 것이냐인데,  난 빨간 구슬, 파란 구슬을 나누어 [x좌표][y좌표][방향][빨간색 or 파란색] 4차원 배열을 만들어서 [x좌표][y좌표][방향][빨간색] || [x좌표][y좌표][방향][파란색] 으로 방문 처리를 하니 30퍼센트에서 틀렸습니다가 발생했다...  그리고 정답 처리가 된 것은 visited[nextrx][nextry][nextbx][nextby] 이런식으로 해야한다. 흠... 아무리 생각해도 위 방법도 될 것 같은데 왜 안되는지 모..
운영체제 - 가상메모리의 개념 위 컴퓨터 구조에서 프로그램이 실행될 때, 예를들어 유튜브를 실행하거나 VS CODE 를 실행하려면 우리는 Main Memory 에 프로세스를 적재해야한다. 그리고 요즘 램은 16~32기가 정도 되는데 편의를 위해 10기가 라고 가정하자. 그리고 우리는 지금 메이플스토리, 워드, 카카오톡을 실행한다고 가정하자. 그런데 알다시피 요즘 메이플스토리 용량은 10기가가 넘는다. 그리고 워드도 1기가는 되고 카카오톡은 500메가 정도되지만 1기가라고 하면 메이플 : 10워드 : 1카톡: 1 이 세개의 프로그램을 동시에 실행하려면 메인 메모리에 무려 12기가가 필요하다! 그렇다면 이 세개는 실행이 안될까? 아니다. 아주 잘 될 것이다. 조금은 렉이 걸릴 수 있지만 잘된다. 이것을 가능캐 해주는 것이 가상메모리이다...
SWEA - 창용 마을의 개수 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 기본적인 유니온 파인드 기본 문제이다. 유니온 파인드는 이름부터 유니온과 파인드 함수로 나뉜다. 유니온은 함께 묶기, 파인드는 부모를 찾는 것이다. 그리고 기본적으로 유니온 파인드는 사이클을 찾기 위해서 사용되기도 하는데, 무방향 그래프는 DFS와 유니온 파인드로. 방향 그래프는 DFS로 알 수 있다. #include #include using namespace std;int people[101];in..
SWEA - 백만 장자 프로젝트 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 그리디 문제로 보인다. N이 백만이지만 제한 시간을 30초나 주기 때문에 엄청나게 빡빡하진 않다고 본다. 먼저 예제에 없는 유형을 보자 1 7 2 10 이 때 최상의 경우는 1 7 2에서 모두 사고 10에서 파는 것이다. 즉, 올라가다가 내려간다고 팔면 최적이라 볼 수 없다. 그래서 계속 이후 앞에 최대값이 얼마나 있을지 생각해야한다. 난 그래서 처음 최대값을 설정하고 최대값을 만났을 때 팔고 이후 반복문을 돌리며 남은 숫자 중 최댓값을 찾는 식으로 작성하..
SWEA - 증가하는 사탕 수열 (C++) 처음엔 이분탐색을 통해 풀이하려 했는데 쉬운 그리디 or 구현 문제이다. 경우를 나누어 볼 수 있다. 1. 처음부터 사탕 주머니가 오름차2. 둘 중 하나라도 3번째 주머니보다 많이 차있음 만약 4 7 4 순서로 되어있다면 -> 2 3 4 순서로 만들어야한다. 즉, 최댓값이 정해져있다. 첫번째 값은 candy[2] - 2두번째 값은 candy[2] - 1 그러므로 만약 지금 사탕의 값이 위 임계값보다 크다면 임계값으로 바꿔주고 먹은 사탕을 샌다.단 1 1 7 의 경우처럼 임계값에 걸리지 않지만 오름차가 아닌 경우가 있으므로 오름차가 맞는지 확인하는 로직까지 추가해주면 쉽게 답을 맞출 수 있다. #include using namespace std;int main(){ int T; cin >> T; ..
프로그래머스 - k진수에서 소수 개수 구하기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/92335?language=cpp 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 0으로 split 작업을 하고 소수를 판별하는 문제이다.소수판별에는 여려가지 방법이 있다. 1. O(N)이 걸리는 가장 기본적인 방법2. 에라토스테네스의 체3. 오일러의 체 오일러의 체는 정말 코드포스같은 경쟁적 프로그래밍에서 필요하지만, 여기선 이렇게까지 딥하게 소수를 찾을 필욘 없다. 비효율적이다.https://ps.mjstudio.net/linear-sieve  PS를 위..

티스토리툴바