https://school.programmers.co.kr/learn/courses/30/lessons/250137?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 그냥 구현문제 부분문제를 나누자면 1. 몬스터에게 공격받을 때 2. 몬스터에게 공격 안받을 때 (붕대 감아야 함) 부분문제를 나눠서 상황에 따라 구현하면 실수를 줄일 수 있다. 2. Code #include #include #include using namespace std; int solution(vector bandage, int health, vect..
전체 글
https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 1. Logic 처음에 DP로 될거같아서 시도했는데 DP는 vis배열을 찍고 나오기 때문에 최단거리 계산이 안된다. 그리고 vis배열을 기록을 안하게 되면 루프를 계속 들어가기 때문에 힙이 터진다..ㅋㅋㅋㅋ 결국 BFS 느낌으로 해결 이 문제에서 " 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다."는 배수만큼 앞으로 이동 + 배수만큼 뒤로 이동할 수 있다. 2...
1. 단일 연결 리스트란? 각 요소들이 데이터부분과 다음 값 주소를 포인팅하는 노드라는 형태로 이루어져 있으며 체인 형태로 선형으로 이루어진 자료구조이다. 값을 추가할 때 배열은 정해진 사이즈를 넘으면 Overflow가 발생하지만 Linked List는 동적으로 할당해서 노드들을 이어주면 되기 때문에 메모리 사이즈 문제에서 벗어날 수 있다. 하지만 노드들이 서로 체인형태로 이어져 있어 배열처럼 인덱스 개념으로 접근이 불가하기 때문에 순회하여 값을 찾아야 하으로 탐색에 있어서는 배열보다 느리다. 하지만 값을 중간에 넣는 경우 배열은 중간에 값을 삽입하고 한칸씩 뒤로 미뤄줘야 하기 때문에 원소의 갯수에 따라 시간이 차이가 나는 방면, 연결 리스트의 경우 단지 노드의 포인팅만 바꿔주면 되기 때문에 최악의 경우..
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. Logic 입력을 인덱스로도 받지만 string으로 받은 후 0의 위치를 찾고 그 상태에서 옮길 수 있는 좌표를 찾아 BFS 브루트포싱한다. 방문처리를 어떻게 해야 할 지 고민이었는데 map / set을 활용하여 중복이 되지 않도록 처리해줬다. map을 활용한 풀이, set을 활용한 풀이 둘 다 해봤다 2. Code map을 활용한 풀이 #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. Logic 정사각형이 같은 섬에 잇는 조건은 가로, 세로, 대각선으로 걸어서 갈 수 있는 경로가 있어야 한다. 즉 8방향 탐색을 해서 섬의 갯수를 구해주면 된다. 2. Code #include using namespace std; int graph[51][51]; bool vis[51][51]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[8] ..
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 1. Logic 여기서 주의해야 할 점은 바이러스가 퍼지면서 비활성 바이러스에 닿게 되면 그 부분은 시간으로 처리를 안해준다. 문제에 따로 명시는 되어있지 않지만 테스트 케이스를 설명해주는 그림을 잘 보면 그렇게 되어있다... 1. 문제를 푸는 로직은 먼저 입력받으면서 바이러스가 있는 좌표를 저장해놓는다. 2. 바이러스를 활성화 할 수 있는 갯수가 정해져있기 때문에 조합을 활용해서 m개만큼 활성화 할 바..
1. Queue란? 선입 선출(First In First Out) 즉 먼저 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 우리의 실생활에서 가장 많이 볼 수 있다. ex) 대기열, 프린터 큐 시간 복잡도 : O(1) 2. Queue 구현 구현해본 기능은 1. Push : 원소를 큐에 넣음 2. Pop : 큐에 가장 먼저 들어간 원소를 제거 3. Front : 큐에 가장 먼저 들어간 원소를 출력 4. Size : 큐에 들어가있는 원소의 갯수를 출력 5. IsEmpty : 큐가 비었는지 확인 6. IsFull : 큐가 다 찼는지 확인 나는 처음에 사용자한테 queue의 사이즈를 입력받아서 구현했고, 원형 큐 형태로 구현했기 때문에 실제로 사용자가 입력한 큐의 사이즈보다 -1만큼 적게 사용한다..
SOLID 원칙이란? 시간이 지나도 유지 보수와 확장이 쉬운 시스템을 만들기 위해 추구해야하는 원칙이다. SOLID는 1. 단일 책임 원칙 (SRP - Single responsibility principle) 2. 개방-폐쇄 원칙 (OCP - Open/closed principle) 3. 리스코프 치환 원칙 (LSLiskov substitution principle) 4. 인터페이스 분리 원칙 (Interface segregation principle) 5. 의존관계 역전 원칙 (Dependency inversion principle) 위 5개의 원칙의 첫글자를 따서 만든 단어이다. 5개의 원칙들에 대해 알아보자! 1. 단일 책임 원칙 (SRP - Single responsibility principl..
https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. Logic 다른 분들의 풀이를 본 결과 내가 푼 방식인 위치마다 주위의 쓰레기 여부를 판단하는 방법이 있고 먼저 쓰레기 여부를 판단하여 배열에 넣은 후 다익스트라를 돌리는 방법 이렇게 2가지가 가장 대표적인 풀이인 것 같다. 내가 푼 방식인 위치를 옮길 때 마다 쓰레기 여부를 판단하는 방법은 1. 입력을 받고 시작, 도착 위치를 기록 후 2. 다익스트라를 실행 하..
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 1. Logic 시작점에서 출발해서 다른 정점들을 거쳐 n-1번째 노드에 도착 하는 최단 거리를 구해야 하기 때문에 다익스트라를 사용해서 풀었다. 와드나 시야가 있는지를 체크하기 위해 bool sight배열을 선언 후 sight배열이 true면 continue하도록 조건을 넣어준 후 다익스트라를 돌리면 된다. 2. Code #include using namespace s..