분류 전체보기

[백준 14890] 경사로 C++

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 구슬 탈출 2 문제를 풀다가 코드가 너무 길어지고.. 구현이 더러워져서 도망치듯 풀게 된 문제다. 도망쳐왔지만 이 문제도 절대 만만하진 않았다. 분명 문제에는 경사로는 서로 겹치면 안 된다고 적혀있어서 가로와 세로 경사로끼리도 겹치면 안되는줄 알았다. 그런데 알보고니 가로 경사로와 세로 경사로는 서로 영향을 주지 않기 때문에 문제가 더 쉬워졌다! 가로길 + 세로길 해주면 답이 나오게 되었다! 문제 설명이 부실한듯해서 시간을 좀 잡아먹었..

[OS] Process #1

Process 프로세스? 실행중인 프로그램을 프로세스 라고 한다. 프로그램은 생명이 없다. 하지만 프로그램이 실행이 되면 프로세스가 되고 프로세스는 프로그램이 종료될 때까지 생명활동을 이어간다. 프로그램이 실행이 되면 아래 그림과 같이 disk의 프로그램 정보가 memory로 load 된다. 프로그램에 속한 모든 정보가 memory로 load되는것은 아니다. OS는 프로그램 실행 도중 필요한 코드를 그때그때 load해서 사용한다. memory 공간은 Code, Data, BSS, Heap, void, Stack 공간으로 구성된다. Code : 프로그램 코드가 올라오는 부분 Data : 초기화된 전역 변수, static 변수 BSS : 초기화되지 않은 전역 변수, static 변수 Heap : malloc..

[백준 1238] 파티 C++

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 단순한 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만 이 문제는 A->X로가는 최단거리 + X->A로 되돌아오는 최단거리를 구해야 한다. A->X로 가는 최단거리를 구해보자. 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O(|V||E|) = 10,000,000 이 되어 시간내에 풀 수 있다고 생각했다. 그래서 A->X로 가는 최단거리를 A의 개수만..

[백준 1509] 팰린드롬 분할 C++

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일단 문자열의 모든 범위에 따른 팰린드롬 여부를 2차원 table로 만들었다. dp[st][ed]에는 st부터 ed까지의 문자열이 팰린드롬인지 확인여부가 담겨있다. dp table을 채울 때 str[st]와 str[ed]가 같고 dp[st+1][ed-1]이 팰린드롬이면 dp[st][ed]도 팰린드롬인 성질을 이용해서 O(n^2)으로 테이블을 구할 수 ..

[백준 3197] 백조의 호수

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS 1. 문제 해결 아이디어 2021.07.01 - [Algorithm/BOJ] - [백준 2636] 치즈 C++ [백준 2636] 치즈 C++ 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄 hyeo-noo.tistory.com 백조 문제에서 매일 얼음 표면을 찾고, 얼음을 녹이는..

[백준 2636] 치즈 C++

2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net BFS 1. 문제 해결 아이디어 치즈의 겉 표면을 찾기 위한 BFS + 겉표면을 녹이는 BFS 이렇게 2개의 BFS를 사용해서 풀었다. BFS를 2개 쓴거라서 아마 내 풀이가 최적의 풀이는 절대 아닐거라 생각한다. 먼저 공기와 맞닿아 있는 치즈표면을 BFS를 통해서 모두 구하면서 개수를 저장해 놓는다. 이때 치즈가 없다면 종료 만약 치즈가 있다면 겉표면 치즈들을 녹이는 BFS를 수행한다. 두 과정을 합칠 수 있을것 같다.. 2. 코드 1 2 3 4 5 6 7 8 9 10..

[백준 4196] 도미노 C++

4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이.. hyeo-noo.tistory.com 타잔 알고리즘을 사용해서 풀었다. 개인적으로 코사라주보다 직관적이..

Sorting Game (SORTGAME)

algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com BFS, 최단거리 처음보는 유형의 문제. 신기한 문제 지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데 이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다. 1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다. ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상..

[백준 1562] 계단 수 C++

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 비트필드를 이용한 다이나믹 프로그래밍 1. 문제 해결 아이디어 현재 구한 계단 수의 자릿수, 마지막 숫자 위 2개의 정보를 가지는 2차원 배열로 문제를 해결하려 했었는데 당연히 답이 제대로 나오지 않았다. 0~9의 숫자가 각각 사용되었는지 아닌지 알아야 하기 때문에 (10개의 숫자 각각 사용되었는지 아닌지에 대한 경우의 수 2^10) 따라서 [1

[백준 2623] 음악프로그램 C++

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상 정렬 1. 문제 해결 아이디어 indegree를 활용한 위상 정렬로 풀었다. 입력을 받을 때 각 정점마다 indegree가 몇 개 인지 배열에 저장해준다. 위상 정렬 bfs를 수행하면서 현재 정점의 자식 정점들의 indegree를 하나씩 빼준다. 만약 자식 정점의 indegree가 0이 된다면 현재 정점을 queue에 넣어준다. queue에 넣는다는 의미는 자신보다 먼저 수행되어야 할 정점이 없어서 현재 정점을 바로 실행해도 무방하다는 ..