본문 바로가기

전체 글308

[프로그래머스/C++] 안티세포 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제를 처음 봤을 때 어떻게 풀지 많이 고민했다. 모든 경우를 계속해서 계산하기에는 너무 계산이 많아졌기 때문에 이전에 계산된 내용을 이용해 빠르게 문제를 풀 수 있을 것 같았다. 고민 후에 DP와 Map을 이용해 문제를 해결했다. [문제 풀이] 안티세포 X와 Y에 들어 있는 수 들을 아래와 같이 표현한다고 가정하자 $$ Y\,=\,(i_{ys},\, ...\, i_{ye})$$ $$ X\,=\,(i_{xs},\, ...\, i_{xe})$$ 여기서 안티세포 Y와 X의 합이 같아서 합쳐진다면 합쳐진 새 안티세포 N은 아래와 같이 표현할 수 있다. $$ N\,=\,(i_{ys},\, ...\, i_{xe})$$ 이제 N의 왼.. 2024. 3. 29.

[프로그래머스/C++] 튜브의 소개팅 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보고 어떤 값을 기준으로 priority_queue를 사용하거나 BFS로 풀면 되겠다는 생각이들었다. 그런데 priority_queue를 사용하면 정렬하는데 시간이 걸린다. 게다가 내가 return 할 답은 거리가 가장 짧은 값 중에서 대화시간이 가장 짧은 값이기 때문에 거리를 기준으로 정렬을 할 것이라면, BFS를 이용하면 된다. 그래서 BFS로 문제를 풀었다. BFS를 이용하면 항상 원점에서 이동한 거리가 짧은 값이 queue에서 먼저 나온다. 그러므로 이를 이용해 특정 지점에 방문할 때 마다 가지치기를 해, 쓸모없는 경우들을 가지치기 해 주었다. 가지치기를 하기 위해서 visited라는 2차원 배.. 2024. 3. 28.

[Unity] UI Text script로 변경하기 HTML 삽입 미리보기할 수 없는 소스 먼저 Hierarchy에 TextMeshPro를 추가하기 그리고 script에서 접근해 사용하기 위해 public으로 가져올 TextMeshProGui를 아래와 같이 선언 public으로 선언한 TextMeshProUGUI를 할당해주기 위해 아래 그림과 같이 TextMeshProUGUI를 drag & drop 이후 script에서 TextMeshProUGUI.text로 접근해 안에 들어갈 text를 변경해 주면 끝! 아래는 코드 예시입니다. using System.Collections; using TMPro; using UnityEngine; public class PlayerManager : MonoBehaviour { // 값 int money; int lu.. 2024. 3. 27.

[프로그래머스/C++] 가사 검색 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음 이 문제를 봤을 때 trie 알고리즘을 사용하면 빨리 문제를 해결할 수 있겠다는 생각이 들었다. 왜냐하면 특정 문자가 같은지 비교하고 수를 세는 과정에서 trie 알고리즘을 사용하면 빠르게 해결 될 것 같았기 때문이다. 문제는 조건을 제대로 안읽어서 ab?cd와 같이 중간에 ?가 들어갈 수 있는 줄 알고 코드를 구현했다. 하지만 알고보니 양 끝에만 ?가 연속적으로 들어갈 수 있었다... [문제 풀이] trie 알고리즘으로 문제를 푼 방법은 다음과 같다. 예를 들어 trie라는 문자가 들어온다고 가정하자. 이 경우 위 그림과 같이 t 뒤에는 물음표가 3개 오는 경우가 올 수 있다. 이를 map를 이용해 [문자열의 길이: 개.. 2024. 3. 27.

[프로그래머스/C++] 표 병합 (2023 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 표 병합 문제에서 중요한 명령어는 MERGE와 UNMERGE다. 다른 명령어들은 vector를 이용하면 바로 수행할 수 있지만, MERGE나 UNMERGE된 셀일 수 있기 때문에 이를 파악하는게 중요하다. 이 문제를 풀기 위해 union-find 알고리즘을 이용했다. 예를 들어 (1, 1) 셀과 (2, 2) 셀이 병합 되었다고 가정하자. 이 경우 (2, 2) 셀은 (1, 1)셀의 집합에 포함되어 있다고 표시를 한다면, (2, 2)셀의 값을 업데이트 하거나 변경할 경우 (2, 2)셀의 집합의 값을 변경하면 문제가 해결된다. UNMERGE는 반대로 한 집합에 속한 모든 원소들을 초기화 시키고 마지막에 명령어에 있는 .. 2024. 3. 26.

[프로그래머스/C++] 징검다리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 생각 났던 풀이는 가장 짧은 거리를 찾은 다음 어떤 돌을 제거할지 선택하는 방법이다. 하지만 이 방법은 최악의 경우 시간복잡도가 O(N^2)이 되기 때문에 다른 방법을 생각했다. 그러다가 바위 사이의 최소 거리를 정한 다음 돌을 몇 개 제거해야 하는지 계산하면 더 빠르게 연산이 될 것이라는 생각이 들었다. 여기서 바위 사이의 최대 거리는 도착점까지의 거리이므로 min Distance = 1, max Distance = 도착점까지의 거리로 이분탐색을 하도록 코드를 구현했다. 예를 들어 돌 사이의 최소 거리가 4라고 하면, 돌 A와 돌 B 사이의 거리는 최소 거리인 4보다 커야한다. 만약 돌 A, B 사이의 .. 2024. 3. 25.

[프로그래머스/C++] 몸짱 트레이너 라이언의 고민 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 규칙을 찾아보려고 생각했다. 규칙을 찾을 경우 인원이 최대 몇명 겹치는지 알면 쉽게 풀 수 있을 것 같았기 때문이었다. 인원이 최대 몇명 겹치는지를 계산하기 위해서 운동 시작시간을 기준으로 정렬을 한다. 운동이 끝나는 시간을 pq에 삽입하고, pq에 들어있는 시간이 다른 사람의 운동 시작 시간보다 빠르다면 그 사람은 운동이 끝났으므로 pq에서 빼준다. 이때 pq의 크기가 max인 경우가 최대 사람 수다. 하지만, 2명인 경우와 사람의 수가 n*n/2+n%2 보다 큰 경우를 빼고는 규칙을 찾기 힘들었다. 그래서 다음으로 생각한 풀이는 2명 이상일 경우에 최대 거리가 2*(n-1)이하로 나.. 2024. 3. 24.

[프로그래머스/C++] 고고학 최고의 발견 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때 어떻게 풀어야 할지 오래 고민했다. 열쇠의 모양이 십자 모양이기 때문에 맨 위 부분만 파악할 수 있으면 쉽게 풀 수 있지만, 열쇠의 정 중앙이 성궤의 테두리에 놓일 수 있기 때문이었다. 그렇게 고민하던 중 다른 사람의 힌트를 봤고, 모든 경우를 전부 탐색할 필요는 없이 첫 줄만 결정하면 된다는 것이었다. 맨 위 부분만 판단하면 되는 이유는 위 그림을 보면 알 수 있다. 양 옆에 다른 열쇠 조각에 영향을 끼치는 부분은 가운데 줄에 위치해야만 가능하다. 그렇기 때문에 남은 조각을 탐색했을 때, 맨 위 조각이 12시가 아닌 상태라면 무조건 그 아래에 있는 부분을 돌려 12시를 맞춰야 하기 때문.. 2024. 3. 23.

[프로그래머스/C++] 캠핑 (2017 카카오코드 예선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 중요한 점은 두 쐐기로 직사각형을 만들었을 때, 그 안에 다른 쐐기가 없어야 한다는 점이다. 단순히 두 쐐기를 정하고 다른 쐐기가 안에 있는지 센다면, 시간복잡도가 O(n^3)으로 매우 커지게 된다. 하지만, 정렬을 잘 한다면 O(n^2)으로도 쉽게 풀 수 있는 문제다. 한번 쐐기의 데이터들을 그림으로 생각해 보자 세로 축을 y, 가로 축을 x라고 하면, 쐐기들의 정보를 y축, x축의 순서로 오름차순 정렬을 한다. 그러면 위 그림과 같이 쐐기들의 순서가 정렬이 될 것이다. 이제 1번 쐐기부터 탐색을 시작한다. 1번 쐐기와 연결할 수 있는 쐐기들은 2~7번 쐐기다. 여기서 2, 3번 쐐기는 1번 쐐기와.. 2024. 3. 22.

[프로그래머스/C++] 선입 선출 스케줄링 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 core가 처리해야하는 작업이 있다면, 모든 작업을 처리할 경우 몇 번째 코어가 최종작업을 실행하는지를 찾는 문제다. 특정 시간에 각 core가 처리한 작업의 수를 찾는 방법은 나눗셈을 이용하면 쉽게 계산할 수 있다. 그렇기 때문에 n개의 작업을 처리할 수 있는 특정 시간을 찾으면 몇 번째 코어가 최종 작업을 실행하는지 알 수 있다. 여기서 특정 시간을 찾는 방법은 이분탐색으로 쉽게 찾을 수 있다. 이분탐색을 사용할 경우 log(N)의 시간 복잡도로 탐색을 할 수 있기 때문에 이 문제의 시간 복잡도는 코어의 수*log(N) 이 된다. 여기서 주의할 점은 특정 시간에 수행할 수 있는 작업은 0시간에는 c.. 2024. 3. 21.

[프로그래머스/C++] 동굴 탐험 (2020 카카오 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 중요한 점은 순서를 지켜서 방문하는 order의 제약사항에 있다. order에서 주어지는 데이터를 [선 방문할 방 : 후 방문할 방] 라고 하자 제약사항을 읽어보면 order에 한번이라도 나온 방인 경우 order의 다른 데이터에 나오지 않는다. 즉, 요약하면 하나의 방은 먼저 방문할 방 나중에 방문할 방 상관 없는 방 3가지 경우로 구분할 수 있다. 여기서 먼저 방문할 방이나 상관 없는 방은 언제 방문해도 상관이 없다. 중요한 방은 나중에 방문할 방이다. 나중에 방문해야하는 방은, 사전에 방문해야 하는 방이 있다는 뜻이므로 사전에 방문 해야하는 방을 먼저 방문하면 된다. 그림을 통해 더 쉽게 알아보.. 2024. 3. 20.

[프로그래머스/C++] 인사고과 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 사원보다 근무 태도 점수와 동료 평가 점수가 낮은 사원을 등수에서 제외하는게 핵심인 문제다. 그렇기 때문에 정렬만 잘 하면 쉽게 해결할 수 있다. 먼저 인사고과 중 근무 태도 점수와 동료 평가 점수 중 하나를 기준으로 정렬을 한다. 예를 들어 근무 태도점수를 기준으로 내림차순으로 정렬을 한다고 가정하자. 위 그림과 같이 정렬이 됐다면, 탐색을 시작한다. 근무 태도 점수는 이미 정렬이 됐으므로 중요한 점수는 동료 평가 점수이다. 여기서 prevMax와 nowMax 두 변수를 사용하는 이유는 근무 평가 점수가 같을 수 있기 때문이다. A 직원이 B직원보다 동료 평가 점수가 높아도 A직원과 B직원의 근.. 2024. 3. 19.

[프로그래머스/C++] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 어려운 문제는 아니지만 주소를 찾거나 단어를 찾는 과정이 생각보다 까다로웠다. 단어를 구분해 주고, 어떤 부분부터 주소를 나타내는지 찾아주어야 하기 때문이다. 먼저 점수를 계산하기 위해 특정 단어가 몇번 나왔는지 찾는 방법을 알아보자 여기서 중요한 점은 특정 단어는 대소문자 구분을 하지 않는다는 점이다. 그래서 대소문자 구분을 하지 않도록 전부 소문자로 변경을 해주었다. 특정 단어의 경우 알파벳으로만 이루어져 있어야 한다. 만약 abc라는 글자가 찾는 단어일 경우 abcabc인 단어는 내가 찾는 글자가 아니다. abc@abc인 경우에는 중간에 @가 있으므로 구분된 단어라 abc가 두개 있으므로 2점이 .. 2024. 3. 18.

[프로그래머스/C++] 호텔 방 배정 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 Set과 Map을 이용해서 이미 배정된 적이 있는 방 번호라면 바로 다음 방을 찾도록 하면 해결될 것이라는 생각이 들었던 문제다. Set에는 이미 배정받은 방들의 수를 저장하고, Map에는 [배정받길 원하는 방 : 다음에 실제로 배정받을 방]의 구조로 저장한다. 처음에 특정 방을 배정받고 싶을 때, 그 방이 Map에 없으면 첫 방문이다. 그러므로 원하는 방에 해당하는 숫자를 가져온다. 만약 Map에 있다면 첫 방문이 아니므로 이미 Map에 저장된 수를 가져온다. 이후 가져온 숫자가 Set에 있으면, 이미 배정받은 방이므로 Map에서 그 숫자가 다음에 실제로 배정받을 방의 숫자를 가져온다. 이 과정을 W.. 2024. 3. 16.

[프로그래머스/C++] 공 이동 시뮬레이션 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을때 고민을 많이 했다. 좌표의 범위가 매우 크기 때문에 모든 좌표를 직접 검사하는 것은 불가능하다. 그래서 처음 했던 생각은 시작 좌표에서 거꾸로 쿼리를 진행하면, 더 빠르게 체크를 할 수 있겠다고 생각이 들었다. x좌표와 y좌표는 서로 영향을 미치지 않으므로 1차원 좌표를 그려 풀이를 생각해보자 위 그림과 같이 쿼리를 거꾸로 진행하는데 왼쪽으로 5번 이동하라는 쿼리가 나오는 경우를 생각해보자. 이때 도착점이 3이 되려면 이전에 E의 위치는 8이여야 하는데, 실제 좌표는 7까지이므로 불가능한 경우다. 그렇다면 항상 좌표의 범위를 벗어나면 불가능한 경우일까? 위 경우에서는 E가 -1로 범위 바깥.. 2024. 3. 15.

이전 1 ··· 7 8 9 10 11 12 13 ··· 21 다음

티스토리툴바