본문 바로가기
반응형

전체 글308

[프로그래머스/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.
[프로그래머스/C++] 보석 쇼핑 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 이 문제는 연속 된 구간을 선택하고 모든 종류의 보석을 전부 구매할 수 있는지를 계산하는 문제다. 구간을 2중 for문으로 탐색할 경우 O(N^2) 이지만, 누적 합과 비슷하게 특정 자리의 보석이 빠지거나 들어올 때, 그 보석의 개수를 고려하면 쉽게 풀 수 있는 문제다. 먼저 모든 종류의 보석의 수를 구한다. 그리고 구간의 시작지점 st와 끝나는 지점 ed를 정한다. 이후 처음 보석부터 모든 종류의 보석이 모일때까지의 구간을 구한다. 이제 모든 종류의 보석이 모였다면 st를 한 칸씩 앞으로 당기면서 보석을 뺀다. 만 보석을 뺐는데 그 보석의 수가 0이라면, 모든 보석을 구매할 수 없는 경우이므로, 구간의 끝인 e.. 2024. 2. 7.
[프로그래머스/C++] 등대 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 주의해야하는 점이 A와 B 등대가 있다면 두 등대 중에 한 등대는 무조건 켜져있어야 한다는 점이다. 위 그림과 같이 등대가 켜져 있어도, A와 B 등대 사이에 불이 켜져있지 않기 때문에 정답이 될 수 없다. A와 B 등대중 하나가 켜져있어야 된다. 이제 문제를 풀때 사이클이 없으므로 하나의 트리로 볼 수 있다. 이를 이용해 1을 트리의 최상단 노드라고 가정하고, leaf 노드를 찾는다. 여기서 leaf 노드를 찾을 경우 leaf 노드의 불을 켜는 것 보다 부모 노드의 불을 켜는게 더 좋다. 왜냐하면 leaf 노드는 연결된 노드가 하나이고, leaf 노드의 부모 노드는 최상단 노드인 1을 제외하면 연결된.. 2024. 2. 7.
[프로그래머스/C++] 베스트앨범 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 stl중 map을 사용하면 쉽게 풀 수 있는 문제다. map을 이용해 장르별로 재생 횟수를 더해 계산을 한다. 그리고 map을 하나 더 만들어 장르별로 index의 위치와 재생횟수를 저장하는 vector를 value로 만든다. 이렇게 두개의 map을 만든 뒤, 장르별 재생 횟수를 저장한 map을 vector로 변환해 정렬한다. 재생 횟수가 많은 순서대로 정렬된 map을 이용해 가장 재생횟수가 많은 장르부터 for문을 돌린다. for문을 돌리면서 장르별로 index와 재생횟수가 저장된 map을 다시 재생횟수 순서로 정렬하면 된다. (이때, 장르별로 index와 재생 횟수를 vector에 넣을때 index.. 2024. 2. 6.
[백준/C++] 6086번 - 최대 유량 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 network Flow문제와 같다. 같은 지점에서 같은 지점으로 연결된 관은 병렬연결이므로 흐를 수 있는 유량에 더해준다. 그리고 양방향으로 흐를 수 있다고 했으므로 이 점도 고려해 흐를 수 있는 유량에 더해주면, Network Flow 문제가 된다. ​ Network Flow 문제를 푸는 방법을 간단하게 소개하면 1. 유량 보존의 법칙 유체가 나오는 부분을 source, 들어오는 부분을 sink라고 하는데, 이 두 부분을 제외하고는 각 정점에서 들어오는 유량과 나가는 유량이 일치해야 한다. 2. 유량의 대칭성 f(u, v) = A 가 u에서 v로 A 만큼 유체가 흐르는 것을 의미한다고 하자. 그러면 .. 2024. 2. 5.
[프로그래밍/C++] 스레드(Thread) 사용하기 (2) HTML 삽입 미리보기할 수 없는 소스 스레드에서 컨텍스트 스위치란? 특정 스레드를 실행하다가 다른 스레드를 실행하는 과정을 의미한다. 그렇다면 왜 중간에 다른 스레드를 실행하는 걸까? 프로그램을 실행하다 보면 동시에 여러 프로그램이 실행되는 걸 볼 수 있다. 물론 여러 코어에서 동시에 프로그램을 실행해 작업을 할 수도 있지만, 하나의 코어에서 순간적으로 A작업, B작업을 번갈아가며 실행해 동시에 실행되는 것처럼 보이게 할 수도 있다. 즉, 여러 작업이 동시에 실행되도록 번갈아가며 실행하기 위해 컨텍스트 스위칭을 한다고 생각하면 된다. 여기서 멀티 스레드를 사용할 때, 주의해야 할 점이 있다. 예를 들어 A=10 이고, 스레드 1은 A+=1이라는 연산을 하려고 한다. 스레드 2는 A*=2라는 연산을 하려.. 2024. 2. 4.
[프로그래머스/C++] 보행자 천국 (2017 카카오코드 예선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제풀이] 이 문제는 아래와 오른쪽으로만 차량이 이동할 수 있다. 그리고 통행이 전부 가능한 구간과 차량의 통행이 금지된 부분, 우회전 및 좌회전을 하지 못하는 구간 3개로 나눠져 있다. 그러므로 내가 원래 아래방향으로 이동하고 있었는지, 오른쪽 방향으로 이동하고 있었는지를 알고 있으면 쉽게 풀 수 있다. 그래서 내가 원래 이동하는 방향이 아래방향인 경우의 수를 기록할 2차원 vector와 오른쪽 방향으로 이동하던 경우를 기록할 2차원 vector를 만들었다. 그리고 for문을 돌려 현재 위치가 모든 차량이 이동가능한 부분이라면, 내 위치에서 아래로 가는 차량과 오른쪽으로 가는 차량의 수를 합쳐 아래와 오른쪽으로 이동하는 차.. 2024. 2. 4.
[프로그래밍/C++] 스레드(Thread) 사용하기 HTML 삽입 미리보기할 수 없는 소스 프로그램이 실제로 실행되서 돌아가고 있는 상태를 프로세스라고 한다. 여기서 하나의 프로세스는 최소 한개 이상의 스레드를 가지고 있으며 프로세스 내의 자원을 공유할 수 있다. 이 스레드가 프로그램이 실행되는 기본 단위다. 프로그램은 CPU의 코어에서 실행이 되는데, 코어는 한 번에 한 가지 연산만 할 수 있다. 하지만 컴퓨터가 발전하면서 CPU에 들어있는 코어 수가 늘어났고, 여러 개의 코어를 사용해 동시에 스레드를 실행하고 여러 작업을 병렬적으로 처리할 수 있게 됐다. 이제 C++에서 실제로 스레드를 구현해 사용해 보자 HTML 삽입 미리보기할 수 없는 소스 일단 C++에서 스레드를 사용하기 위해서는 #include 라는 헤더가 필요하다. #include #incl.. 2024. 2. 3.
[프로그래머스/C++] N으로 표현 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 횟수가 8이라 DFS로 쭉 풀어도 되겠다는 생각이 들었다. DFS로 풀 경우 현재 숫자 Num과 NNN, 111과 같은 숫자들을 DFS로 연산하기만 하면 된다. 왜냐하면 N으로 특수하게 만들 수 있는 숫자들로 계산을 다 해주었기 때문에, 연산하는 과정에 다 포함이 되기 때문이다. 문제를 풀고 나서 다른 사람의 풀이를 보니 DP를 이용해 푼 풀이들이 보였다. T번 써서 만든 숫자들 = [T-n번 써서 만든 숫자들] (사칙연산) [n번 써서 만든 숫자들] 과 같은 형태로 풀었는데, 이렇게 보니 좀 더 풀이가 깔끔해 보였다. 문제가 크게 어렵진 않았는데, 연산을 코드로 작성하는게 그냥 좀 오래.. 2024. 2. 2.
[프로그래머스/C++] 재밌는 레이싱 경기장 설계하기 (2023 현대모비스 알고리즘 경진대회 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음에 이 문제를 봤을 때, 적당히 잘 자른다음 옆으로 밀면서 비교하면 되지 않을까?라고 생각했다. 그런데 옆으로 밀면서 비교해도 특수한 경우가 있어서, 단순 비교로는 풀 수 없을 것이라 생각하고 다른 사람의 힌트를 참고 했다. 알고보니 풀이는 비슷한데 숫자의 개수가 홀수인 경우와 짝수인 경우를 구분해서 생각해야했다. 나는 계속 홀수개의 숫자에서 고민을 하다보니 어려웠던 것이다... [문제 풀이] 먼저 숫자가 짝수개일 때는 정렬을 한 다음 절반을 나눠서 비교하면 된다. [짝수일 경우] 아래 그림과 같이 한 다음 숫자의 배치를 b1, a1, b2, a2 순서로 배치한다. 여기서 a1을 먼저 배치하지 않고 b1을 배치하는 이유는 .. 2024. 2. 2.
[프로그래머스/C++] 가장 긴 팰린드롬 (feat. Manacher's Algorithm) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보자마자 O(n^2)으로 해결 되겠다고 생각이 들었다. 문자열의 사이즈가 작았기 때문이다. 하지만 더 효율적인 알고리즘이 뭐가 있을까 찾아보다가 Manacher's Algorithm을 알게 됐다. Manacher's Algorithm을 처음 봤을 때, 설명이 많이 복잡하다는 생각이 들었다. [참고] https://www.crocus.co.kr/1075 https://m.blog.naver.com/jqkt15/222108415284 즉 Manacher's Algorithm을 요약하면 이전에 Palindrome인지 체크한 것을 이용한 것이다. for문으로 앞에서 부터 문자열이 Palindrome인지 체크하.. 2024. 2. 1.
반응형

티스토리툴바