알고리즘
1.[C++] 백준 11650 : 좌표 정렬하기
https://www.acmicpc.net/problem/11650 문제 푼 시간 : 13분 생각 흐름 정렬 규칙 x 좌표가 증가하는 순으로 정렬 x 좌표가 같으면 y 좌표가 증가하는 순으로 정렬 => pair을 사용하여 x,y 값을 vector에 저장한 후 s
2.[C++]백준 11660 : 구간 합 구하기 5
누적합(Prefix Sum) >배열의 각 위치까지의 누적합을 저장한 배열이다. 이를 통해 배열의 일부 구간의 합을 보다 빠르게 계산할 수 있다. 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n2)의 시간복잡도를 갖기 때문에 범위가 클
3.[C++]프로그래머스 : 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물
먼저 누적합에 대한 개념은 여기에 정리해뒀다:https://velog.io/@bjy6631/%EB%88%84%EC%A0%81%ED%95%A9-Prefix-Sum누적합 문제인데 어떤 식으로 누적합을 써야할 지 모르겠어서..일단 그냥 브루트포스로 풀어봤다역시나..
4.[C++] 프로그래머스 : 단어 변환(bfs,dfs)
DFS란 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프를 탐색할 때 특정한 경로로 쭉 타고 밑바닥까지 내려간 후 막다른 길에 도착하면 다시 돌아와 다른 경로로 탐색하는 것이다.스택이나 재귀함수로 구현한다.스택을 활용한 DFS시작 정점을 스택에 삽입한다
5.[C++] 프로그래머스 : 자물쇠와 열쇠
구현 알고리즘이란?머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 거의 모든 문제가 '구현 문제'인데 구현이 어려운 문제들이 있다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다.구현 문제는 모든 범위의 문제 유형을 포함하고 프로그래밍 언어의 문법
6.[C++] 프로그래머스 : 스킬트리
어제 푼 알고리즘이 구현 문제였는데 너무 어려웠어서..이번에도 구현 문제를 했다. 조금 더 낮은 난이도로!unordered_map에 각 스킬과 순서를 저장해 주었고 BOOL배열로 스킬을 배웠는지 여부를 저장하였다.skill_trees에서 스킬을 하나씩 확인하면서 해당
7.[C++] 프로그래머스 : 정수 삼각형
DP는 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 정답을 구한 작은 문제의 답은 어딘가에 저장해 놓고 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이다.1\. 작은 문제가 반복이 일
8.[C++] 프로그래머스: 도둑질
DP문제인 걸 알고 봐서 어떻게든 생각을 했는데 뭔가 알듯말듯..했다.처음 코드를 짤 때, dpi-1의 값과 비교하지 않아서 틀렸었다. 그래서...쪼금 도움을 받아서 풀었다.문제 링크:https://school.programmers.co.kr/learn/cou
9.[C++] 프로그래머스 : 가장 먼 노드
그래프는 여러 개의 점(노드 또는 정점)들이 선으로 연결된 구조vertex : 그래프의 구성 요소 (=Node,정점)Edge : 정점간 연결 관계Weight: 간선의 크기가 있는 경우, 가중치값 무방향 그래프 : 방향이 없는 그래프. 노드와 노드가 간선으로 이루어져 있
10.[C++] 프로그래머스 : 합승 택시 요금
다익스트라 알고리즘은 그래프에서 한 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘 입니다. 동작 과정1\. 출발 노드와 도착 노드를 설정하여 최단 거리 테이블을 초기화 한다.현재 위치한 노드의 인접 노드 중에서 방문하지 않은 노드들 중 거리가 가장 짧은 노
11.[C++] 프로그래머스 : 도넛과 막대그래프
처음에 이 문제를 보고 어떤식으로 풀어야 할 지 막막해서 예시를 보면서 생각 정리를 해보았다.이 그림을 보면 일단 2라는 점이 생성한 정점이고 2번이 가리키는 1번은 도넛 모양 그래프, 그 다음 3번은 막대 모양 그래프이다. 먼저 생성한 정점을 찾는다. 그래프의 수는
12.[C++] 프로그래머스 : 입국심사
이분 탐색(이진 탐색) : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이분 탐색은 배열 내부의 데이터가 정렬되어야만 사용할 수 있는 알고리즘찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는것이분탐색으로
13.[C++] 프로그래머스 : 징검다리
이분탐색 문제인 걸 알고 계~속 생각해봤지만 진짜 어떤 식으로 접근해야 할지 모르겠어서 찾아봐서 풀었다..start = 1, end = distance로 두고 mid값을 기준으로 mid보다 거리가 작으면 돌을 제거하는 방식으로 구하는거였다. 예시)start = 1, e
14.[C++] 프로그래머스 : 섬 연결하기
그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 탐욕적으로 푸는 알고리즘 이다.한 마디로 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해
15.[C++] 프로그래머스 : 단속 카메라
진출 지점을 기준으로 정렬하여서 첫 번째 차량의 진출 지점에 카메라를 설치하고 계속 반복하며 다음 차량의 진입 지점이 카메라 설치보다 전인지 확인하여 설치보다 전이라면 계속해서 탐색하고 카메라 설치 후라면 그 차량의 진출 지점에 카메라를 설치하고 그 위치를 기준으로 계
16.[C++] 프로그래머스 : 구명보트
가장 무거운 사람과 가장 가벼운 사람을 더해서 limit값보다 작으면 같이 구명보트에 타고 아니면 무거운 사람만 타도록 코드를 작성하였다.아이디어는 빨리 생각해냈는데 문제에서 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고 를 제대로 못봐서 시간이 좀 걸렸다.
17.[C++] 프로그래머스 : 기지국 설치
처음에는 이런식으로 하나씩 비교하면서 코드를 작성해주었는데 정확성은 맞는데 시간초과 때문에 틀렸었다. 그래서 좀 찾아보면서 다시 작성하였다..현재 시점이 기지국 전파 범위에 들지 않으면 현재 시점부터 전파 범위 시작 전까지의 아파트 수를 이용하여 설치해야 하는 기지국의
18.[C++] 프로그래머스 : 등굣길
초기에 시작점은 1로, 물이 잠긴 지역은 -1로 하고 나머지는 0으로 채워줬다.그리고 위에서부터 차례대로 위아래를 더해주었고, 물이 잠긴 지역은 더하지 않고 넘어가면서 풀었다.
19.[C++] 프로그래머스 : N으로 표현
이것저것 참고해가면서 풀었다........🫠N = 5라면5를 1개 사용 55를 2개 사용55, 5+5, 5-5, 5/5, 5\*55를 3개 사용5555+(5+5), 5+(5-5), 5+(5/5), 5+(55),5(5+5), 5(5-5), 5 (5/5), 5(55),5
20.[C++] 프로그래머스 : 네트워크
깊이 우선 탐색으로 풀었다! 처음에 dfs에 주소값으로 visited랑 v를 주지 않아서 답이 안 나왔었다. 이번꺼는 괜찮았다
21.[C++] 프로그래머스 : 네트워크
dfs를 이용해서 풀었고 i=0부터 탐색하면서 방문하지 않았다면(visited == false) dfs를 이용해서 이어진 노드들을 방문하고 answer을 1 증가시켜주었다.
22.[C++] 프로그래머스 : 여행경로
23.[C++] 백준 : 31403번 A + B - C
사실 브론즈4문제라 어렵지는 않은데 string -> int 나 int -> string으로 형 변환하는 함수가 헷갈려서 정리를 해놔야겠다고 생각했다. 첫 줄에는 A,B,C를 수로 생각했을 때, 둘째 줄에는 A,B,C를 문자열로 생각했을 때 값을 출력하는거다.strin
24.[C++] 백준 : 28702번 FizzBuzz
class문제들을 풀고 있는데 2에서 안 푼 브론즈1 문제가 있어서 풀어봤다. 문자열 중에 숫자로 된 문자열을 찾고 싶은데 어떤 함수를 써야할 지 몰라서 찾아 보았다. int atoi(const char \*);atoi는 해당 문자가 숫자이면 숫자로 변환해주고 아니면
25.[c++] 백준 : 11430번 경로찾기
계속 풀었는데 시간초과가 나서 미쳐버리는 줄 알았다..계속 보완한다고 보완해서 아래코드까지 작성했는데 출력결과는 잘 나오는데 시간초과가 나서 어쩔 수 없이..지피티의 힘을 조금 빌렸다..array의 값이 1인지 0인지 판단하여서 0이면 깊이탐색을 해주니 시간초과가 해결
26.[C++] 백준 25206번 : 너의 평점은
https://www.acmicpc.net/problem/25206오랜만에 c++푸니까 다 까먹어서 하나씩 찾아보면서 풀었다. 20개 전공의 전공평점을 구하는거였다. 오랜만에 푸니까 string이 스페이스까지 같이 입력받는 줄 알고 stringstream을 써
27.[C++] 백준 2563번 : 색종이
요즘 알고리즘 감각을 잃어서 백준에서 단계별로 풀어보고 있다. 2차원 배열이었는데 위의 문제를 보고 2차원 배열로 어떻게 접근해야할지 감이 안 잡혔다. 그냥 전체에서 겹치는 부분을 빼주는 풀이로 해봤는데 너무 복잡하고 이게 맞나..? 싶었다....일단 백준 예시는 통과
28.[C++] 백준 2581번 : 소수
이 문제를 보고 M과 N의 사이의 수들을 하나씩 돌면서 이 수가 소수인지 아닌지 알아내면서 풀자고 생각했다. 그래서 완전탐색 방법으로 풀고 예제까지 잘 출력이 되어서 제출하였는데 틀렸다고 나왔다...!그래서 다시 생각해보니까 내가 1이나 2에 대한 예외처리를 안해줘서
29.[C++] 24267번 : 알고리즘 수업 - 알고리즘의 수행 시간 6
브론즈 문제라 쉬운문제이지만 조금 헷갈려서 종이에 적어가며 풀었다. 근데 맞는것 같은데 계속 틀리다고나오는거...!!!!그래서 질문 게시판을 조금 참고해서 내가 뭐때문에 틀렸나 찾아보는데 내가 for문을 돌리면서 i를 습관적으로 int로 줘서 틀린거였다..! 다음부터는
30.[C++] 24313 : 알고리즘 수업 - 점근적 표기 1
이번꺼는 테스트 코드의 해설을 보고 바로 풀어서 냈었는데 계속 91퍼에서 틀렸다고 떠서 진짜 뭐가 문제지 계속 고민했다. 그러다가 질문 게시판에서 나와같이 91퍼에서 틀렸다는 사람의 질문의 답을 보고 힌트를 얻고 다시 고민해보았다.처음에 답글에서 n은 1~100사이 범
31.[C++] 백준 2485번 : 가로수
처음에 lastNum 대신에 벡터로 뒤에 계속 숫자를 넣어줬었는데 그거 때문에 메모리 초과가 되었다. 마지막 값만 필요해서 굳이 벡터를 사용할 필요가 없는데 반복해서 최기화하고 내부에 값을 넣는것이 문제였던 것 같다. 항상 메모리는 신경 안쓰고 문제를 풀었는데 이제는
32.[C++] 백준 13909번 : 창문 닫기
소수, 약수 관련 문제를 푸는데 이 문제는 잘 봐도 모르겠어서 하나씩 적으면서 해보았다. 그래서 약수 개수가 관련된건 알았는데 x의 약수 개수가 홀수이려면 어떤수의 제곱수여야 한다는것을 생각하지 못했었다.(질문게시판 보고 알았음) 약수 개수 관련된거면 제곱수인지 판단은
33.[C++] 4779번 : 칸토어 집합
테스트는 잘 되는데 계속 내면 출력초과가 떴다. 그래서 보니까 파일 끝에서 멈춰줘야 해서로 while문의 조건을 바꿔줬는데도 계속 틀렸다고 떴다. 계속 질문게시판을 찾아보면서 나와 비슷한 오류인 사람들을 참고했는데 밑에처럼 바꾸니까 되었다.https://www
34.[C++] C++에서의 형 변환
알고리즘을 풀 때 C++ 형변환이 많이 사용되는데 제대로 공부해 본 적이 없어서 정리해봤다.