Category: Programming
백준 - 백트래킹
백준 백트래킹백트래킹 문제 이름 링크 정리여부 비고 1987 병든 나이트 https://www.acmicpc.net/problem/1987 2580 스도쿠 https://www.acmicpc.net/problem/2580 4574 스도미노쿠 https://www.acmicpc.net/problem/4574 6603 로또 https://www.acmicpc.net/problem/6603 9663 N-Queen https://www.acmicpc.net/problem/9663 16987 계란으로 계란치기 https://www.acmicpc.net/problem/16987
백준 - 이분탐색
백준 이분탐색이분 탐색 문제 이름 링크 정리여부 비고 1920 수찾기 https://www.acmicpc.net/problem/1920 1939 중량제한 https://www.acmicpc.net/problem/13397 2110 공유기 설치 https://www.acmicpc.net/problem/2210 2343 기타레슨 https://www.acmicpc.net/problem/2343 O 겁나 많이 틀림 2792 보석상자 https://www.acmicpc.net/problem/2792 O 중요! 다시 풀어보기 2805 나무자르기 https://www.acmicpc.net/problem/2805 2869 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 3020 개똥벌레 https://www.acmicpc.net/problem/3020 10815 숫자카드 https://www.acmicpc.net/problem/10815 10816 숫자카드2 https://www.acmicpc.net/problem/10816 13397 구간 나누기2 https://www.acmicpc.net/problem/13397
백준 - BFS
백준 BFSBFS기본 유형 문제 이름 틀린횟수 정리여부 비고 c++ java python 1260 DFS와 BFS 기초 O 1953 팀 배분 0 O 이분 그래프 2178 미로 탐색 최단 거리 O O O 전체 문제 문제 이름 틀린횟수 정리여부 비고 c++ java python 1012 유기농 배추 2 O 1194 달이 차오른다, 가자 1 O 1260 DFS와 BFS 기초 O O 1600 말이 되고픈 원숭이 5 O 1707 이분 그래프 4 O 1726 로봇 1 O 1939 중량제한 3 O 1953 팀 배분 0 O 이분 그래프 O 1963 소수 경로 0 O 1967 트리의 지름 2 O 2146 다리 만들기 5 O 2178 미로 탐색 최단 거리 O O O 2206 벽 부수고 이동하기 5 2251 물통 0 2234 성곽 0 2468 안전 영역 2 2573 빙산 3 2583 영역 구하기 1 2589 보물섬 0 2606 바이러스 0 2644 촌수 계산 0 2667 단지번호 붙이기 4 2933 미네랄 5 5014 스타트와 링크 1 5213 과외맨 6 5427 불 2 6087 레이저 통신 0 6593 상범 빌딩 1 7576 토마토 1 9019 DSLR 4 9205 맥주 마시면서 걸어가기 3 9372 상근이의 여행 1 12886 돌 그룹 1 15558 점프 게임 11 16236 아기 상어 4 O bfs를 통해 거리구하기 16397 탈출 5 16933 벽 부수고 이동하기3 6 16959 체스판 여행 1 0 17471 게리맨더링 4 O 조합, bfs, 삼성 17836 공주님을 구해라 5 18809 Gaaaaaaaaaarden 0 조합, bfs, 삼성
백준 - 문자열 처리
백준 문자열 처리문자열 처리 문제 이름 정리여부 비고 cpp java python 1032 명령 프롬프트 문자열 속 문자, 문자열 비교 O O O 1152 단어의 개수 문자열 분리, 문자열 토큰화 O O 1157 단어 공부 소문자 -> 대문자 O O 1296 데이트 문자열 정렬 O O O 1316 그룹 단어 체커 문자열 속 문자 찾기 O O O 1475 방 번호 문자열 속 문자 O O 2064 IP 주소 토크나이징 O 2743 단어 길이 재기 문자열 길이 O O O 2857 FBI 문자열 속 단어 찾기 O O O 2902 KMP는 왜 KMP일까? 문자열 토큰화 O O O 2908 상수 문자열 뒤집기 O O 2941 크로아티아 문자 문자열 속 문자 찾기, 문자열 대치 O O O 5586 JOI와 IOI 문자열 분리substr O O O 10808 알파벳 갯수 10809 알파벳 찾기 문자 check하는 방법, dic 사용 방법 O 11654 아스키 코드 아스키 코드 변환 O
백준 - 삼성 기출문제
백준 삼성 기출문제삼성 기출 문제 문제 이름 링크 정리여부 비고 1012 유기농 배추 https://www.acmicpc.net/problem/1012 1600 말이 되고픈 원숭이 https://www.acmicpc.net/problem/1600 1707 이분 그래프 https://www.acmicpc.net/problem/1707 1726 로봇 https://www.acmicpc.net/problem/1726 1939 중량제한 https://www.acmicpc.net/problem/1939 1953 팀 배분 https://www.acmicpc.net/problem/1953 O 이분 그래프 1963 소수 경로 https://www.acmicpc.net/problem/1963 1967 트리의 지름 https://www.acmicpc.net/problem/1967 2146 다리 만들기 https://www.acmicpc.net/problem/2146 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2251 물통 https://www.acmicpc.net/problem/2251 2468 안전 영역 https://www.acmicpc.net/problem/2468 2573 빙산 https://www.acmicpc.net/problem/2573 2583 영역 구하기 https://www.acmicpc.net/problem/2583 2589 보물섬 https://www.acmicpc.net/problem/2589 2606 바이러스 https://www.acmicpc.net/problem/2606 2644 촌수 계산 https://www.acmicpc.net/problem/2644 2667 단지번호 붙이기 https://www.acmicpc.net/problem/2667 2933 미네랄 https://www.acmicpc.net/problem/2933 5014 스타트와 링크 https://www.acmicpc.net/problem/5014 5213 과외맨 https://www.acmicpc.net/problem/5213 5427 불 https://www.acmicpc.net/problem/5427 6087 레이저 통신 https://www.acmicpc.net/problem/6087 6593 상범 빌딩 https://www.acmicpc.net/problem/5427 7576 토마토 https://www.acmicpc.net/problem/7576 9019 DSLR https://www.acmicpc.net/problem/9019 9205 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9372 상근이의 여행 https://www.acmicpc.net/problem/9372 12886 돌 그룹 https://www.acmicpc.net/problem/12886 16236 아기 상어 https://www.acmicpc.net/problem/16236 O bfs를 통해 거리구하기 16397 탈출 https://www.acmicpc.net/problem/16397 17471 게리맨더링 https://www.acmicpc.net/problem/17471 O 조합, bfs 17836 공주님을 구해라 https://www.acmicpc.net/problem/17836 브루트 포스 문제 이름 링크 정리여부 비고 1051 숫자 직사각형 https://www.acmicpc.net/problem/1051 1065 한수 https://www.acmicpc.net/problem/1065 1182 부분수열의 합 https://www.acmicpc.net/problem/1182 1436 영화감독 슘 https://www.acmicpc.net/problem/1436 1748 수 이어쓰기1 https://www.acmicpc.net/problem/1748 2231 분해 합 https://www.acmicpc.net/problem/2231 2309 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2798 블랙잭 https://www.acmicpc.net/problem/2798 3085 사탕 게임 https://www.acmicpc.net/problem/3085 7568 덩치 https://www.acmicpc.net/problem/7568 10448 유레카 이론 https://www.acmicpc.net/problem/10448 12100 2048(Easy) https://www.acmicpc.net/problem/12100 12738 가장 긴 증가하는 부분 수열3 https://www.acmicpc.net/problem/12738 13460 구슬 탈출2 https://www.acmicpc.net/problem/13460 O while문을 이용한 bfs 14502 연구소 https://www.acmicpc.net/problem/14502 14888 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14889 스타크와 링크 https://www.acmicpc.net/problem/14889 15653 구슬 탈출4 https://www.acmicpc.net/problem/15653 O while문을 이용한 bfs 15683 감시 https://www.acmicpc.net/problem/15683 15684 사다리 조작 https://www.acmicpc.net/problem/15684 15686 치킨 배달 https://www.acmicpc.net/problem/14686 16198 에너지 모으기 https://www.acmicpc.net/problem/16198 17127 벚꽃이 정보섬에 피어난 이유 https://www.acmicpc.net/problem/17127 17142 연구소 3 https://www.acmicpc.net/problem/17142 O 조합, 경우의 수 탐색bfs 17779 게리멘더링2 https://www.acmicpc.net/problem/17779 O 영역 나누어 탐색하기
백준 - 자료구조
백준 자료구조vector 문제 이름 틀린 횟수 정리여부 비고 1158 요세푸스 문제 1 스택 문제 이름 링크 정리여부 비고 1406 에디터 https://www.acmicpc.net/problem/1406 1918 후위표기식 https://www.acmicpc.net/problem/1918 3015 오아시스 재결합 https://www.acmicpc.net/problem/3015 O 다시 풀어보기 9012 괄호 https://www.acmicpc.net/problem/9012 10799 쇠막대기 https://www.acmicpc.net/problem/10799 Set 문제 이름 틀린 횟수 정리여부 비고 1181 단어 정렬 1539 이진 검색 트리 2210 숫자판 점프 7785 회사에 있는 사람 map 문제 이름 틀린 횟수 정리여부 비고 1302 1539 9375
1194-달이차오른다_가자
백준 1194 - 달이 차오른다. 가자https://www.acmicpc.net/problem/1194 문제 해설기존 BFS문제를 푸는 형식에 비트마스킹까지 더해진 문제이다. 비트마스킹을 통해 키를 가지고 있는 각각의 상태들을 체크할 수 있다. 키는 총 6개가 주어지기 때문에 50x50x64 = 160,000 의 공간 복잡도를 갖게 돼 메모리 제한에 걸리지 않는다. 소스 코드#include <bits/stdc++.h>using namespace std;int N, M;char Map[55][55];bool check[1 << 6][55][55];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};queue<pair<int, int>> q;int startY, startX;struct point { int y; int x; int key; int count;};int bfs() { queue<point> q; q.push({startY, startX, 0, 0}); check[0][startY][startX] = true; while (!q.empty()) { int cntY = q.front().y; int cntX = q.front().x; int cntKey = q.front().key; int cntCount = q.front().count; q.pop(); if (Map[cntY][cntX] == '1') { return cntCount; } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 >= ny || ny > N || 0 >= nx || nx > M) { continue; } if (check[cntKey][ny][nx] == true) { continue; } if (Map[ny][nx] == '.') { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } else { // 열쇠에 마주쳤을 경우 if ('a' <= Map[ny][nx] && Map[ny][nx] <= 'f') { int key = (1 << (Map[ny][nx] - 'a')); check[cntKey | key][ny][nx] = true; q.push({ny, nx, cntKey | key, cntCount + 1}); } // 문을 만났을 경우 if ('A' <= Map[ny][nx] && Map[ny][nx] <= 'F') { int door = (1 << (Map[ny][nx] - 'A')); if (door & cntKey) { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } } // 출구를 만났을 경우 if (Map[ny][nx] == '1') { q.push({ny, nx, cntKey, cntCount + 1}); } } } } return -1;}void init() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { cin >> Map[i][j]; if (Map[i][j] == '0') { startY = i; startX = j; Map[i][j] = '.'; } } }}int main(void) { cin >> N >> M; init(); cout << bfs() << '\n'; return 0;}
백준 1406 - 후위표기식
https://www.acmicpc.net/problem/1918 문제 해설문제를 해결할 때 후위 표기식에 대한 명확한 이해와 연산자 우선순위에 대해 고려 해야 한다. 연산자를 별도의 stack에 쌓아가면서 후위 표기식을 만든다. stack에 연산자를 넣기 전에 연산자 비교를 통해 stack에 넣을 려는 연산자 우선순위 보다 stack에 있는 연산자의 우선순위가 작을 때까지 계속해서 stack에서 연산자를 꺼내 후위 표기식에 추가해준다. 연산자 우선순위 (가 제일 높은 우선순위다. * 와 /가 그 다음 우선순위 + 와 -가 다음 우선순위를 갖고 있다. )가 제일 낮은 우선순위다. (를 만날때까지 모든 연산자를 stack에서 꺼낸다. 소스 코드#include <bits/stdc++.h>using namespace std;string str;string result;int main(void) { cin >> str; stack<char> operation; for (int i = 0; i < str.length(); i++) { char cntChar = str[i]; if (cntChar == '(') { operation.push(cntChar); } else if (cntChar == '*' || cntChar == '/') { while (!operation.empty() && (operation.top() == '*' || operation.top() == '/')) { result += operation.top(); operation.pop(); } operation.push(cntChar); } else if (cntChar == '+' || cntChar == '-') { while (!operation.empty() && (operation.top() != '(')) { result += operation.top(); operation.pop(); } operation.push(cntChar); } else if (cntChar == ')') { while (!operation.empty() && operation.top() != '(') { result += operation.top(); operation.pop(); } operation.pop(); } else { result += cntChar; } } while (!operation.empty()) { result += operation.top(); operation.pop(); } cout << result << '\n'; return 0;}
프로그래머스 - 수식 최대화 (Cpp)
https://programmers.co.kr/learn/courses/30/lessons/67257 문제 해설경우의 수 문제이다. 모든 경우의 연산자 우선순위를 만들어 해당 연산자 우선순위를 이용해 연산을 진행하면 된다. 중위표기식으로 나타난 식을 후위 표기식으로 바꿔서 문제를 해결 했다. 경우의 수 만들기만들 수 있는 모든 연산자 우선순위를 만들어줘야 한다. DFS를 이용해 모든 경우의 수를 만들어 줬다. void makeAllCase(int depth) { if (depth == 3) { allCase.push_back(cntCase); } for (int i = 0; i < 3; i++) { int cntOper = operation[i]; if (check[i] == false) { check[i] = true; cntCase[depth] = cntOper; makeAllCase(depth + 1); check[i] = false; } }} 연산자 우선순위를 가반으로 한 연산 가장 높은 우선순위의 연산자가 들어왔을 때 Stack을 확인해 같은 먼저 들어온 같은 우선순위의 연산자가 있는지 확인한다. 같은 우선순위의 연산자가 Stack에 있는 경우 pop 해서 해당 연산을 진행한 후 지금 들어온 연산자를 push한다. 없는 경우에는 Stack에 push 한다. 두번째 우선 순위가 연산자가 들어온 경우 Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다. Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다. 세번째 우선 순위의 연산자가 들어온 경우 Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다. Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다.
백준 1406 - 에디터
https://www.acmicpc.net/problem/1406 문제 해설Stack을 이용한 문제 풀이기본적인 자료구조를 사용해 문제를 해결하는 문제이다. 두개의 스택을 이용해서 커서를 기점으로 커서 왼쪽에 있는 것들은 left 스택에 커서 오른쪽에 있는 단어들은 right 스택에 넣어서 관리를 한다. import java.io.IOException;import java.util.Scanner;import java.util.Stack;public class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); Stack<Character> left = new Stack<>(); Stack<Character> right = new Stack<>(); for (int i = 0; i < str.length(); i++) { left.push(str.charAt(i)); } int numOfCmd = sc.nextInt(); for (int i = 0; i < numOfCmd; i++) { String cmd = sc.next(); if (cmd.equals("L")) { if (!left.isEmpty()) { right.push(left.peek()); left.pop(); } } else if (cmd.equals("D")) { if (!right.isEmpty()) { left.push(right.peek()); right.pop(); } } else if (cmd.equals("B")) { if (!left.isEmpty()) { left.pop(); } } else if (cmd.equals("P")) { char value = sc.next().charAt(0); left.push(value); } } while (!left.isEmpty()) { right.push(left.peek()); left.pop(); } StringBuilder stringBuilder = new StringBuilder(); while (!right.isEmpty()) { stringBuilder.append(right.peek()); right.pop(); } System.out.println(stringBuilder.toString()); }} LinkedList와 ListIterator를 이용한 문제 풀이해당 문제는 LinkedList를 이용해서도 문제를 해결할 수 있다. LinkedList의 원소에 List로 접근을 하게 되면 O(n) 의 시간이 걸려 시간 초과가 뜨게 된다. 때문에 다행이 문제는 Cursor위치를 한칸씩 밖에 못 움직이므로 ListIterator 라는 객체를 이용해 LinkedList를 관리하도록 한다. public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out)); String[] str = br.readLine().split(""); List<Character> charList = new LinkedList<>(); ListIterator<Character> iter = charList.listIterator(); for (int i = 0; i < str.length; i++) { iter.add(str[i].charAt(0)); } int index = charList.size(); int numOfCmd = Integer.parseInt(br.readLine()); for (int i = 0; i < numOfCmd; i++) { char[] inputs = br.readLine().toCharArray(); if (inputs[0] == 'L') { if (iter.hasPrevious()) { iter.previous(); } } else if (inputs[0] == 'D') { if (iter.hasNext()) { iter.next(); } } else if (inputs[0] == 'B') { if (iter.hasPrevious()) { iter.previous(); iter.remove(); } } else if (inputs[0] == 'P') { char value = inputs[2]; iter.add(value); } } for (char c : charList) { wr.write(c); } wr.flush(); }}
백준 - 14499 주사위 굴리기
https://www.acmicpc.net/problem/14499 체점 현황 문제 해설문제를 입력받는 곳에서 함정이 있다. 평소에 세로를 y, 가로를 x로 놓고 문제를 해결하는 사람들에게는 틀리기 너무 좋은 문제주사위의 현재 위치를 계속 추적하면서 주사위 상태도 계속해서 관리해야 한다. 위치를 쉽게 관리하기 위해서 전역변수를 통해 전역적으로 관리했다. #include <iostream>#include <vector>using namespace std;int n, m, x, y, k;int map[22][22];int cube[4][3];vector<int> command;void moveUp() { if (x - 1 >= 0) { x -= 1; int temp01, temp11, temp21, temp31; temp01 = cube[0][1]; temp11 = cube[1][1]; temp21 = cube[2][1]; temp31 = cube[3][1]; cube[0][1] = temp11; cube[1][1] = temp21; cube[2][1] = temp31; cube[3][1] = temp01; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveDown() { if (x + 1 < n) { x += 1; int temp01, temp11, temp21, temp31; temp01 = cube[0][1]; temp11 = cube[1][1]; temp21 = cube[2][1]; temp31 = cube[3][1]; cube[1][1] = temp01; cube[2][1] = temp11; cube[3][1] = temp21; cube[0][1] = temp31; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveRight() { if (y + 1 < m) { y += 1; int temp11, temp12, temp31, temp10; temp11 = cube[1][1]; temp12 = cube[1][2]; temp31 = cube[3][1]; temp10 = cube[1][0]; cube[1][1] = temp10; cube[1][2] = temp11; cube[3][1] = temp12; cube[1][0] = temp31; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveLeft() { if (y - 1 >= 0) { y -= 1; int temp11, temp12, temp31, temp10; temp11 = cube[1][1]; temp12 = cube[1][2]; temp31 = cube[3][1]; temp10 = cube[1][0]; cube[1][0] = temp11; cube[1][1] = temp12; cube[1][2] = temp31; cube[3][1] = temp10; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveCube() { int commandNum = command.size(); for (int i = 0; i < commandNum; i++) { int cntCommand = command[i]; if (cntCommand == 1) { moveRight(); } if (cntCommand == 2) { moveLeft(); } if (cntCommand == 3) { moveUp(); } if (cntCommand == 4) { moveDown(); } }}int main(void) { cin >> n >> m >> x >> y >> k; for (int i = 0; i < n; i++) { { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } } map[x][y] = 0; for (int i = 0; i < k; i++) { int temp = 0; cin >> temp; command.push_back(temp); } moveCube(); return 0;}
백준 3190 - 뱀
https://www.acmicpc.net/problem/3190 체점 현황 전체 소스 코드#include <bits/stdc++.h>using namespace std;int board[110][110];int board_size;int num_of_apple;int num_of_command;map<int, char> command;// 동, 남, 서, 북int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int direction[4] = {0, 1, 2, 3};struct snake { int y; int x; int dir;};int main(void) { cin >> board_size >> num_of_apple; for (int i = 0; i < num_of_apple; i++) { int y, x; cin >> y >> x; board[y][x] = 1; } cin >> num_of_command; for (int i = 0; i < num_of_command; i++) { int time; char dir; cin >> time >> dir; command[time] = dir; } queue<pair<int, int>> snake_tail; int snake_head_y = 1; int snake_haed_x = 1; int snake_dir = 0; snake_tail.push({1, 1}); board[1][1] = 2; int time = 0; while (true) { time++; snake_head_y += dy[snake_dir]; snake_haed_x += dx[snake_dir]; snake_tail.push({snake_head_y, snake_haed_x}); if (board[snake_head_y][snake_haed_x] == 2) { cout << time << '\n'; return 0; } if (0 >= snake_head_y || snake_head_y > board_size || 0 >= snake_haed_x || snake_haed_x > board_size) { cout << time << '\n'; return 0; } if (board[snake_head_y][snake_haed_x] == 1) { board[snake_head_y][snake_haed_x] = 2; } else { board[snake_head_y][snake_haed_x] = 2; board[snake_tail.front().first][snake_tail.front().second] = 0; snake_tail.pop(); } if (command.find(time) != command.end()) { char com = command[time]; command.erase(time); if (com == 'L') { snake_dir = (snake_dir + 3) % 4; } else { snake_dir = (snake_dir + 1) % 4; } } } return 0;}
JPA - Entity의 생명주기
목차 JPA - Entity의 생명주기 JPA - Persist Context (영속성 컨텍스트) 엔티티 생명주기비영속 (new/transient) Entity 객체가 영속성 컨텍스트와 전혀 관계가 없는 새로운 상태 Entity 객체가 생성돼 아직 영속성 컨텍스트에 저장되기 전 상태다. // 비영속 상태Member member = new Member();member.setId(101L);member.setName("HelloJPA"); 영속 (managed) Entity 객체가 현재 영속성 컨텍스트에 관리되는 상태