본문 바로가기
반응형

C++250

[프로그래머스/C++] 트리 트리오 중간값 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀면서 고민을 많이 했던 문제다. n의 범위가 250000 이기 때문에 2차원 vector로 거리를 저장 하기에는 무리였다. 그렇다고 하나의 노드가 들어올 때 마다 노드들의 거리를 측정해 계산하자니, 약 250000*250000이기 때문에 이것도 무리라는 생각이 들었다. 그래서 노드들의 관계가 트리로 주어지기 때문에 하나의 노드를 부모 노드로 지정하고, 반복해서 자식 노드들을 잘 탐색하면 문제가 풀리지 않을까? 라는 생각을 했다. 여기서 먼저 짚고 가야하는 점이 있다. f(a, b, c)를 구할 때, 중간값을 가장 크게 하려면 어떻게 해야할까? 정답은 가장 거리가 긴 노드들을 알면 된다. 예를 들어 특.. 2024. 2. 22.
[프로그래머스/C++] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 보와 기둥을 잘 구분하면 해결되는 문제다. 여기서 보를 건설 할 수 있는 조건은 양쪽에 보가 있거나, 한쪽 끝이 기둥위에 닿아있으면 된다. 기둥은 보의 한쪽 끝 위에 세우거나, 바닥, 기둥 위에 세울 수있다. 이를 고려해 보와 기둥이 세워졌는지 기록을 할 2차원 vector를 만들었다. 그리고 세워지는 위치를 기준으로 아래와 같이 정의했다. [x ,y]에 기둥이 세워졌다면 이 기둥은 [x, y]와 [x, y+1]을 차지한다는 뜻이다. [x ,y]에 보가 세워졌다면 이 보는 [x, y]와 [x+1, y]을 차지한다는 뜻이다. 이렇게 보나 기둥을 세울 수 있는지 검사하고 세울 수 있다면 보, 기둥을 세우도.. 2024. 2. 21.
[프로그래머스/C++] 리틀 프렌즈 사천성 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제의 사천성은 일반 사천성과 다르게 딱 한번만 방향을 꺾을 수 있다. 그리고 제한도 까다롭지 않기 때문에, A부터 Z까지 글자들의 위치를 저장해 뒀다. A부터 Z까지의 글자를 찾을 때, x를 기준으로 먼저 찾고 없다면 y를 증가시켜서 찾는 식으로 찾았기 때문에 특정 글자 중 y가 더 작은게 먼저 저장되도록 코드를 짰다. (y가 같다면 x가 작은 게 먼저 저장된다) 이렇게 코드를 짤 경우 두 좌표를 크게 직선과 꺾인 경우로 나눌 수 있다. 예를 들어 A라는 문자가 저장된 위치가 a, b라고 하자. 만약 a와 b의 y좌표가 같거나, x좌표가 같다면, 직선으로만 연결해 카드를 지울 수 있다. (한번만 꺾을 수 있.. 2024. 2. 20.
[프로그래머스/C++] 무지의 먹방 라이브 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 어떻게 풀까 고민을 많이 했다. 고민 끝에 크기 비교와 나누기를 잘 이용하면 쉽게 풀리겠다는 생각이 들었다. 먼저 음식을 먹는 시간인 food_times를 정렬한다. 여기서 음식을 먹는데 걸리는 시간이 가장 적은 음식을 다 먹기 전까지는 모든 음식의 개수가 그대로다. 만약 가장 시간이 적게 걸리는 음식을 다 먹었다면, 음식의 개수가 줄어든다. 그림을 보면 이해가 쉽다. 음식을 먹는데 걸리는 시간이 위와 같다고 가정하자. 그러면 먹는데 걸리는 시간이 가장 적게 드는 음식은 첫번째 음식(2) 이다. 그렇기 때문에 이 회전판이 두바퀴 돌 때 까지는 음식의 길이에 영향을 미치지 않는다. 만약.. 2024. 2. 19.
[프로그래머스/C++] 경주로 건설 (2020 카카오 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최소 비용을 구하는 탐색 문제다. 길을 연결하기 위해 드는 비용이 음의 값을 갖지 않고 시작위치와 끝 위치가 정해져있기 때문에 쉽게 풀 수 있는 문제다. 나는 BFS와 memoization을 이용해 풀기로 했다. 코너를 만들 때 비용이 추가가 되므로, 이를 구분하기 위해 방향을 구분할 필요가 있다. 그래서 내가 세로 방향으로 이동중이였는지 가로방향으로 이동중이였는지를 구분하고, 만약 가로 방향에서 세로로 방향을 바꾸거나 세로에서 가로로 방향을 바꾸면 비용을 추가해 비교하도록 코드를 구현했다. 그리고 이전에 y, x 지점을 세로방향으로 방문했을 경우 이번에 방문한 경우의 비용이 더 적다면 다시 탐색을 하.. 2024. 2. 17.
[프로그래머스/C++] 미로 탈출 (2021 카카오 채용연계형 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트랩이 있어서 경로가 계속 바뀌는게 특징인 문제다. 만약 트랩이 없다면, 특정 지점에 방문하는 가장 빠른 경로를 구하는 문제와 같기 때문에 최단 경로 알고리즘 중 다익스트라 알고리즘으로 풀 수 있다. 처음에는 최단 경로 문제인 것은 알았지만, 트랩 때문에 완전 탐색을 먼저 해보자는 생각이 들었다. 여기서 중요한 점은 특정 노드를 방문처리할 때, 트랩이 있기 때문에 한번 방문하면 다시는 방문하지 못하는게 아니라 최대 2번까지 방문이 가능하다는 점이다. 여기서 최대 2번까지 방문이 가능한 이유는 트랩을 처음 밟으면 방향이 바뀌는 경우고, 트랩을 그 다음 밟으면 원래 방향으로 바뀌는 경우다. 이후 3번 방문.. 2024. 2. 16.
[프로그래머스/C++] 자물쇠와 열쇠 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 열쇠로 자물쇠를 열 수 있는지 확인하는 문제다. 여기서 중요한 점은 열쇠의 블럭과 자물쇠의 블럭이 일치해야 하는데, 만약 열쇠의 블럭이 있는 부분이 자물쇠에 블럭이 있는 부분이라면 열지 못한다는 점이다. 그러므로 열쇠와 자물쇠가 정확히 일치해야 하는데, 자물쇠 밖에 있는 열쇠의 범위는 블럭이 있어도 되고 없어도 된다는게 특징이다. 그래서 문제를 풀 때 열쇠의 오른쪽 하단이 자물쇠 왼쪽 상단부터 시작해 전부 탐색하는 방식으로 코드를 구현했다. 위 그림에 보이는 것처럼 열쇠와 자물쇠가 겹치는 최소 범위부터 시작해 왼쪽으로 이동하고, 자물쇠의 가장 왼쪽과 열쇠의 가장 오른쪽이 겹치면 한칸 아래로 내려 다시 .. 2024. 2. 16.
[프로그래머스/C++] GPS (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정정횟수를 어떻게 하면 최소 횟수로 줄일 수 있는지를 계산하는 문제다. 중요한 점은 시간 순서대로 탐색하면서 시간을 고치는게 최선이 아니라는 점이다. 올바르게 정해진 이동경로를 고치는게 오히려 더 정정횟수가 적을 수 있다. 그래서 처음에 이 문제를 보고 BFS로 풀면서 memoization을 활용해 시간을 줄여야 겠다는 생각이 들었다. 먼저 경로를 정정하거나 정정하지 않은 경우를 queue에 넣고, BFS로 특정 시간에 어느 지점을 방문했을 때 정정횟수가 최소인 경우를 계속 저장하면서 문제를 풀었다. 이 과정에서 BFS를 실행하면 정정 횟수가 최소인 경우가 아님에도, BFS 탐색을 할 경우가 생길 수 .. 2024. 2. 15.
[프로그래머스/C++] 쌍둥이 빌딩 숲 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DP를 이용하면 빠르게 풀 수 있는 문제다. 처음에는 큰 빌딩이 새로 생긴다고 생각하고 새로 추가된 큰 빌딩을 기준으로 삼 combination을 이용해 문제를 풀려고 했다. 이렇게 문제를 풀자 문제가 풀리긴 풀리는데 수가 너무 커 1000000007로 나누어 줘야하고, 곱셈을 하는 과정에서 범위를 넘어가기도 했다. 그래서 반대로 작은 빌딩이 추가가 된다고 생각하고 문제를 풀었다. 예를 들어 앞에서 봤을 때 count가 1이고 빌딩의 수가 2인 경우에서, 빌딩의 수가 3으로 늘어난다고 생각을 하자 (2, 1) => 빌딩의 수가 2이면서 count가 1인 경우의 수 그러면 작은 빌딩사이에 큰 빌딩이 들어.. 2024. 2. 14.
[프로그래머스/C++] 행렬과 연산 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 어떻게 효율적으로 연산을 하는지가 중요한 문제다. 먼저 처음에는 단순하게 구현했다. 구현 결과 회전의 경우 값 자체를 직접 변경해줬기 때문에 시간 초과가 걸렸다. 그래서 deque를 이용해 push 와 pop을 빠르게 연산 할 수 있도록 코드를 짰다. shift연산의 경우 단순히 deque의 push와 pop을 이용하면 되기 때문에 쉽게 코드를 구현할 수 있었다. 하지만 rotation의 경우 오른쪽은 아래로 왼쪽은 위로 값들이 바뀌기 때문에 구조를 분리할 필요가 있었다. 위와 아래의 경우 값을 단순히 2차원 deque의 처음과 끝에 push와 pop을 적절히 사용하면 되기 때문에 따로 분리하지 않아도.. 2024. 2. 13.
[프로그래머스/C++] 방의 개수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 닫힌 도형이 몇개가 되는지 구하면 되는 문제다. 쉽게 생각하면 닫힌 도형이란 이미 방문한 노드를 다시 방문할 경우 닫히게 된다. 그림을 보면 더 쉽게 이해가 된다. 위 그림처럼 C에서 A방향으로 이동하고, 그 뒤 이미 방문한 노드인 A를 방문하면 닫힌 도형이 만들어지게 된다. 여기서 중요한 점은 이미 방문한 노드를 방문한다고 해서 무조건 닫힌 도형이 되는 것은 아니라는 점이다. 아래 그림에서 이미 A와 B라는 점을 방문했다고 가정하자. 이 경우 A에서 이전에 방문한 노드인 B를 방문하거나 B에서 이미 방문한 A를 방문하더라도 닫힌 도형이 새로 만들어지지 않는다. 그렇기 때문에 Set으로 A에서 B로 가.. 2024. 2. 11.
[프로그래머스/C++] 외벽 점검 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 완전탐색으로 풀 수 있는 문제다. 시계방향으로 점검을 하나 시계 반대 방향으로 점검을 하나 어차피 이동하는 거리는 같기 때문에 시계 방향으로 도는 경우만 고려하면 된다. 여기서 완전 탐색을 할 때 weak 부분에서 점검을 시작하는게 이득이다. 이 점을 고려해서 특정 weak 부분에서 어떤 weak까지 점검을 할 수 있는지 비교하면된다. 마지막 취약점 부분까지 탐색을 완료하면 탐색을 마쳤을 경우 이때 출발한 친구 수를 min값과 비교해 저장하면 된다. 여기서 또 출발을 어디서부터 하는지 생각해야 한다. 왜냐하면 계산을 편하게 하기 위해 시계 반대 방향의 탐색을 고려하지 않고 시계 방향으로 탐색만 고려했기.. 2024. 2. 10.
[프로그래머스/C++] 2차원 동전 뒤집기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에는 이 문제를 DFS나 완전탐색으로 풀어도 괜찮겠다는 생각이 들었다. 왜냐하면 가로 세로가 최대 10이였고, 한 줄을 키거나 끌 수 있기 때문에 경우의 수가 약 2^20 이고, 추가로 변환을 했을 때 일치하는지 검사를 할 경우 100개의 동전을 검사하므로 약 1억 정도면 충분하지 않을까? 라는 생각이 들었다. 문제는 완전 탐색을 했더니 시간 초과가 걸렸고, 다른 방법을 생각하게 됐다. 문제에서 핵심은 target의 y, x의 값과 beginning의 y, x의 동일한지 여부다. 즉, target의 y, x의 값과 beginning의 y, x의 값이 다르다면 가로축이나 세로축으로 바꿔야 한다는 뜻이다. 이를 .. 2024. 2. 9.
[프로그래머스/C++] 블록 이동하기 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀이만 생각하면 그렇게 어렵지 않은 문제다. 가장 빠르게 도달하는 방법을 찾는 문제이므로, BFS로 문제를 해결하면 된다. 4방향으로 이동하는 경우와, 회전하는 경우를 고려하면 되는데, 문제는 회전을 구현하는게 생각보다 힘들었다. 푸는 방법은 로봇이 가로일 경우, 세로일 경우가 있으므로 visitedHorizontal, visitedVertical 두 2차원 벡터를 이용해 이미 방문 한적이 있는지를 판단하고, 방문했다면 Queue에 넣지 않기로 했다. 여기서 일반적인 이동은 Horizontal 방향이면 visitedHorizontal에서 방문한 적이 있는지 확인하면 되는데, 회전할 경우 Horizont.. 2024. 2. 8.
[프로그래밍/C++] 헤더파일과 소스파일을 분리하는 이유 헤더파일과 소스파일을 분리하는 이유에 대해 알아보기 전에 선언과 정의에 대해 먼저 알아보자  선언과 정의" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 C++을 사용하면 int a; 와 같이 변수를 선언해 주라는 말을 들었을 것이다.선언은 말 그대로 어떤 변수나 함수를 사용하겠다고 컴파일러에게 변수의 존재와 타입을 알려주는 것이고, 정의는 변수나 함수가 어떤 값이나 동작을 하는지 정의해 메모리에 할당하는 것이다. 선언과 정의의 예는 아래와 같다. int a(int); // 선언 했지만 정의는 하지 않음extern const int a; // 선언 했지만 정의는 하지 않음extern const int b = 1; // b를 정의함struct S{ int n; // S구조.. 2024. 2. 8.
반응형

티스토리툴바