티스토리

무지성 코딩뉴비

검색하기

블로그 홈

무지성 코딩뉴비

anwltjdzheldsbql.tistory.com/m

노가다 김씨 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

백준 문제 20541번 앨범정리 문제풀이 c++ https://www.acmicpc.net/problem/20541 20541번: 앨범정리 지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다. www.acmicpc.net 코드 //20541번 #include #include #include #include #include #include using namespace std; class Album { private: Album* parentAlbum; string albumName; int photoCnt; int albumCnt; set photoSet; //사진이름 map albumMap; //자식 앨범이름 ,.. 공감수 0 댓글수 0 2022. 6. 23.
백준 문제 14501번 퇴사 문제풀이 c++ https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제해석 문제를 보면 dp 문제임을 어렵지 않게 알 수있는데 나는 탑다운 형식으로 dp를 작성하였다. 예시와 같은 문제일때 1일 부터 확인하는게 아닌 7일부터 확인해야한다. 1일을 확인해보자 1일 상담을 하면 2일 3일은 상담을 할 수 없다. 즉 1일 상담의 금액 P[0]과 4일부터 상담했을때 최대 이익 =dp[3] 5일부터 상담했을때 최대 이익 =dp[4] 6일부터 상담했을때 최대 이익 =dp[5] 7일부터 상담했을때 최대 이익 =dp[6] 의 합중 가장 큰것이 답이 된다. 즉 dp[0]=max(p[0]+dp[4],p[0]+dp[5.. 공감수 0 댓글수 0 2022. 4. 11.
백준 문제 19236번 청소년 상어 문제풀이 c++ https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제해석 예전에 이 문제를 처음 봤을때 생각 났었던 아이디어는 백트래킹이 떠오르긴했는데 막상 직접 구현을 하기에 빡세게 느껴졌어서 언젠가 풀어야지하고 미루다가 얼마 전에 풀게 되었다. 실제로 백트래킹을 이용한 깡구현 문제인데 아이디어는 이렇다. 먼저 4x4 공간이기 때문에 상어의 현재 위치와 방향에 따라서 물고기를 최소 0개에서 최대 3개를 먹게 되는경우가 생긴다는걸 알 수있다... 공감수 0 댓글수 0 2022. 4. 11.
백준 문제 14499번 주사위 굴리기 문제풀이 c++ https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제해석 먼저 전역 변수로 dice를 선언해주었다 순서는 어떻게 하든 상관없지만 나는 앞 위 뒤 바닥 왼 오 순서대로 작성하였다. 현재 주사위의 위치와 방향이 주어지면 방향에 맞게 그 다음의 위치로 주사위를 돌려주고(turn) 다음 그 위치의 지도에 0인가 아닌가에 따라 문제에 설명 되어진 대로 구현한 move함수를 구현하였다. 참.. 공감수 0 댓글수 0 2022. 4. 10.
백준 문제 1069번 집으로 문제풀이 c++ https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 문제해석 이 문제는 기하문제 라고 생각하고 풀었다. 먼저 걸을때와 점프 하는 것이 있는데 점프 없이 걸어갈때 만을 먼저 살펴보자 그렇다면 1초당 1만큼 움직이므로 집까지의 걸리는 시간은 거리 d=sqrt(X*X+Y*Y)이다. 그런데 시작 점에서 점프를 섞어서 집으로 가는 방법 역시 존재 할 수있다. 처음에 빨간색 처럼 점프거리가 집 까지의 거리 보다 짧아 안 닿는 경우와 초록색 처럼 .. 공감수 0 댓글수 0 2022. 4. 10.
백준 문제 7453번 합이 0인 네 정수 문제풀이 c++ https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제해석 전에 풀어봤던 3151번 합이 0 문제와 비슷한 문제 같다는 느낌을 받았다. https://www.acmicpc.net/problem/3151 다만 3151번은 3개 합이 0이 되는 쌍의 갯수를 찾는 것 이고 이 문제는 4개 합이 0이 되는 쌍의 갯수를 찾는 것 이다. 그냥 모든 경우를 확인해버리면 배열의 크기가 최대 4000개 이므로 4000^4 이므로 이렇게 풀면 시.. 공감수 0 댓글수 0 2022. 4. 10.
백준 문제 2583번 영역 구하기 문제풀이 c++ https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제해석 문제에 나온 설명처럼 빗금이 없는 부분의 영역을 구하여 오름 차 순으로 출력하면되는데 빗금이 있는곳을 1 없는곳을 0으로 세팅한 후 dfs또는 bfs를 사용하여 각 영역의 넓이를 오름차순으로 출력하여 풀었다. 문제에선 좌표로 x,y좌표로 나타나있는데 배열로 풀 경우 행 열로 표현이 편하기 때문에 뒤집어 풀었다. 무슨 말이냐면 윗 그림과 아래 그림은 동치인데 편의상 아래.. 공감수 0 댓글수 0 2022. 4. 10.
백준 문제 11052번 카드 구매하기 문제풀이 c++ https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제해석 전형적인 dp문제인데 4 1 5 6 7 입력이 위 처럼 들어왔다고 가정해보자 카드 4장을 구매하는 경우는 1+1+1+1 1+1+5 1+6 7 5+5 이렇게 5가지가 존재하고 이 중 5+5가 가장 큰 값이 되므로 이것이 답이된다. 위의 5가지 경우를 식으로 나타내면 dp[4]=max({dp[3]+p[1],dp[2]+p[2],dp[1]+p[3],dp[0]+p[4]})가 되고 점화식을 일반화 하면 j.. 공감수 0 댓글수 0 2022. 4. 10.
백준 문제 1655번 가운데를 말해요 문제풀이 c++ https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제해석 이 문제는 예전에 풀어봤던 2696번 중앙값 구하기 https://www.acmicpc.net/problem/2696 이것과 같은 문제이다. 아이디어는 이렇다. 우선순위큐 두개를 선언하는데 하나는 오름차순 하나는 내림차순으로 한다. 항상 왼쪽 우선순위 큐 내의 모든숫자의 숫자는 중앙 값보다 작은 값이 오른쪽 우선순위 큐 내의 모든숫자는 중앙 값보다 크게 조절을 하자 입력을.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 1715번 카드 정렬하기 문제풀이 c++ https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제해석 문제를 읽고 조금 생각해보니 최소 비교를 구하려면 계속 최소의 비교를 하면 되면 되지 않을까 하는 결론에 도달했다. 1.카드 묶음중 가장 작은 두개의 뭉치를 골라 비교를한다. 2.비교를 하면 두 뭉치는 합쳐서 하나의 뭉치가 된다. 1번과 2번의 과정을 카드 뭉치가 1개가 될 때까지 반복하자. 이 과정을 따라 10 20 40이 입력이 주어졌을때를 보자 가장 작은 뭉치 두개는 .. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 10827번 a^b 문제풀이 python https://www.acmicpc.net/problem/10827 10827번: a^b 첫째 줄에 a와 b가 주어진다. (0 < a < 100, 1 ≤ b ≤ 100) a는 최대 소수점 9자리이며, 소수가 0으로 끝나는 경우는 없다. a는 항상 소수점이 포함되어 있다. www.acmicpc.net 문제해석 실수형으로 a^b를 할 경우 오차가 생기기 마련인데 그것을 정확하게 출력하는게 문제이다. 이 문제를 나는 정수로 보고 풀었다. 예를들어 3.141592 3 가 입력으로 주어 졌을경우 3141592^3를 구한다. 3141592^3=31006257328285746688 소수점을 삽입해야하는 곳을 찾는다. 여기서 소수점의 위치는 31뒤에 찍어야하므로 답은 31.006257328285746688이 된다. 소.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 14890번 경사로 문제풀이 c++ https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제해석 경사로를 놓고 지나갈 수 있는 길이 몇개인지 찾는 그냥 구현문제이다. 그런데 어떻게 할지 몰라서 생각나는대로 그냥 막 구현했다.. 아이디어는 이렇다. 각 행마다 1.왼쪽에서 오른쪽 2.오른쪽에서 왼쪽 각열마다 3.위쪽에서 아래쪽 4.아래쪽에서 위 길을 갈 수있는 경우가 이렇게 있는데 a.1 1이 가능하면 그 행은 갈 수있는 길이므로 ans값을 1증가 a.2 1이 불가능하면 2를 확인한다. a.2.1 2가 가능하.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 16234번 인구이동 문제풀이 c++ https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제해석 dfs를 사용해서 구현하였다. 아이디어는 이렇다. 1.인접한 나라의 인구 차이가 범위내에 있다면 벡터를 인접리스트처럼 사용해서 국경을 연결해 그래프를 만든다. 2.그리고 dfs를 통해서 연결된 모든 국가의 인구를 합쳐서 국가의 개수만큼으로 나누어 재분배를 시킨다. 1,2를 반복하고 종료 조건은 9328번 열쇠 코드에서 작성했던거 처럼 전과 후의 배열을 비교해서 인구가 달라진.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 2573번 빙산 문제풀이 c++ https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제해석 dfs 또는 bfs로 이 문제를 풀 수있다. 난 dfs로 구현하였는데 bfs로 구현해도 상관없다 먼저 종료 조건 부터 생각해보자. 모든 빙산이 녹거나 또는 빙산섬이 두개로 분리 될때까지 탐색을 계속 돌려주면된다. dfs는 물이 아닐때 즉 빙산일때 돌려 주면 되고 dfs를 한번 돌릴때마다 섬의 개수를 하나 세주면 된다. 섬이 2개가 된 순간 즉시 시간을 출력하고 종료를 하면된다. 코드.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 12100번 2048 (Easy) 문제풀이 c++ https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제해석 그림생략 평범한 2048게임과 같은 규칙이다. 단 새로은 블록이 추가되지 않는다는 차이 점이 있다. 최대 5번 움직일수있고 상하좌우 4방향이므로 총 4^5 = 1024 가지의 경우가 존재한다. 그래서 제한시간에비해 경우가 적으므로 전부 다 해보는 것으로 하기로 결정했다. 상하좌우의 경우에 따라 move함수를 구현했는데 이게 보니까 200줄이 넘는다. 사실 반복.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 9328번 열쇠 문제풀이 c++ https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제해석 아이디어는 이렇다. 입력 받을때 입구가 될 수 있는 모든 좌표를 저장한다. 주의 할점은 가장 바깥쪽 . 뿐만 아니라 $이거나 대문자이거나 소문자일때 입구가 될 수있다. 즉 '*' 벽 만 아니면된다. 그리고 가지고 있는 키를 저장한다. 그리고 너비우선탐색을 하는데 소문자를 만나면 키를 업데이트해주고 대문자를 만나면 열수있는 문이면 빈공간처럼 그렇지 않으면 벽처럼 취급하고 문서를 먹으면 답을 1올려준다... 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 1504번 특정한 최단 경로 문제풀이 c++ https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제해석 1번 정점에서 N번정점까지의 최단거리는 다익스트라 알고리즘을 사용하면 구할수있다. 그러나 여기선 V1,V2가 주어지고 꼭 이 두점을 지나야 한다는 조건이 붙어있다. 맨 처음 이문제를 볼때는 너무 어렵게 생각한 나머지 어떻게 풀지 생각이 안났는데 며칠 지난후 나중에 다시 이 문제를 보니 갑자기 어떻게 풀어야할지 보이길래 어렵게 생각한게 독이 되었.. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 13977번 이항 계수와 쿼리 문제풀이 c++ https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제해석 nCk와 페르마의 소정리 두가지를 동시에 사용하면 이 문제를 풀수가 있다. 분자를 A 분모를 B로 p=1000000007로 치환하면 A/B mod p를 구하는 것이 되고 이는 (A mod p * B^-1 mod p) mod p이다. A mod p는 미리 전처리해주면 그만이고 문제는 B^-1 mod p를 구하는 것인데 여기서 페르마의 소정리를 쓴다. 위의 페르마 소정리에서 n^p = n mod .. 공감수 0 댓글수 0 2022. 4. 3.
백준 문제 1027번 고층 건물 문제풀이 c++ https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 문제해석 N이 최대 50이므로 N^3 브루트포스 전체탐색이 가능하다. 예로 N=4인경우 0번째 건물과 1번째 건물이 서로 보이나 비교 0번째 건물과 2번째 건물 서로 보이나 비교 0번째 건물과 3번째 건물 서로 보이나 비교 1번째 건물과 2번째 건물 서로 보이나 비교 1번째 건물과 3번째 건물 서로 보이나 비교 2번째 건물과 3번째 건물 서로 보이나 비교 즉 i번째 건물 과 j번째 건물이 서로 보.. 공감수 0 댓글수 0 2022. 3. 28.
백준 문제 1766번 문제집 문제풀이 c++ https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제해석 위상정렬 문제인데 저번에 풀었던 2252번 줄 세우기보다 조건이 많아졌다. 무엇보다 3번 조건때문에 이 문제를 dfs로 풀경우 제일 깊은 곳까지 들어가서 숫자를 확인해야한다. 당연히 이렇게 풀면 매우 비효율적이되기때문에 bfs 그리고 큐대신 우선순위 큐를 사용하여 풀어야 한다. bfs 위상정렬에서는 indegree가 필요하기 때문에 indegree 배열을 최.. 공감수 0 댓글수 0 2022. 3. 28.
백준 문제 3151번 합이 0 문제풀이 c++ https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 문제해석 그냥 N이 최대 10000개이고 4초 제한이라 N^2으로 풀릴거같아서 별 생각 안하고 브루트포스 방법을 사용했다. 먼저 N개중에 2개를 뽑아서 더한 값을 x라고 하면 선택하지 않은 것중 -x가 있는지 없는지 확인했다. 코드에서 p는 양수 m은 음수이다. 예를들어 p[36]=2 이면 36이 2개란 뜻이고 m[24]=5 이면 -24가 5개란 뜻이다. 근데 귀찮게 이렇게 안하고 map 사용하면 되는.. 공감수 0 댓글수 0 2022. 3. 28.
백준 문제 2252번 줄 세우기 문제풀이 c++ https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제해석 위상정렬 문제인데 dfs를 사용한 위상정렬로 코드를 작성하였다. dfs로 위상정렬을 할 경우 역순으로 출력해야한다. 답이 여러가지인경우 아무거나 출력하면되기 때문에 좀 수월했다. 만약 여러 답중 사전순으로 가장 앞선 것을 출력을 요구하면 우선순위큐를 사용한 bfs 위상정렬로 풀어야 했을 것 같다. 먼저 입력이 들어온대로 방향 그래프를 만들어준 후.. 공감수 0 댓글수 0 2022. 3. 28.
백준 문제 1188번 음식 평론가 문제풀이 c++ https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 문제해석 예시를 들어 보자 평론가가 소세지보다 많을때 예를 들어 소세지 2개 평론가 5명이 있는경우 소세지 하나의 양을 5라고 두면 한 평론가당 먹어야 하는 양은 2만큼 이고 아래 그림과 같은 과정을 거친다. 첫 과정에서 2번 칼질 한 후에 소세지 2개 평론가 3명이 된다. 두번째 과정에서 2번 칼질 한 후에 소세지 소세지 2개 평론가 1명이 된다. 세번째 과정에서 칼질이 필요없으므로 총 4번의 칼질이 필요하다. dp[2][5]=2+dp[2][3] dp[2][3]=2+dp[2][1] dp[2][1]=.. 공감수 0 댓글수 0 2022. 3. 28.
백준 문제 1007번 벡터 매칭 문제풀이 c++ https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제해석 힌트: 모든 벡터의 합 = 벡터의 끝점의 합 - 벡터의 시작점의 합 이다. 따라서 주어진 점의 개수의 반만큼을 시작점으로 잡고 나머지 반을 끝점으로 하는 모든 경우를 구한다. 그리고 벡터의 길이를 계산해서 그것들중 가장 작은 값을 출력해주면된다. 반씩 나누는 모든 경우는 백 트래킹을 사용했다. 코드 #include #include #include #include typedef l.. 공감수 0 댓글수 0 2022. 3. 28.
백준 문제 2436번 공약수 문제풀이 c++ https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 문제해석 최대 공약수를 x 최소 공배수를 y라고 하면 x*y값의 약수 쌍 중 최소가 되면서 그 둘의 최대 공약수가 x가 되는 값을 찾으면된다. 나는 최소 공배수를 최대 공약수로 나눠서 그 값을 z=y/x로 두었고 z의 약수 쌍중 최소가되면서 최대 공약수가 1인것인 쌍을 찾은수 그 둘에 각각 x를 곱해서 출력하였다. 최대 공약수를 구하는 것은 유클리드 호재법을 사용하여 구하였다. 코드 #includ.. 공감수 0 댓글수 0 2022. 3. 22.
백준 문제 1722번 순열의 순서 문제풀이 c++ https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 문제해석 이런 문제는 예시하나 들어서 규칙찾아내서 작성하는게 편한거같다. 케이스 2번부터보자. 4 2 3 2 1 4 가 입력이 주어졌을 경우를 예를들어보자. 처음에 작은 순서대로 1 2 3 4 가있고 3이 처음 수란것은 3!만큼 두번 움직였기때문에 3이나온것이다. 그래서 여기서 2*3!=12 3을 사용하였으니 그 다음 작은 순서대로 1 2 4 가있다. 2번째 수로 2.. 공감수 0 댓글수 0 2022. 3. 22.
백준 문제 1405번 미친 로봇 문제풀이 c++ https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 문제해석 이 문제에서 바로 확인한것이 N의 범위이다. N의 최대값은 최대 14이므로 백트래킹으로 구현해도 약 3^14이면 충분히 시간초과는 안난다. 확률을 순서대로 동서남북의 순서로 배열에 담고 dy dx역시 동서남북 순서로 넣었다. 그리고 지나온길을 visited배열로 마킹하고 마킹이 되지않은쪽으로 깊이 n까지 도달하는 모든경우의 확률을 더해서 출력하면 답이된다. 시작하자마자 서쪽 또는 북쪽.. 공감수 0 댓글수 0 2022. 3. 22.
백준 문제 1016번 제곱 ㄴㄴ 수 문제풀이 c++ https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 문제해석 수의 범위가 굉장히 큰 것에 비해 max와 min의 차이는 최대 100만까지 나지 않는 점을 주목해야한다. 따라서 사실상 최대 100만 정도 배열이면 이 문제를 푸는데 지장이 없다. min부터 max까지 순서대로 배열에 저장하고 이에 대해 에라토스테네스의 체는 아니지만 그와 같은 방식으로 걸러주면된다. 예를 들어 min=50 max=60 이 입력으로 주어지면 1n>>m; .. 공감수 0 댓글수 0 2022. 3. 22.
백준 문제 1238번 파티 문제풀이 c++ https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제해석 예를 들어 n=4 ,x=2 인 경우를 생각해보자 1->2 + 2->1 2->2 + 2->2 (시작점 끝점이 같은경우는 없음) 3->2 + 2->3 4->2 + 4->1 이 세가지 경우 중에 가장 작은 값이 답이 된다. 따라서 각 마을에서 마을까지 전부 다익스트라를 돌리든 플로이드를 돌리든 최단 거리를 저장시켜놔야한다고 생각했다. 마을개수가 최대 1000이므로.. 공감수 0 댓글수 0 2022. 3. 22.
백준 문제 1753번 최단경로 문제풀이 c++ https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제해석 다익스트라 문제이다. 그런데 정점의 개수가 20000개라서 n^2 다익스트라로 구현하면 시간초과가 난다. 그래서 현재 상태에서 가장 가까운 정점을 구하는것을 우선순위큐로 구현하면 시간 초과를 피할수있다. 다익스트라를 실행하고 처음 d배열을 세팅할때 그리고 지금까지의 거리보다 거쳐서 가는 길이 더 최단인경우에 우선순위 큐에 그 정보를 푸쉬해주면된다. 코.. 공감수 0 댓글수 0 2022. 3. 22.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.