알고리즘
우선순위 큐
1. Comparable, Comparator를 이용한 오름차순 compareTo를 구현 함으로 r변수를 기준으로 오름차순 정렬한다. Comparator를 구현한 다음, 정렬을 할때 객체를 같이 넘긴다. 내림차순은 o2.r - this.r 같이 순서만 바꿔주면 된다. import java.util.Arrays; import java.util.Comparator; public class 정렬 { static class Pair implements Comparable { int r, c; public Pair(int r, int c) { this.r = r; this.c = c; } @Override public int compareTo(Pair o) { //r기준 오름차순 정렬하고 싶음 return thi..
비트연산자
1. 비트연산자 1) & : 비트가 둘다 1인 경우만 결과가 1 나온다. 2) | : 비트가 하나라도 1인 경우 결과가 1 나온다 3) 1
[백준 1405] 미친 로봇
https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 유형 dfs 로직 dfs를 돌린다 -> 재방문 하는 곳은 리턴 -> dfs를 돌리면서 방향에 맞는 확률도 같이 계산해서 파라미터로 넘겨준다 -> 주어진 N 만큼 깊이로 탐색을 했을 시 확률을 더해준다 코드 package 백준; import java.util.Scanner; public class 미친로봇1405 { static int dr[]= {0,0,1,-1}; static int dc..
프로그래머스 level2 - 소수 찾기
https://programmers.co.kr/learn/courses/30/lessons/42839?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이방법 sort로 최대값 구하기 최대값까지 소수 찾기 찾은 소수를 string으로 바꿔 numbers에 포함되면 answer증가 #include #include #include #include using namespace std; int answer =0; int numSize = 0; bool cmp(char a, char b) { return a > b; } void isCheck..
프로그래머스 level2 - 프린터
https://programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 필요개념 덱에 대한 개념 for(auto) 를 이용하여 덱 탐색 pair 사용 법 flag를 다뤄서 맞는 조건에 찾기 /* --스택을 탐색 방법? -- */ #include #include #include using namespace std; int solution(vector priorities, int location) { int answer = 0; deque q;//인덱스, 우선순위 vector res..
SWEA level3 - 부분 수열의 합
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 재귀함수를 잘 나타내는 문제 처음 재귀호출은 arrIdx부분 arr을 선택하겠다는 뜻 두번째는 선택 안 하겠다는 뜻 solution(arrIdx + 1, sum + arr[arrIdx]); solution(arrIdx + 1, sum); /* -- 재귀사용 */ #include using namespace std; i..
2017 카카오코드 본선 - 단체사진 찍기
https://programmers.co.kr/learn/courses/30/lessons/1835 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 중요개념 next_permutaion(배열의 시작주소, 끝 주소) : 순열을 구해준다, algorithm 헤더 #include #include #include #include using namespace std; bool pos_check(vector s, vector data) { for (int i = 0; i < data.size(); i++) { int first; int second; int num =..
2019카카오 인턴쉽 - 불량 사용자
https://programmers.co.kr/learn/courses/30/lessons/64064# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 금지된 아이디가될 가능성이 있는 user_id를 찾아서 vector를 만든다 만들어 놓은 vector를 재귀함수와 비트마스크를 이용하여 중복되지 않게 만든다 중요 개념 1001 | 0110 -> 1111 1001 & 0110 -> 0000 1>3 -> 1 1을 오른쪽으로 3만큼 이동 bool visited[1 배열크기가 2^8이다. 왜? 1을 8만큼 이동하고 10진법으로 바꿨기 때문. 비트마스크 관련 링크 ..
2020 카카오 기출 괄호 변환
https://programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 유형: 문자열 변환 is_check()에서 stack을 활용하여 "올바른"인지 "균형잡힌" 인지 구분한다 is_check()에서 "올바른"과 "균형잡힌"의 경계선을 구한다. substr을 활용하여 u,v로 나눈다 /* main 입력 ans+=solution 출력 solutioin w if 빈 문자 리턴 flag = is_check w pos를 구했으니 u,v 알 수 있음 if 균형이면 tmp = ( + sol..
백준 16234 인구 이동
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 유형: bfs, 시뮬레이션 나라별로 구분 map을 구분 짓는다. bfs로 알 수 있음 bfs가 끝 났을 때 avg함수를 사용하여 ma..
백준 15686 치킨 배달
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 치킨집을 선택, 재귀를 사용 집에서 선택한 치킨집 중에서 거리가 최소인 것을 선택 위 에서 구한 거리를 모두 더한다 /* 치킨집을 m..
백준 15685 드래곤 커브
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 유형: 시뮬레이션 방향의 규칙성을 먼저 찾는다. 시작점에서 벡터의 정보대로 드레곤 커브를 완성한다 map에 1로 업데이트 한다 주어..
15684 사다리 조작
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net 유형: 시뮬레이션 재귀를 이용하여 막대기의 조합 만들기. (선택,비선택) check함수를 만들어 col이 원 위치로 오는지 확인 /..
15683 감시
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 유형: 시뮬레이션 1. 한 방향만 보는 함수를 생성 see함수 생성 2. cctv 갯수만큼 재귀함수를 돌린다 3. cctv타입 마다 볼 수..
14891번 톱니바퀴
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 유형: 시뮬레이션 /* sol for 0이상 if 6,2 같으면 break else 방향left = 방향right *-1 for 4미..